data-structures - 自平衡树或小高度树结构如何帮助高效列表和抽象数据结构

Question

我正在阅读有关 AVL 树的信息，并在那里重定向到自平衡树，我读到了

在计算机科学中，自平衡（或高度平衡）二叉搜索树是任何基于节点的二叉搜索树，它在面对任意项目插入和删除时自动保持其高度（根以下的最大层数）较小。1

这些结构为可变有序列表提供了有效的实现，并可用于其他抽象数据结构，例如关联数组、优先级队列和集合。

我很困惑

1. 高度与列表有什么关系？大批？
2. 小高度树如何为可变有序列表提供有效的实现？大批？排队？
3. 假设列表的节点或数组的索引是列表或数组的高度，它怎么会小？

Answer 1

这是平衡 2 的视觉效果。请记住，树为每个节点提供了唯一的路径。因为 AVL 树是二叉搜索树，所以我们“知道”给定值时要走的方向，因为树是排序的。AVL 树（对于每个节点，左右子树的高度最多相差 1）允许快速搜索和插入，通常是 log N，因为它可以在恒定时间内旋转和操纵自身。我们可以将有序列表、队列等值实现为树结构以利用其特性。关键是保持平衡的树（保持水平而不是垂直，这是通过遵循二叉搜索树特征来实现的）。

你能详细说明1和3吗？