資料結構中的重量傾向左傾樹

這裡我們將介紹左傾樹的另一種變體。這裡我們將考慮子樹中的節點數，而不是從根到外部節點的最短路徑長度。這裡我們將定義節點 x 的權重 w(x)，即以 x 為根的子樹中內部節點的數目。如果 x 是外部節點，那麼權重為 0。如果 x 是內部節點，那麼權重將比其子節點權重的總和多 1。

以下是一個重量傾向左傾樹 (WBLT) 的示例−

假設二叉樹如下−

如果我們計算每個節點的 w(x) 值，它將如下−

現在 WBLT 的定義如下−

如果且僅當樹中每個內部節點的左子節點的 w(x) 大於或等於右子節點的 w(x)，那麼一棵二叉樹稱為重量平衡左傾樹。最大 (最小) WBLT 是一棵最大 (最小) 樹，同時也是一棵 WBLT。

更新日期：2020-08-11

1000+ 瀏覽量

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告