差異重量平衡樹和高度平衡樹

Question

可以解釋一下重量平衡樹和高度平衡樹有什麼不同。

AVL是平衡重樹

Answer 1

高度平衡二叉搜索樹需要左，右子樹的高度最多由一個不同。權重平衡二叉搜索樹要求左右二叉搜索樹中的節點數相差最多一個。

請記住，高度不同於節點的數量。根據定義，高度是樹中最長的路徑。

例如， 如果我們有一個高度平衡的BST，如果左子樹的高度與右邊的高度相差最多爲1，那麼它將被平衡。由於高度沒有指定僅節點的數量最長路徑，這意味着左側和右側子樹中的節點數可以相差超過1.

通用規則 權重均衡BST - 使用左右子樹中的節點數量進行平衡。 高度平衡BST - 使用左右子樹的高度來平衡。

注： AVL是一種高度平衡樹。