这是一棵似乎不平衡的红黑树。如果是这样，请有人解释为什么它不平衡？。
术语“平衡”有点含糊，因为不同种类的平衡树具有不同的约束。
红黑树可确保通往叶子的每条路径都具有相同数量的黑节点，并且至少与红节点一样多。结果是最长的路径最多是最短的路径的两倍，这足以保证O（log N）时间用于搜索，插入和删除操作。
大多数其他种类的平衡树具有更严格的平衡约束。例如，一棵AVL树可确保每个节点两侧的最长路径的长度最多相差1。这超出了您的需要，并且存在成本-在AVL树中插入或删除（找到后目标节点）平均执行O（log N）次操作，而在红黑树中插入或删除则平均执行O（1）次操作。
如果要保持一棵树完全平衡，以便每个节点的每一侧都有相同数量的子孙，+ /-1，那将非常昂贵-插入和删除操作将花费O（N）时间。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句