按序号索引红黑树访问 [英] 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屋！