使用 AVL 树的缺点是什么？
What is the downside to using an AVL tree?
在我看来，AVL 树总是比 BST 更有效。那么为什么人们仍然使用 BST？ AVL 实施是否会产生成本？
AVL 树与 Red-Black 树或 2-3 树或普通 BST 等其他树相比有其优点和缺点。
AVL 树：
优势：
- 简单。相当容易编码和理解
- 额外存储：相当小，每个节点 2 位（用于存储 +1,0,-1）。还有一个
通过使用 children 可以在每个节点使用 1 位的技巧
一位。
- 用于查找的常量（查找您最喜欢的
分析书：Knuth等）为1.5
（所以 1.5 日志）。 Red-Black 树的常量为 2（因此 2*log(n) 用于查找）。
缺点：
- 删除为 expensive-ish。删除一个节点仍然是对数，但是你可能要"rotate"一直到树的根。换句话说，一个更大的常数。 Red-Black 树木只需旋转 1 次。
- 编码不简单。他们大概是树家族的"simplist"，但是还是有很多or corner cases。
如果您希望对数据进行排序，则 BST 会转化为链表。但是，如果您希望您的数据相当随机，"on average"，您对 BST 的所有操作（查找、删除、插入）都将是对数的。编写 BST 非常容易：AVL 树虽然编写起来相当简单，但有很多极端情况，测试可能很棘手。
总而言之，普通的二叉搜索树很容易编码并且正确，如果您的数据相当随机，应该表现得很好（平均而言，所有操作都是对数的）。 AVL Tree 更难编码，但可以保证对数性能，代价是一些额外的 space 和更复杂的代码。
在我看来，AVL 树总是比 BST 更有效。那么为什么人们仍然使用 BST？ AVL 实施是否会产生成本？
AVL 树与 Red-Black 树或 2-3 树或普通 BST 等其他树相比有其优点和缺点。
AVL 树：
优势：
- 简单。相当容易编码和理解
- 额外存储：相当小，每个节点 2 位（用于存储 +1,0,-1）。还有一个 通过使用 children 可以在每个节点使用 1 位的技巧 一位。
- 用于查找的常量（查找您最喜欢的 分析书：Knuth等）为1.5 （所以 1.5 日志）。 Red-Black 树的常量为 2（因此 2*log(n) 用于查找）。
缺点：
- 删除为 expensive-ish。删除一个节点仍然是对数，但是你可能要"rotate"一直到树的根。换句话说，一个更大的常数。 Red-Black 树木只需旋转 1 次。
- 编码不简单。他们大概是树家族的"simplist"，但是还是有很多or corner cases。
如果您希望对数据进行排序，则 BST 会转化为链表。但是，如果您希望您的数据相当随机，"on average"，您对 BST 的所有操作（查找、删除、插入）都将是对数的。编写 BST 非常容易：AVL 树虽然编写起来相当简单，但有很多极端情况，测试可能很棘手。
总而言之，普通的二叉搜索树很容易编码并且正确，如果您的数据相当随机，应该表现得很好（平均而言，所有操作都是对数的）。 AVL Tree 更难编码，但可以保证对数性能，代价是一些额外的 space 和更复杂的代码。