2-3 樹/紅黑樹(red-black tree)
2-3 tree
2-3樹節點 :
- null節點,null節點到根節點的距離都是相同的,所以2-3數是平衡樹
- 2叉節點,有兩個分樹,節點中有一個元素,左樹元素更小,右樹元素節點更大
- 3叉節點,有三個子樹,節點中有兩個元素,左樹元素更小,右樹元素更大,中間樹介於兩個父元素之間。
Line"/> 插入操作如下圖所示
紅黑樹
紅黑樹可以理解為實現了2-3樹的BST(binary search tree),它是一個自平衡樹,保證在最壞的情況下的操作也是O(lg(n))
特性:- 每個節點有一個顏色屬性(紅或黑)
- 根節點是黑色的
- 所有的null節點都是黑色的,從任何null節點到根節點所經過的黑色節點數目相同
查詢操作與BST是相同的
插入規則如下:
- 按BST的插入方法在null節點上建立新節點,新節點的顏色為 紅色
- 如果有右子節點為紅色,則 左旋 ,右子節點變為父節點
- 如果左子節點與左孫節點都為紅色,則進行 右旋 ,左位元組的變為父節點
- 如果兩個節點的顏色都為紅色,則 翻轉反色
操作流程如下圖所示:
- 圖左 為插入節點c,先標記為紅,因為a、c都為紅節點,故 顏色反轉
- 中間 插入節點a,由於插入後a、b節點都為紅色,按第3條規則需要進行 右旋 操作,b變成了新的父節點
- 圖右 插入節點b,由於b在a的右邊,故先進行 左旋 ,然後又發現a、b同為紅色,再進行 右旋
左旋:
左圖為左旋前,右圖為左旋後,程式碼如下所示:
private Node rotateRight(Node h){ assert isRed(h.right); Node x = h.right;// 複製h的 右子樹 為節點x h.right = x.left;// 將x的左子樹移動到h的右節點上(替代) x.left = h;// 將修改後的h節點作為x的左節點(替代) x.color = h.color;// x繼承h的顏色 h.color = RED;// 將h節點的顏色設定為紅色 return x;// 返回x節點作為新的父節點 }
右旋操作與之類似
顏色反轉:
左圖為顏色翻轉前,右圖為操作之後,程式碼如下所示:
private void flipColors(Node h){ assert !isRed(h); assert isRed(h.left); assert isRed(h.right); h.color = RED;// 將父節點顏色改為紅色 h.left.color = BLACK;// 將左右子節點顏色改為黑色, h.right.color = BLACK; }
此處只實現了查詢與插入,如要完整實現所有功能(還有刪除),可以採用 ofollow,noindex" target="_blank">左傾紅黑樹 (LLRB, Left-leaning red–black tree)
紅黑樹顯示的 demo