淺析樹結構之紅黑樹
首先先來了解一下紅黑樹的五個性質
- 每個結點非紅即黑。
- 根結點是黑的。
- 每個葉結點（這裡葉節點指的是NULL結點）都是黑的。
- 如果一個結點是紅的，那麼它的兩個兒子都是黑的。
- 對于任意結點而言，其到樹末端即NULL節點的每條路徑都包含相同數目的黑結點。
等等等,一臉懵逼吧?? 那還是先來了解一下2-3樹吧
2-3查找樹
2-3樹是一種樹型資料結構,内部節點(存在子節點的節點)分為兩種:
(1)2-節點, 有1個資料元素和2個孩子
(2)3-節點, 有2個資料元素和3個孩子
先來看一棵普通的2-3 查找樹到底長什麼樣?
由上圖可以知道, 對于2-3樹中任意一個節點,左右子樹的高度均相同,可見2-3樹是一棵絕對平衡的樹,所有空連結到根節點的距離都是相同的.
在一棵大小為N的2-3樹中,查找和插入操作通路的結點必然不超過lgN個
2-3樹的插入操作
2-3樹(并不是二叉查找樹)的插入操作與BST(二叉查找樹)的插入操作有很大的差別, BST的插入操作是先進行一次未命中的查找,然後再将節點插入到對應的空連結上.如果2-3樹也按照BST這樣進行插入,就破壞了絕對平衡.它采用的方式是将新節點插入到已經存在的葉子節點中.
根據葉子節點的類型不同,插入的處理方式也有所變化:
- 向2-節點中插入新鍵,直接将新節點合并到原來的節點上組成一個3-節點
淺析樹結構（三）紅黑樹淺析樹結構之紅黑樹 - 向一個父節點為2-節點的3-節點中插入新鍵(圖中插入4), 這時會産生一個臨時的4-節點, 需要将這個臨時的4-節點分裂為3個2-節點,并将中間的2-節點上移與其父節點合并成一個3-節點.
淺析樹結構（三）紅黑樹淺析樹結構之紅黑樹 - 向一個父節點為3-節點的3-節點中插入新鍵,這時會産生一個臨時的4-節點, 需要将這個臨時的4-節點分裂為3個2-節點,并将中間的2-節點上移與其父節點合并成一個臨時的4-節點, 繼續分裂上移,直到不再存在臨時的4-節點.
淺析樹結構（三）紅黑樹淺析樹結構之紅黑樹
為何不直接使用2-3樹
需要維護兩種不同類型的節點(2-節點,3-節點),兩種類型的節點在轉換,比較等很多情況都相當麻煩,實作代碼所産生的額外開銷可能會導緻算法比标準的二叉查找樹速度更慢. 是以我們不使用直接的2-3樹,而是使用更加優秀的紅黑樹 !
紅黑樹與2-3樹的等價性
紅黑樹是 2-3 查找樹，但它不需要分别定義 2- 節點和 3- 節點，而是在普通的二叉查找樹之上，為節點添加顔色。指向一個節點的連結顔色如果為紅色，那麼這個節點和上層節點表示的是一個 3- 節點，而黑色則是普通連結(2-節點)。
下圖左邊的2-3樹與右邊的紅黑樹是完全等價的.
2-節點等價于帶有黑色連結的節點
3-節點等價于帶有紅色連結的節點與上層節點的結合體 淺析樹結構（三）紅黑樹淺析樹結構之紅黑樹
紅黑樹的實作—點選連結
BST樹, AVL樹與紅黑樹性能總結:
對于完全随機的資料, 普通的二分搜尋樹很好用!
缺點: 極端情況退化為連結清單(或者高度不平衡)
對于查詢較多的使用情況,AVL樹很好用!
缺點: AVL樹每次插入删除會進行大量的平衡度計算,頻繁的插入删除使AVL樹性能變差
紅黑樹犧牲了平衡性(2logN的高度),但是其統計性能更優秀(綜合增删改查所有的操作)
基于紅黑樹實作的TreeMap和TreeSet
對TreeMap實作感興趣請點選這個連結------Java集合幹貨系列-（四）TreeMap源碼解析
對TreeSet實作感興趣請點選這個連結------TreeSet源碼分析
另外在Java8中HashMap的實作也使用了紅黑樹,具體分析請點選這個連結------紅黑樹在HashMap中的應用
淺析樹結構（一）二叉查找樹(BST樹代碼實作)
淺析樹結構（二）AVL平衡二叉樹(AVL樹原理及代碼實作)
淺析樹結構（三）紅黑樹