红黑树的最大不平衡度是多少？是否为树高的1/2或等于1？

最大不平衡度及与树高的关系 #

红黑树的核心约束是：任意节点到其所有叶子节点的路径中，黑节点的数量（黑高度）完全一致。基于这个规则，红黑树的最长路径（节点数最多）长度不会超过最短路径（节点数最少）的2倍：

• 最短路径由全黑节点构成，假设黑高度为k，则路径节点数为k；
• 最长路径是黑红节点交替排列（每个黑节点下挂载一个红节点，避免连续红节点违反规则），此时路径节点数为2k。

如果以最长路径与最短路径的高度差作为不平衡度的衡量标准，那么最大不平衡度为k。而此时树的总高度（即最长路径的高度）为2k，因此这个最大不平衡度恰好是树高的1/2。

关于“最大不平衡度为1”的观点纠正 #

你提到的“叶子节点前一层均为红色节点”的场景，并非红黑树的最大不平衡状态。这种场景下的路径高度差远小于2倍的极限情况。红黑树的最大不平衡出现在“一条路径全黑，另一条路径黑红交替且每个黑节点都带红子节点”的结构中，此时两条路径的高度差远大于1，所以你的这个观点并不正确。

内容的提问来源于stack exchange，提问作者Ivory Le