热门问题
时间线
聊天
视角
左傾紅黑樹
来自维基百科,自由的百科全书
Remove ads
左傾紅黑樹(英語:Left-leaning red–black tree,縮寫:LLRB)是一種類型的自平衡二元搜尋樹。它是紅黑樹的變體,並保證對操作相同漸近的複雜性,但被設計成更容易實現。[1]
![]() |
左傾紅黑樹(LLRB) 是 Robert Sedgewick 在 〈Left-Leaning Red-Black Trees〉(2008) 一文中提出,其核心理念是強制所有紅邊只能出現在左邊,透過這個限制,把原本需要處理的對稱情況「砍掉一半」,以此簡化紅黑樹的實作複雜度,但仍保有與 2–3 樹等價的平衡性
Remove ads
特性
左傾紅黑樹(Left-Leaning Red-Black Tree, LLRB)滿足紅黑樹的所有性質:
- 每個節點不是紅色就是黑色。
- NIL 節點(空節點)視為黑色。
- 紅色節點不能有紅色子節點(即不能連續紅)。
- 從任一節點到其所有後代 NIL 節點的所有路徑,都經過相同數量的黑色節點。
- 根節點依慣例視為黑色。
此外,左傾性質(left-leaning property)還規定:
- 如果一個節點只有一個紅色子節點,這個紅色子節點必須是左子節點。
左傾性質的好處是:能減少實作搜尋樹操作時需要考慮的情況數量,讓實作更簡單。
與 2-3 樹和 2-3-4 樹的關係
LLRB(左傾紅黑樹)與 2–3–4 樹是同構的(isomorphic)。 與傳統紅黑樹不同的是,LLRB 強制 所有 3-node 都向左傾,因此 LLRB 與 2–3–4 樹之間存在一對一的對應關係。 這表示:每一棵 LLRB 樹,都唯一對應到一棵 2–3–4 樹,反之亦然。
如果再額外加上一條限制:任一節點不得同時有兩個紅色子節點,那麼 LLRB 樹就會變得與 2–3 樹同構,因為這個限制會禁止 4-node 的存在。
分析
所有已提出的紅黑樹演算法,其特點都是: 在含有 N 個鍵的樹中,最壞情況的搜尋時間會被限制在某個小常數倍的 log N。 而實際觀察到的效能表現,通常也比這個最壞界限快上相同的倍數,接近一棵完全平衡樹(perfectly balanced tree)中 log N 的理論最佳節點訪問數。
- Robert Sedgewick. Left-leaning Red–Black Trees (頁面存檔備份,存於網際網路檔案館). Direct link to PDF (頁面存檔備份,存於網際網路檔案館).
- Robert Sedgewick. Left-Leaning Red–Black Trees (slides). Two versions:
- Linus Ek, Ola Holmström and Stevan Andjelkovic. May 19, 2009. Formalizing Arne Andersson trees and Left-leaning Red–Black trees in Agda (頁面存檔備份,存於網際網路檔案館)
- Julien Oster. March 22, 2011. An Agda implementation of deletion in Left-leaning Red–Black trees
- Kazu Yamamoto. 2011.10.19. Purely Functional Left-Leaning Red–Black Trees (頁面存檔備份,存於網際網路檔案館)
Remove ads
Remove ads
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads