差异重量平衡树和高度平衡树

Question

可以解释一下重量平衡树和高度平衡树有什么不同。

AVL是平衡重树

Answer 1

高度平衡二叉搜索树需要左，右子树的高度最多由一个不同。权重平衡二叉搜索树要求左右二叉搜索树中的节点数相差最多一个。

请记住，高度不同于节点的数量。根据定义，高度是树中最长的路径。

例如， 如果我们有一个高度平衡的BST，如果左子树的高度与右边的高度相差最多为1，那么它将被平衡。由于高度没有指定仅节点的数量最长路径，这意味着左侧和右侧子树中的节点数可以相差超过1.

通用规则 权重均衡BST - 使用左右子树中的节点数量进行平衡。 高度平衡BST - 使用左右子树的高度来平衡。

注： AVL是一种高度平衡树。