为什么红黑树插入后一直保持不平衡？
Why the Red Black Tree is kept unbalanced after insertion?
Here是一棵看起来不平衡的红黑树。如果是这种情况，请有人解释一下为什么不平衡？。
是的，它是平衡的。规则说，计算黑色 NIL 叶子，最长的可能路径应该包含最多 2*B-1 个节点，其中 B 是从根到任何叶子的最短可能路径中的黑色节点。在您的示例中，最短路径有 2 个黑色节点，因此 B = 2，所以最长路径最多可以有 3 个黑色节点，但它只有 2 个。
术语"balanced"有点含糊，因为不同种类的平衡树有不同的约束条件。
红黑树确保到叶子的每条路径都具有相同数量的黑色节点，并且至少与红色节点一样多的黑色节点。结果是最长路径最多是最短路径的两倍，这足以保证O(log N)的搜索、插入和删除操作时间。
大多数其他类型的平衡树都有更严格的平衡约束。例如，AVL 树确保每个节点任一侧的最长路径的长度最多相差 1。这超出了您的需要，并且有成本 - 在 AVL 树中插入或删除（在找到之后目标节点)平均需要O(log N)次操作，而在红黑树中插入或删除平均需要O(1)次操作。
如果你想让一棵树完全平衡，这样你在每个节点的两边都有相同数量的后代，+/- 1，这将是非常昂贵 -- 插入和删除操作将花费 O(N) 时间。
Here是一棵看起来不平衡的红黑树。如果是这种情况，请有人解释一下为什么不平衡？。
是的，它是平衡的。规则说，计算黑色 NIL 叶子，最长的可能路径应该包含最多 2*B-1 个节点，其中 B 是从根到任何叶子的最短可能路径中的黑色节点。在您的示例中，最短路径有 2 个黑色节点，因此 B = 2，所以最长路径最多可以有 3 个黑色节点，但它只有 2 个。
术语"balanced"有点含糊，因为不同种类的平衡树有不同的约束条件。
红黑树确保到叶子的每条路径都具有相同数量的黑色节点，并且至少与红色节点一样多的黑色节点。结果是最长路径最多是最短路径的两倍，这足以保证O(log N)的搜索、插入和删除操作时间。
大多数其他类型的平衡树都有更严格的平衡约束。例如，AVL 树确保每个节点任一侧的最长路径的长度最多相差 1。这超出了您的需要，并且有成本 - 在 AVL 树中插入或删除（在找到之后目标节点)平均需要O(log N)次操作，而在红黑树中插入或删除平均需要O(1)次操作。
如果你想让一棵树完全平衡，这样你在每个节点的两边都有相同数量的后代，+/- 1，这将是非常昂贵 -- 插入和删除操作将花费 O(N) 时间。