平衡二叉搜索树和二叉搜索树有什么区别？

Question

抱歉，如果这是一个非常基本的问题，但我对树还很陌生，因此，这个疑问这些天困扰着我。

二叉搜索树和平衡二叉搜索树有什么区别？不是每个 BST（二叉搜索树）都已经是 BBST（平衡 BST）了吗？

Answer 1

“平衡”是二叉树可能具有的属性。它通常意味着树中的每个节点在其下面的每个子树上具有大致相同数量的后代节点。更具体地说，它意味着树的“高度”已最小化。

对于非“平衡”的树，可能有一个二叉树，其中所有“左”子节点都为空，并且它仍然具有“二叉搜索树”的属性。这称为退化树，因为它在结构上更像链表，因此具有 O(N) 搜索时间而不是 O(log(N))。

Answer 2

区别在于平衡二叉树具有可能的最小高度

Answer 3

平衡二叉树是每个节点的左右子树高度相差不超过1的二叉树结构。