红黑树再平衡 [英] Red Black Trees Rebalancing

问题描述

我想在我的树中插入 7 个项目 -3、-2、-1、0、1、2 和 3.当我按以下顺序插入时，我得到了高度为 3 的均衡树，无需进行旋转:0，-2, 2, -1, 1, -3, 3. 但是当我按升序插入所有项目时，根节点的右侧部分会重新平衡，但根节点的左侧部分不会.我见过的所有重新平衡算法都是从插入的节点重新平衡到根节点，然后停止.他们不应该继续到根节点的另一部分吗?如果我按升序(例如 0 到 100)插入大量项目，我感觉情况会变得更糟.最后，树是平衡的，但没有高度优化.

I want to insert 7 items in my tree -3, -2, -1, 0, 1, 2 and 3. I get a well balanced tree of height 3 without doing rotations when I insert by this order: 0, -2, 2, -1, 1, -3, 3. But when I insert all items in ascending order, the right part of the root node does rebalancing, but the left part of the the root node doesn't. All rebalancing algorithms I have seen, do rebalancing from the inserted node up to the root node, and then they stop. Shouldn't they continue to the opposite part of the root node? And I have the feeling it gets worse, if I insert lots of items in ascending order (like 0 to 100). At the end tree is balanced, but is not height optimized.

推荐答案

平衡二叉搜索树(R/B 树、AVL 树等)都没有提供绝对平衡，即它们都没有提供最小可能的高度.这是因为不可能快速进行这种完全"的重新平衡.如果我们希望始终保持尽可能最小的高度，则树操作通常需要大量重新平衡，因此重新平衡将在 O(log N) 中不起作用.结果，所有操作(插入、更新、删除等)在 O(log N) 时间内也将无法工作，这将破坏平衡树的整个思想.

None of the balanced binary-search trees (R/B trees, AVL trees, etc.) provide absolute balancing, that is none of them provide minimal possible height. This is because it is not possible to do such a "complete" rebalancing fast. If we want always to keep the height minimal possible, a heavy rebalancing will often be required on tree operations, and therefore the rebalancing will not work in O(log N). As a result, all the operations (insert, update, delete, etc) will not work in O(log N) time also, and this will destroy the whole idea of balanced tree.

平衡树做保证的是对树高的一个不那么严格的要求:树高是O(log N)，即C*log N 用于某些常量 C.所以这棵树不能保证是理想的平衡，但平衡总是离理想不远.

What balanced trees do guarantee is a not-so-strict requirement on tree height: the tree height is O(log N), that is C*log N for some constant C. So the tree is not guaranteed to be ideally balanced, but the balance will always be not far from ideal.

这篇关于红黑树再平衡的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！