該書中先介紹了2-3查找樹,然后引入了紅黑樹,得到了和大部分書籍中定義不同的紅黑樹。即改進2-3樹,將3-結點表示為由一條左斜的紅色鏈接相連的兩個2-結點。具體定義如下:
1.紅鏈接均為左鏈接
2.沒有任何一個結點同時和兩條紅鏈接相連
3.任意空鏈接到根結點的路徑上的黑鏈接數量相同
其中2,3條容易理解,能和紅黑樹定義對應的上,但是第一條為什么紅鏈接只能是左鏈接,我感覺有右的紅鏈接存在也不影響紅黑樹的時間復雜度,求解釋
uj5u.com熱心網友回復:
同問,樓主明白了嗎?轉載請註明出處,本文鏈接:https://www.uj5u.com/houduan/247765.html
標籤:C++ 語言
上一篇:新手請教一下多載運算子
下一篇:Qt 實作甘特圖
