트리 정렬

1. 트리 정렬 알고리즘
2. 트리 정렬 예
3. 트리 정렬 알고리즘 구현
4. 트리 정렬 알고리즘 복잡성

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

트리 정렬 알고리즘

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

TreeSort()

Insert()

Inorder()

트리 정렬 예

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

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

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

4는 5보다 작지만 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(n²)가 필요합니다. . 최악의 경우 시간 복잡도는 [Big O] : O(n²)입니다.

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

• 베스트 케이스

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

공간 복잡성

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