我有一棵红黑树(二叉树,所有叶子都在2层以内)。
我可以浏览节点:向左、向右或父节点。
我知道节点的全部数量。
我必须找到树中第 N 个最小的元素。有没有比 O(n) 更快的方法?有什么通过索引优化访问的想法吗?
在每个节点 X 中,您应该存储以 X 作为根的子树中有多少个节点。
count(LEAF) = 1
count(NODE) = count(NODE->LEFT) + count(NODE->RIGHT) + 1
在每次插入/删除期间,您应该使用此方程来更新受旋转影响的节点中的计数。
之后解决方案就简单了
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);
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)