트리 정렬

Harshit Jindal 2023년10월12일
  1. 트리 정렬 알고리즘
  2. 트리 정렬 예
  3. 트리 정렬 알고리즘 구현
  4. 트리 정렬 알고리즘 복잡성
트리 정렬

트리 정렬은 온라인 정렬 알고리즘입니다. 이진 검색 트리 데이터 구조를 사용하여 요소를 저장합니다. 이진 검색 트리의 순회 순회를 수행하여 정렬 된 순서로 요소를 검색 할 수 있습니다. 온라인 정렬 알고리즘이므로 삽입 된 요소는 항상 정렬 된 순서로 유지됩니다.

트리 정렬 알고리즘

n 개의 요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정 해 보겠습니다.

TreeSort()

  • 이진 검색 트리의 배열에서 요소를 삽입하여 이진 검색 트리를 만듭니다.
  • 트리에서 순서대로 순회를 수행하여 요소를 정렬 된 순서로 되돌립니다.

Insert()

  • 배열 요소A[i]와 같은 값으로 BST 노드를 만듭니다.
  • 삽입 (노드, 키)
    • If root==null, return the newly formed node.
    • If rootdata < key, rootright = insert(root➡right,key)
    • If rootdata > key, rootleft= insert(root➡left,key)
  • 원래 루트에 대한 포인터를 반환합니다.

Inorder()

  • 왼쪽 하위 트리를 탐색합니다.
  • 루트를 방문하십시오.
  • 오른쪽 하위 트리를 탐색합니다.

트리 정렬 예

배열이(5, 3, 4, 2, 1, 6)이라고 가정합니다. 삽입 정렬 알고리즘을 사용하여 정렬합니다.

트리 정렬 알고리즘

먼저 루트 노드 5를 생성하여 BST를 초기화합니다.

35보다 작으므로5의 왼쪽에 삽입됩니다.

45보다 작지만 3보다 크므로 3의 오른쪽에는 삽입되지만 4의 왼쪽에는 삽입됩니다.

2는 현재 트리에서 가장 작은 요소이므로 가장 왼쪽에 삽입됩니다.

1은 현재 트리에서 가장 작은 요소이므로 가장 왼쪽에 삽입됩니다.

6은 현재 트리에서 가장 큰 요소이므로 가장 오른쪽에 삽입됩니다.

BST가 빌드 된 후 트리에서 순차 순회를 수행하여 최종 정렬 된 배열(1, 2, 3, 4, 5, 6)를 얻습니다.

트리 정렬 알고리즘 구현

#include <bits/stdc++.h>

using namespace std;

class Node {
 public:
  int key;
  Node *left, *right;
};

Node *newNode(int item) {
  Node *temp = new Node;
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

void inorder(Node *root, int arr[], int &i) {
  if (root != NULL) {
    inorder(root->left, arr, i);
    arr[i++] = root->key;
    inorder(root->right, arr, i);
  }
}

Node *insertintoBST(Node *node, int key) {
  if (node == NULL) return newNode(key);
  if (key < node->key)
    node->left = insertintoBST(node->left, key);
  else if (key > node->key)
    node->right = insertintoBST(node->right, key);
  return node;
}

void treeSort(int arr[], int n) {
  Node *root = NULL;
  root = insertintoBST(root, arr[0]);
  for (int i = 1; i < n; i++) root = insertintoBST(root, arr[i]);
  int i = 0;
  inorder(root, arr, i);
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  treeSort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

트리 정렬 알고리즘 복잡성

시간 복잡성

  • 평균 사례

평균적인 경우, BST에n 노드를 삽입하는 시간 복잡도는O(nlogn)정도입니다. 형성된 BST가 균형 BST 일 때 발생합니다. 따라서 시간 복잡도는 [Big Theta] :O(nlogn)의 순서입니다.

  • 최악의 경우

최악의 경우는 배열이 정렬되어 최대 높이가 O(n)인 불균형 이진 검색 트리가 형성 될 때 발생합니다. 높이logn의 일반 BST의 경우 순회에O(logn)시간에 비해 순회에 O(n)시간이 필요하고 삽입에 O(n2)가 필요합니다. . 최악의 경우 시간 복잡도는 [Big O] : O(n2)입니다.

AVL 트리, Red-Black Tree 등과 같은 자체 균형 데이터 구조를 사용하여 O(nlogn)로 줄일 수 있습니다.

  • 베스트 케이스

가장 좋은 경우는 형성된 이진 검색 트리가 균형을 이룰 때 발생합니다. 최적의 시간 복잡도는 [Big Omega] :O(nlogn)입니다. 평균 케이스 시간 복잡성과 동일합니다.

공간 복잡성

이 알고리즘의 공간 복잡도는 이진 검색 트리 내의 각 요소에 대해 n 개의 노드를 만들어야하므로 O(n)입니다.

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

관련 문장 - Sort Algorithm