Binary Search Tree

置放大量數字並進行排序的資料結構。原理是Divide and Conquer，把所有數字分成一個與兩半，樹根在中間，左子樹較小，右子樹較大，然後遞迴分割下去。

插入、刪除、搜尋的時間複雜度等同於二元搜尋樹的高度。資料可以動態增加和減少，二元搜尋樹的高度亦會變動，因此時間複雜度最差為O(N)，最佳為O(logN)。所有節點連成一線的時候是最差的，所有節點形成full tree是最佳的。

空間複雜度等同於節點數目，空間複雜度是O(N)。

尋找極小值、極大值，從樹根開始往左小孩走到底、往右小孩走到底就可以了。時間複雜度等同於二元搜尋樹的高度。

樹葉可以額外建立線索（Thread），如此就能依照大小順序走訪元素。建立線索不影響時間複雜度與空間複雜度。

最佳二元搜尋樹（Optimal Binary Search Tree）

如果二元搜尋樹的資料不會變動，則可以依照每個節點被搜尋到的頻率，使用Dynamic Programming求得結構最佳的二元搜尋樹，藉此加快搜尋速度。建立時間為O(N^2)。

UVa 10304

排名（Ranking）

二元搜尋樹雖然有排序的功效，但是卻沒有排名的功效。如果想知道資料的排名，那麼就要在每個節點新增一個變數，記錄其子樹的節點個數，如此便可以用Divide and Conquer的方式求得每筆資料的排名。不影響時間複雜度與空間複雜度。

UVa 10909

以陣列表示二元搜尋樹

利用陣列索引值定位到樹的節點。優點是實作輕鬆，結構簡單，效率高。缺點是當二元搜尋樹沒有形成full tree的時候，會有很多陣列空間沒有使用到，浪費記憶體，甚至記憶體會不敷使用。

int left_child(int index) {return index * 2;} int right_child(int index) {return index * 2 + 1;} void binary_tree() { int tree[5 + 1]; // array[0]不使用，只有五個節點。 cout << "根為" << tree[1]; cout << "根的左邊小孩是" << tree[ left_child(1) ]; cout << "根的右邊小孩是" << tree[ right_child(1) ]; }

AVL Tree

平衡二元搜尋樹。令每個葉子的高度落差不會太多，讓各項操作的運行速度很穩定均勻，不會出現忽快忽慢的極端現象。限制樹上所有節點，其左右兩子樹的高度差不會超過一，此舉造成整棵樹的高度為O(logN)。每當插入、刪除，高度差超過一，就馬上在高度落差太大的子樹上面，對子樹的根使用右旋轉或左旋轉，把左右子樹的高度差維持在一以下。

插入、刪除、搜尋的時間複雜度為O(logN)。旋轉的時間複雜度是O(1)，最多旋轉兩次就會平衡。至於空間複雜度仍是O(N)。

struct Node { Node* l, *r; int h, c, key; Node(int key): l(0), r(0), h(1), c(1), key(key) {} void update() { h = 1 + max(l?l->h:0, r?r->h:0); c = (l?l->c:0) + 1 + (r?r->c:0); } }; Node* rL(Node* x) // 左旋轉 { Node* y = x->r; x->r = y->l; y->l = x; x->update(); y->update(); return y; } Node* rR(Node* x) // 右旋轉 { Node* y = x->l; x->l = y->r; y->r = x; x->update(); y->update(); return y; } Node* balance(Node* x) { x->update(); if (x->l->h > 1 + x->r->h) { if (x->l->l->h < x->l->r->h) x->l = rL(x->l); x = rR(x); } else if (x->r->h > 1 + x->l->h) { if (x->r->r->h < x->r->l->h) x->r = rR(x->r); x = rL(x); } return x; } Node* insert(Node* x, int key) { if (x == 0) return new Node(key); if (key < x->key) x->l = insert(x->l, key); else x->r = insert(x->r, key); return balance(x); }

Red-Black Tree

紅黑樹的功效等同平衡二元搜尋樹，但是效率更勝一籌。

http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf

可以直接使用STL的set、map。

Skip Lists

置放大量數字並進行排序的資料結構。不用樹狀結構，而改用高度不同的Linked List來連接資料。資料結構在概念上可以表示成Left Child-Right Sibling Binary Tree的模式。時間複雜度與空間複雜度與Binary Search Tree皆相同，但是實際運作效率比Binary Search Tree還要好。

Splay Tree

splay是反覆旋轉兩次，把當前節點旋轉至根。插入、刪除後就立即splay；儘管樹沒有完全平衡，插入、刪除的均攤時間複雜度仍是O(logN)。實際運作效率比AVL Tree稍快。

運用splay就很容易拆接子樹，拆接子樹的時間複雜度為O(logN)。

Binary Heap

常簡稱Heap，置放大量數字，並且可以隨時求最大（小）值的資料結構。插入、刪除、求極值的時間複雜度為O(logN)，資料可以動態增加和減少。

可以直接使用STL的priority_queue。

UVa 501 10587 11997

Binomial Heap

置放大量數字，並且可以隨時求最大（小）值的資料結構。遞迴結合多個高度不同的Binomial Tree，所構成的一個資料結構，以抽象化的角度來看像是一個二進位系統。兩個Binomial Heap在結合的時候，原理就像是在做二進位加法一樣，因而得此名。

Fibonacci Heap

置放大量數字，並且可以隨時求最大（小）值的資料結構。一個規則極其詭異的結構，重點在於他有一個特殊功能叫做decrease key，可以搜尋數字，並且還可以減少該數字，時間複雜度均攤之後僅有O(1)。另外，插入的時間複雜度均攤之後僅有O(1)。

Quake Heap

置放大量數字，並且可以隨時求最大（小）值的資料結構。與Fibonacci Heap功能相同，但是據說簡單很多。

http://www.cs.uwaterloo.ca/~tmchan/pub.html

Binary Search Tree

BST也可以當作Heap使用。

Heap::push  = BST::insert
Heap::pop   = BST::get_extremum + BST::delete
Heap::peek  = BST::get_extremum
Heap::merge = BST::merge

Heap的每一項操作，都可以用BST兜出來，時間複雜度完全一樣，唯一的例外是：Heap可以預先偷看將要彈出來的元素，僅需O(1)時間；BST要偷看，就等同於需要花費O(logN)時間搜尋最小值或最大值。

Treap

Binary Search Tree與Binary Heap進行合體術變成的東西。

令數字有額外的優先次序，同時具有「排序優先次序」的功能與「求最大（小）值」的功能。

Cartesian Tree

令數字具有額外的索引值。Cartesian Tree是二元樹，根的數值大（小）於左右子樹，根的索引值區隔左右子樹。

Cartesian Tree可以看作是一種Treap。

Cartesian Tree是以online方式建立，由左到右讀取陣列元素，每讀取一個元素就建立一個節點，整棵樹剛好會來回遍歷一次。可使用stack來實作，確保stack的元素是照順序排好的。

van Emde Boas Tree（vEB Tree）

置放大量正整數（與零）的資料結構，並且可以作為Double Ended Priority Queue。利用Divide and Conquer，將0到K-1的整數分為sqrt(K)個區塊，每個區塊的範圍大小為sqrt(K)，接著各區塊各自遞迴下去。

以另一個角度來看，就是把一個整數從中間切開，成為高位數字部份和低位數字部份，把高位數字抽取出來，作為索引值，找出對應的陣列格子，並遞迴下去以儲存低位數字。跟Trie有點像。

每次搜尋、插入、刪除為O(loglogK)，總時間複雜度為O(NloglogK)，其中N為正整數個數，K為這些正整數的最大值。

速度是快了那麼一點，然而缺點是記憶體用很兇，空間複雜度為O(K)。【待補分析】

其實我們也可以使用Counting Sort來紀錄正整數，速度還比vEB Tree快，只不過Counting Sort不能動態排序罷了。

struct vEB_Tree // [0, K-1] have m digits in binary { int digit; // store m。或者紀錄陣列有多大（遞迴有多深）。 vEB_Tree* lower[possibility of m/2 digits]; };

若要作為Double Ended Priority Queue，則在每個節點加上兩個變數，紀錄該子樹目前擁有的數字的大小範圍。

struct vEB_Tree { int digit; vEB_Tree* lower[possibility of m/2 digits]; int min, max; // 子樹目前擁有的數字們，最大值與最小值。 };