AVL树：如何做索引访问？

我在AVL Tree Wikipedia page注意到以下注释：AVL树：如何做索引访问？

“如果每个节点还记录其子树（包括本身和它的后代）的大小，则该节点可以通过指数为O检索（log n）的时间作为好。”

我有谷歌，发现少数地方提accessing by index，但似乎无法找到一个算法会写的说明。

非常感谢

[更新]谢谢大家。如果发现@templatetypedef与@一个答案结合user448810 links以特别帮助。特别是这个snipit：

“这两个函数的关键是，一个节点的索引是它左边的孩子的大小，只要我们通过它的左边孩子下降一棵树，我们只需要索引但是当我们必须通过右边的孩子向下移动树时，我们必须调整大小以包含我们排除的树的一半。“

因为我的实现是不可变的，我并不需要做任何额外的工作重新平衡时，每个节点计算它的建筑规模（相同链接的方案IMPL）

我最终实现结束了：

class Node<K,V> implements AVLTree<K,V> { ... 
    public V index(int i) { 
     if (left.size() == i) return value; 
     if (i < left.size()) return left.index(i); 
     return right.index(i - left.size() - 1); 
    } 
} 

class Empty<K,V> implements AVLTree<K,V> { ... 
    public V index(int i) { throw new IndexOutOfBoundsException();} 
}

这与其他实现方式略有不同，让我知道，如果你认为我有一个错误！

来源

2012-06-08 Daniel Worthington-Bodart

这种结构背后的总体思想是利用现有的BST，并通过存储在左子树的节点的数目增加每个节点。一旦你做到了这一点，你可以看一下第n个节点的树通过以下递归算法：

要查找的第n个元素的BST其根节点在其左子树k个元素：
- 若k = n时，返回根节点（因为这是树中的第零节点）
- 如果n ≤ K，递归地查找该第n个元素的左子树。
- 否则，查找第（n - K - 1）个元件在右子树。

这需要时间O（h）中，其中h是树的高度。在AVL树中，这个O（log n）。在CLRS，这种结构被探索应用于红/黑树，他们称这种树为“订单统计树”。

在树轮旋转过程中，您必须添加一些额外的逻辑来调整左子树中缓存的元素数量，但这并不是特别困难。

希望这会有所帮助！

来源

2012-06-08 21:04:35 templatetypedef

尽管我同意这是做事的正确方式，但它似乎并不像维基页面所涵盖的那样相同（它存储了整个子树的大小，而不是左子树）。他们正在做的事情（显然）需要一点点笨拙，通过减去右子树的大小或查看左子树来获得左子树的大小以找到它的大小。 –

@ JerryCoffin-我已经勾画出的方法与此方法相关。如果每个子树存储它的总大小，我可以通过查看左边孩子的总大小来查找左边子树的大小（如果有的话）。这两种方法基本上是同构的。 – templatetypedef

然而，我想再看看他们的系统有一个优势：它支持从任何一端进行索引，因此从集合的末尾对N进行索引就像从一开始就一样简单。 –

AVL树：如何做索引访问？

回答

相关问题