樹形選擇排序
樹形選擇排序是一種線上排序演算法，它使用二叉搜尋樹資料結構來儲存元素。它使用二叉搜尋樹資料結構來儲存元素。通過對二叉搜尋樹進行順序內遍歷，可以按排序順序檢索元素。由於是線上排序演算法，所以插入的元素始終保持排序的順序。
樹形選擇排序演算法
假設我們有一個包含 n 個元素的未排序陣列 A[]。
TreeSort()
-
將陣列中的元素插入到二叉搜尋樹中，構建二叉搜尋樹。
-
在樹上進行順序遍歷，將元素按排序順序取回。
Insert()
-
建立一個 BST 節點，其值等於陣列元素
A[i]。 -
Insert(node,key)。-
如果
root為null, 返回新形成的節點。 -
如果
root➡data<key,root➡right=insert(root➡right,key) -
如果
root➡data>key,root➡left=insert(root➡left,key)
-
-
返回指向原始根的指標。
Inorder()
-
遍歷左側子樹。
-
訪問根部。
-
遍歷右邊的子樹。
樹形選擇排序示例
假設我們有一個陣列：(5, 3, 4, 2, 1, 6). 我們將使用插入排序演算法對其進行排序。
首先，我們通過建立根節點 5 來初始化 BST。
3 比 5 小，所以它被插入 5 的左邊；4 比 5 小，但比 3 大，所以它被插入 3 的右邊。
4 比 5 小，但比 3 大，所以它被插入到 3 的右邊，但 4 的左邊。
2 是當前樹中最小的元素，所以它被插入到最左邊的位置。
1 是當前樹中最小的元素，所以它被插入到最左邊的位置。
6 是當前樹中最大的元素，所以它被插入到最右邊的位置。
建立完二叉搜尋樹後，我們對樹進行順序遍歷，得到最終的排序陣列 (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) 的不平衡二叉搜尋樹。遍歷需要 O(n) 時間，插入需要 O(n2)時間，而高度 logn 的常規 BST 的遍歷時間為 O(logn)。最壞情況下的時間複雜度為 [Big O]：O(n2)。
使用 AVL 樹、紅黑樹等自平衡資料結構，可以將其降低到 O(nlogn)。
- 最佳情況
當形成的二叉搜尋樹是平衡的時候，就會出現最好的情況。最佳情況下的時間複雜度為 [Big Omega]：O(nlogn)。它與平均情況下的時間複雜度相同。
空間複雜度
該演算法的空間複雜度為 O(n)，因為要為二叉搜尋樹內的每個元素建立 n 個節點。
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