參考資料:資料結構 - 常見的樹
紅黑樹:
紅黑樹是一種近似平衡的二叉查找樹,它能夠確定任何一個節點的左右子樹的高度差不會超過二者中較低那個的一陪。具體來說,紅黑樹是滿足如下條件的二叉查找樹(binary search tree):
- 每個節點要麼是紅色,要麼是黑色。
- 根節點必須是黑色
- 紅色節點不能連續(也即是,紅色節點的孩子和父親都不能是紅色)。
- 對于每個節點,從該點至null(樹尾端)的任何路徑,都含有相同個數的黑色節點
左旋:
右旋:
後繼:
- t的右子樹不空,則t的後繼是其右子樹中最小的那個元素。
- t的右孩子為空,則t的後繼是其第一個向左走的祖先。