c++ - 使用 AVL 树的缺点是什么？

Question

<分区>

Answer 1

AVL 树与红黑树或 2-3 树或普通 BST 等其他树相比有其优点和缺点。

AVL 树:

优点:

1. 简单。相当容易编码和理解
2. 额外存储:相当小，每个节点 2 位(用于存储 +1,0,-1)。还有一个 通过使用您的 child 的，您可以在每个节点使用 1 位的技巧 一位。
3. 查找常量(查找您最喜欢的 分析书:Knuth等)为1.5 (所以 1.5 日志)。红黑树的常数为 2(因此 2*log(n) 用于查找)。

缺点:

1. 删除是昂贵的。删除一个节点仍然是对数，但是你可能要一直“旋转”到树的根部。换句话说，一个更大的常数。红黑树只需旋转 1 次。
2. 编码不简单。它们可能是树家族中的“极简主义者”，但仍然有很多或角落案例。

如果您希望对数据进行排序，则 BST 会转化为链表。但是如果你希望你的数据是相当随机的，“平均而言”，你对 BST 的所有操作(查找、删除、插入)都将是对数的。编写 BST 非常容易:AVL 树虽然编写起来相当简单，但有很多极端情况，测试可能很棘手。

总而言之，普通的二叉搜索树很容易编码并且正确，如果您的数据相当随机，应该表现得很好(平均而言，所有操作都是对数的)。 AVL Tree 更难编码，但以一些额外的空间和更复杂的代码为代价保证了对数性能。