BST
二叉查找樹（Binary Search Tree，簡(jiǎn)稱BST）是一棵二叉樹，它的左子節(jié)點(diǎn)的值比父節(jié)點(diǎn)的值要小，右節(jié)點(diǎn)的值要比父節(jié)點(diǎn)的值大。它的高度決定了它的查找效率。
在理想的情況下，二叉查找樹增刪查改的時(shí)間復(fù)雜度為O(logN)（其中N為節(jié)點(diǎn)數(shù)），最壞的情況下為O(N)。當(dāng)它的高度為logN+1時(shí)，我們就說二叉查找樹是平衡的。
BST存在的問題
BST存在的主要問題是，數(shù)在插入的時(shí)候會(huì)導(dǎo)致樹傾斜，不同的插入順序會(huì)導(dǎo)致樹的高度不一樣，而樹的高度直接的影響了樹的查找效率。理想的高度是logN，最壞的情況是所有的節(jié)點(diǎn)都在一條斜線上，這樣的樹的高度為N。
RBTree
基于BST存在的問題，一種新的樹——平衡二叉查找樹(Balanced BST)產(chǎn)生了。平衡樹在插入和刪除的時(shí)候，會(huì)通過旋轉(zhuǎn)操作將高度保持在logN。其中兩款具有代表性的平衡樹分別為AVL樹和紅黑樹。AVL樹由于實(shí)現(xiàn)比較復(fù)雜，而且插入和刪除性能差，在實(shí)際環(huán)境下的應(yīng)用不如紅黑樹。
RBTree的定義
RBTree的定義如下:
- 1.任何一個(gè)節(jié)點(diǎn)都有顏色，黑色或者紅色
- 2.根節(jié)點(diǎn)是黑色的
- 3.父子節(jié)點(diǎn)之間不能出現(xiàn)兩個(gè)連續(xù)的紅節(jié)點(diǎn)
- 4.任何一個(gè)節(jié)點(diǎn)向下遍歷到其子孫的葉子節(jié)點(diǎn)，所經(jīng)過的黑節(jié)點(diǎn)個(gè)數(shù)必須相等
- 5.空節(jié)點(diǎn)被認(rèn)為是黑色的
class Node<T>{
public T value;
public Node<T> parent;
public boolean isRed;
public Node<T> left;
public Node<T> right;
}
作為平衡二叉查找樹里面眾多的實(shí)現(xiàn)之一，紅黑樹無疑是最簡(jiǎn)潔、實(shí)現(xiàn)最為簡(jiǎn)單的。紅黑樹通過引入顏色的概念，通過顏色這個(gè)約束條件的使用來保持樹的高度平衡。作為平衡二叉查找樹，旋轉(zhuǎn)是一個(gè)必不可少的操作。通過旋轉(zhuǎn)可以降低樹的高度，在紅黑樹里面還可以轉(zhuǎn)換顏色。
紅黑樹里面的插入和刪除的操作比較難理解，這時(shí)要注意記住一點(diǎn)：操作之前紅黑樹是平衡的，顏色是符合定義的。在操作的時(shí)候就需要向兄弟節(jié)點(diǎn)、父節(jié)點(diǎn)、侄子節(jié)點(diǎn)借調(diào)和互換顏色，要達(dá)到這個(gè)目的，就需要不斷的進(jìn)行旋轉(zhuǎn)。所以紅黑樹的插入刪除操作需要不停的旋轉(zhuǎn)，一旦借調(diào)了別的節(jié)點(diǎn)，刪除和插入的節(jié)點(diǎn)就會(huì)達(dá)到局部的平衡（局部符合紅黑樹的定義），但是被借調(diào)的節(jié)點(diǎn)就不會(huì)平衡了，這時(shí)就需要以被借調(diào)的節(jié)點(diǎn)為起點(diǎn)繼續(xù)進(jìn)行調(diào)整，直到整棵樹都是平衡的。在整個(gè)修復(fù)的過程中，插入具體的分為3種情況，刪除分為4種情況。
整個(gè)紅黑樹的查找，插入和刪除都是O(logN)的，原因就是整個(gè)紅黑樹的高度是logN，查找從根到葉，走過的路徑是樹的高度，刪除和插入操作是從葉到根的，所以經(jīng)過的路徑都是logN。
