一、 二叉查找樹
二叉查找樹就是以二分法思想為指導，設計出來的一種快速查找樹，二叉查找樹保證以下特性：
每一個節點關鍵字隻會在樹中出現一次。
任何一個節點，如果它有子節點，那麼左側的關鍵字一定比較小，右側的關鍵字一定比較大。
基于這種結構，搜尋時每次從根節點開始查找，就算找到葉子結點，也隻進行了log2n次比較，效率明顯高于順序/倒序周遊。
二、 平衡二叉樹（AVL樹）
極端情況下的二叉查找樹可能隻有左子樹，進而退化為連結清單結構。為應對這種情況，引入了平衡二叉樹：
它是一個空樹或二叉查找樹
左右兩個子樹的高度差的絕對值不超過1
左右兩個子樹都是一顆平衡二叉樹
平衡二叉樹的查找時間複雜度不會超過O(log2n)，平衡二叉樹在做插入或删除的時候，需要通過一系列的旋轉（左旋、右旋）操作（自平衡），讓其始終滿足平衡二叉樹的條件。
三、2-3樹
一顆2-3樹或為一顆空樹，或有以下節點組成：
2-節點，含有一個元素和兩個子樹（左右子樹），左子樹所有元素的值均小于它父節點，右子樹所有元素的值均大于它父節點；
3-節點，還有兩個元素和三個子樹（左中右子樹），左子樹所有元素的值均小于它父節點，中子樹所有元素的值都位于父節點兩個元素之間，右子樹所有元素的值均大于它父節點；
子樹也是空樹、2-節點或者3-節點；
沒有元素相等的節點。
2-3樹能夠保證在插入元素之後，樹依然保持平衡狀态，它的最壞情況下所有子節點都是2-節點，樹的高度為lgN，相比于我們普通的二叉查找樹，最壞的情況下樹的高度為N，确實保證了最壞情況下的時間複雜度，但是2-3樹實作起來過于複雜，是以我們經常使用一種使用2-3樹思想進行簡單實作的紅黑樹來替代。
四、 紅黑樹
紅黑樹主要是對2-3樹進行編碼，紅黑樹的基本思想是用标準的二叉查找樹（完全由2-節點構成）和一些額外的資訊（替換3-節點）來表示2-3樹。我們将樹的連結分為兩種：
紅連結：将兩個2-節點連接配接起來構成一個3-節點。
黑連結：是2-3樹中的普通連結。
确切的說，3-節點表示為由一條左斜紅色連結相連的兩個2-節點。這種表示法的一個優點是，我們無需修改就可以直接使用标準的二叉查找樹的get方法。
紅黑樹也是一種自平衡二叉樹，但在統計上，它的性能要優于平衡二叉樹。
1) 節點是紅色或者黑色
2) 根節點是黑色
3) 每個葉子結點(NIL節點，虛拟的外部空節點，不真實存在)為黑色
4) 每個紅色節點的兩個子節點都是黑色
5) 從任一節點到其每個葉子結點的所有路徑都包含相同數目的黑色節點。
根據這些性質，可以得出推論：從根到葉子的最長距離，不超過最短距離的兩倍。 因為性質5限制了左支和右支黑色節點數目一定相等，性質4又限制了不會有兩個相鄰的紅色節點，最長路徑為紅黑相間的節點序列，紅色節點數最多為黑色節點數-1，是以紅色+黑色<黑色*2。
對紅黑樹進行增删操作，會是樹結構違背這些性質，是以像平衡二叉樹一樣需要在插入時進行自平衡操作。
紅黑樹的節點除了和其它二叉樹一樣的left/right/parent節點外，還有顔色red/black屬性和是否為葉子節點标記isNil。
由于性質5的限制，所有新插入的節點，都是紅色節點，假設插入節點為N，父節點為P，祖父節點為G，叔節點為U，定義一個函數f(A,B)，函數傳回A節點相對B節點的位置（left/right）。
1) 如果該樹為空樹，那麼N節點為根節點，根據性質2變色為黑。
2) 如果P為黑色，那麼新增節點為紅色，不會違背性質5，滿足紅黑樹性質，不做任何操作。
3) 如果P為紅色，那麼分多種子情況：
U為紅色，把P、U改為黑色、G改為紅色。G改為紅色後，由于G的父節點也可能是紅色，進而違背性質4，這時把G節點視為新插入的節點，遞歸進行插入操作。
U為黑色，且f(P,G)=f(N,P)，則将P、G變色，對G為根節點的樹做單向旋轉（f(P,G)=L則LL右旋轉，為R則RR左旋轉），旋轉是為了保證子樹上黑色節點總數一緻。
U為黑色，且f(P,G)!=f(N,P)，對P進行一次單向旋轉，轉化為f(P,G)=f(P,N)情況。
總結：紅黑樹的插入過程主要操作有兩種。
變色，用于調整兩個紅色節點相鄰的情況，以适應性質4
旋轉，用于調整左右子樹黑色節點數目不等的情況，以适應情況5
通過"數學歸納法"開始論證高度為h的紅黑樹，它的包含的内節點個數至少為 2bh(x)-1個"。
(01) 當樹的高度h=0時，
内節點個數是0，bh(x) 為0，2bh(x)-1 也為 0。顯然，原命題成立。
(02) 當h>0，且樹的高度為 h-1 時，它包含的節點個數至少為 2bh(x)-1-1。這個是根據(01)推斷出來的！
下面，由樹的高度為 h-1 的已知條件推出“樹的高度為 h 時，它所包含的節點樹為 2bh(x)-1”。
當樹的高度為 h 時，
對于節點x(x為根節點)，其黑高度為bh(x)。
對于節點x的左右子樹，它們黑高度為 bh(x) 或者 bh(x)-1。
根據(02)的已知條件，我們已知 "x的左右子樹，即高度為 h-1 的節點，它包含的節點至少為 2bh(x)-1-1 個"；
是以，節點x所包含的節點至少為 ( 2bh(x)-1-1 ) + ( 2bh(x)-1-1 ) + 1 = 2^bh(x)-1。即節點x所包含的節點至少為 2bh(x)-1。
是以，原命題成立。
由(01)、(02)得出，"高度為h的紅黑樹，它的包含的内節點個數至少為 2^bh(x)-1個"。
是以，“一棵含有n個節點的紅黑樹的高度至多為2log(n+1)”。
結論
紅黑樹的時間複雜度為: O(lgn)
紅黑樹在HashMap中的應用
1) treeifyBin方法
當table容量小于最小建樹容量64時，調整table大小。最小建樹容量的意義在于，重新規劃table大小和樹化某個哈希桶（哈希值對應下标的容器），都可以提高查詢效率。這裡取一個經驗數字64作為衡量，當table容量超過64，調用TreeNode.treeify方法把連結清單轉化為紅黑樹。
2) putTreeVal方法
執行二叉樹查找，每一次都比較目前節點和待插入節點大小，如果帶插入節點較小，那麼從目前節點左子樹查找，否則從右子樹查找，這種查詢效率等同于二分法，時間複雜度為O(log2n),待找到空位可以存放節點值之後，執行兩個方法。
balanceInsertion(root,x)，平衡插入，一方面把節點插入紅黑樹中，一方面對紅黑樹進行變換使之平衡。
moveRootToFront(table, root)由于紅黑樹重新平衡之後，root節點可能發生了變化，table裡記錄的節點不再是紅黑樹的root，需要重置。
3) balanceInsertion方法
此方法即上邊插入分析的代碼實作。
4) rotateLeft和rotateRight方法
左旋與右旋，改變節點左右子樹引用即可實作。