热门问题
时间线
聊天
视角

左傾紅黑樹

来自维基百科,自由的百科全书

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 的理論最佳節點訪問數。

論文

Remove ads

實現

更多信息 作者, 時間 ...
Remove ads
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads