Question

Binary Search Tree

请先参考“ Binary Tree ”。

二元搜寻树。置放大量数字并且进行排序的资料结构。原理是 Divide and Conquer，树根居中，左子树较小或相等，右子树较大，然后递迴分割下去。

插入、删除、搜寻的时间複杂度等同于二元搜寻树的高度。资料可以动态增加和减少，二元搜寻树的高度亦会变动，因此时间複杂度最差为 O(N)，最佳为 O(logN)。所有节点连成一线的时候是最差的，所有节点形成 perfect binary tree 是最佳的。

空间複杂度等同于节点数目，空间複杂度是 O(N)。

寻找极小值、极大值，从树根开始往左小孩走到底、往右小孩走到底就可以了。时间複杂度等同于二元搜寻树的高度。

寻找次大节点，就先往右小孩走一步、再往左小孩走到底就可以了；如果一开始没有右小孩，就往左上父亲走到底，再往右上父亲走一步就可以了。寻找次小节点，方法类似。时间複杂度等同于二元搜寻树的高度。

树叶可以额外建立线索（Thread），左小孩连往次小节点，右小孩连往次大节点，如此就能迅速地依照大小顺序走访元素，实作仅用迴圈即可、免用递迴。建立线索不影响时间複杂度与空间複杂度。

最佳二元搜寻树（Optimum Binary Search Tree）

如果二元搜寻树的资料不会变动，则可以依照每个节点被搜寻到的次数（频率），使用 Dynamic Programming 求得结构最佳的二元搜寻树，藉此减少搜寻时间。建立时间为 O(N^2)。

UVa 10304

扩充资讯（Augmented Tree）

二元搜寻树的每个节点，可以扩充资讯，例如子树的高度、节点总数、数字总和、数字最大值、数字最小值、……。

排名（Ranking）

二元搜寻树虽然有排序的功效，但是却没有排名的功效。想要排名，就要在每个节点新增一个变数，记录其子树的节点个数。不影响时间複杂度与空间複杂度。

找到第 k 名的节点：方向从根往叶，取得左小孩的节点个数，判断第 k 名位于左子树还是右子树。时间複杂度等同于二元搜寻树的高度。

找到节点是第几名：方向从叶往根，累计左子树的节点个数，判断当前节点是左小孩或右小孩以决定是否累计。时间複杂度等同于二元搜寻树的高度。

UVa 10909

二进位数字表示法

二进位数字一一对应到二元搜寻树的节点。

如此就能以阵列实作二元搜寻树。优点是程式码简洁，效率高，缺点是浪费记忆体空间、树的高度受限制。

UVa 712

AVL Tree

http://www.qmatica.com/DataStructures/Trees/AVL/AVLTree.html

平衡二元搜寻树。树上每个节点（每棵子树），其左右两子树的高度差最多为一。此举造成整棵树的高度为 O(logN)，让各项操作稳定运行，不会产生忽快忽慢的极端现象。

每当插入节点，高度差超过一，就马上运用右旋转或左旋转调整高度；旋转一至两次，就使整棵树平衡。旋转不影响排序。

找到最深、高度差超过一的节点（子树），依据插入节点的路线，可分为四类情况。左左/右右：旋转子树树根，立即平衡。左右/右左：先旋转子树树根的左/右小孩，成为左左/右右，后续同前。

删除节点则是反过来做。

插入、删除、搜寻的时间複杂度为 O(logN)。旋转、平衡的时间複杂度是 O(1)，至于空间複杂度仍是 O(N)。

UVa 11688

Red-Black Tree

红黑树的功效等同平衡二元搜寻树，但是效率更胜一筹。

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

可以直接使用 STL 的 set、map，但是没有排名功能。

Splay Tree

splay 是按照规则，把一个节点不断双旋至根。插入、删除之后立即 splay，儘管树没有完全平衡，插入、删除的均摊时间複杂度是 O(logN)。

splay 改为单旋，均摊时间複杂度并非 O(logN)，却是个不错的偷懒方式。

运用 splay 拆接子树，时间複杂度是 O(logN)，是主要特色。

排序资料结构: Multi-way Search Tree 系列

B-Tree

Binary Tree 再进化！一个节点改为储存大量数字和分枝，以符合传输通道大小、减少传输次数。适用“每次读取需要很多准备时间、一次可以读取一连串资料”的设备，例如硬碟、网路资料库。

一笔异地资料，存取时间约是计算时间的一千倍！此时我们关心存取时间（存取次数），不太关心计算时间（时间複杂度）。儘管 B-Tree 的搜寻、插入、删除远比 Binary Tree 冗长，但是 B-Tree 存取节点的次数较少！是 External Memory Algorithm 的经典范例。

网路已有详细的教学和动画，请读者自行搜寻。

一、一个节点，可储存 m 个分枝、m-1 个数字。
二、一个节点，数字由小到大，循序储存。
三、所有树叶，位于同一层。
四、小孩数量等于数字数量加一。（排除树叶）
五、小孩数量上下限是[ceil(m/2) , m]。（排除树叶）
六、树根不考虑小孩数量上下限。

插入、删除过程繁複，动用许多节点。后来又发明了 B⁺-Tree 与 B*-Tree，尽可能直接编辑邻近节点，避免新增、删除、搬移节点。

(a,b)-Tree

最少 a 个小孩，最多 b 个小孩。详细内容请自行搜寻。

排序资料结构: Skip Lists

Skip Lists

http://en.wikipedia.org/wiki/Skip_list

置放大量数字并进行排序的资料结构。不用树状结构，而改用高度不同的 List 来连接资料。资料结构在概念上可以表示成 Left Child-Right Sibling Binary Tree 的模式。是 Cache-oblivious Algorithm 的经典范例。

时间複杂度与空间複杂度与 Binary Search Tree 皆相同，但是实际运作效率比 Binary Search Tree 还要好。

极值资料结构: Heap 系列

Priority Queue

置放大量数字，可以随时添加数字、随时取出极值（最小值、最大值，只能选一种）的资料结构，泛称 Priority Queue。

泛称是用来凸显资料结构的功能。有了这样的泛称，当遇到的问题隐含著 queue 与 sort 的概念，就能直觉联想到 Priority Queue 资料结构，而不会被 Heap、Search Tree 这种不直觉的名称困住了思考。

极值是排序的特例

Heap    Search Tree
-------------------------
push    insert
pop     extremum + delete
peek    extremum
merge   merge

Heap 的每一项操作，都能用 Search Tree 兜出来，时间複杂度完全一样，唯一的例外是：Heap 预先偷看极值，仅需 O(1) 时间；Search Tree 则需 O(logN) 时间来搜寻极值。

如果在 push 和 pop 之时，随时记录极值，Search Tree 还是能快速偷看极值。

Binary 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 功效相同，据说简单很多。因为课本没教而乏人问津。

https://cs.uwaterloo.ca/~tmchan/heap.ps

Treap

Binary Search Tree 与 Binary Heap 进行合体术。

令数字拥有额外的次序，同时具有“排次序”与“求极值”的功能。树根的次序介于左右子树，树根的数字小于等于左右子树。

具备排名功效的 Binary Search Tree，可以用来代替 Treap。

极值资料结构: van Emde Boas Tree

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 不能动态排序罢了。

若要作为 Double Ended Priority Queue，则在每个节点加上两个变数，记录该子树目前拥有的数字的大小范围。