按序号索引红黑树访问 [英] Red-black tree access by ordinal index
本文介绍了按序号索引红黑树访问的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我有一个红黑树(二叉树,所有的树叶都在2级)。 我可以通过节点导航:左,右或父母。 我知道整个节点计数。
I have a red-black tree (binary tree, all the leaves are within 2 levels). I can navigate through nodes: to left, right or parent. I know the entire count of nodes.
我一定要找到一个树中的第N个最小的元素。有没有办法做到这一点比O(n)的速度更快?通过索引优化访问的任何想法?
I have to find the N-th smallest element in a tree. Is there any way to do this faster than in O(n)? Any ideas of optimizing access by index?
推荐答案
在每个节点X你是否应该存储,有多少个节点的树以X为根。
In each node X you should store, how many nodes are in subtree with X as a root.
count(LEAF) = 1
count(NODE) = count(NODE->LEFT) + count(NODE->RIGHT) + 1
在每次插入/删除,你应该使用这个公式在受旋转节点更新计数。
During each insert/delete you should use this equation to update counts in nodes affected by rotations.
在这个解决方案很简单
NODE nth(NODE root, int n) {
if (root->left->count <= n) return nth(root->left, n);
if ( root->left->count + 1 == n) return root;
return nth(root->right, n - root->left->count - 1);
}
这篇关于按序号索引红黑树访问的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文