BST
二叉查找樹（Binary Search Tree掩宜，簡稱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í)候會導(dǎo)致樹傾斜宠纯，不同的插入順序會導(dǎo)致樹的高度不一樣，而樹的高度直接的影響了樹的查找效率层释。理想的高度是logN婆瓜，最壞的情況是所有的節(jié)點(diǎn)都在一條斜線上，這樣的樹的高度為N。
RBTree
基于BST存在的問題廉白，一種新的樹——平衡二叉查找樹(Balanced BST)產(chǎn)生了个初。平衡樹在插入和刪除的時(shí)候，會通過旋轉(zhuǎn)操作將高度保持在logN猴蹂。其中兩款具有代表性的平衡樹分別為AVL樹和紅黑樹院溺。AVL樹由于實(shí)現(xiàn)比較復(fù)雜，而且插入和刪除性能差磅轻，在實(shí)際環(huán)境下的應(yīng)用不如紅黑樹珍逸。
RBTree的定義
RBTree的定義如下:
- 1.任何一個節(jié)點(diǎn)都有顏色，黑色或者紅色
- 2.根節(jié)點(diǎn)是黑色的
- 3.父子節(jié)點(diǎn)之間不能出現(xiàn)兩個連續(xù)的紅節(jié)點(diǎn)
- 4.任何一個節(jié)點(diǎn)向下遍歷到其子孫的葉子節(jié)點(diǎn)聋溜，所經(jīng)過的黑節(jié)點(diǎn)個數(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)之一谆膳，紅黑樹無疑是最簡潔、實(shí)現(xiàn)最為簡單的撮躁。紅黑樹通過引入顏色的概念漱病，通過顏色這個約束條件的使用來保持樹的高度平衡。作為平衡二叉查找樹把曼，旋轉(zhuǎn)是一個必不可少的操作杨帽。通過旋轉(zhuǎn)可以降低樹的高度，在紅黑樹里面還可以轉(zhuǎn)換顏色祝迂。
紅黑樹里面的插入和刪除的操作比較難理解睦尽，這時(shí)要注意記住一點(diǎn)：操作之前紅黑樹是平衡的，顏色是符合定義的型雳。在操作的時(shí)候就需要向兄弟節(jié)點(diǎn)、父節(jié)點(diǎn)山害、侄子節(jié)點(diǎn)借調(diào)和互換顏色纠俭，要達(dá)到這個目的，就需要不斷的進(jìn)行旋轉(zhuǎn)浪慌。所以紅黑樹的插入刪除操作需要不停的旋轉(zhuǎn)冤荆，一旦借調(diào)了別的節(jié)點(diǎn)，刪除和插入的節(jié)點(diǎn)就會達(dá)到局部的平衡（局部符合紅黑樹的定義）权纤，但是被借調(diào)的節(jié)點(diǎn)就不會平衡了钓简，這時(shí)就需要以被借調(diào)的節(jié)點(diǎn)為起點(diǎn)繼續(xù)進(jìn)行調(diào)整，直到整棵樹都是平衡的汹想。在整個修復(fù)的過程中外邓，插入具體的分為3種情況，刪除分為4種情況古掏。
整個紅黑樹的查找损话，插入和刪除都是O(logN)的，原因就是整個紅黑樹的高度是logN，查找從根到葉丧枪，走過的路徑是樹的高度光涂，刪除和插入操作是從葉到根的，所以經(jīng)過的路徑都是logN拧烦。
