红黑树与BST的高度特性
红黑树与BST的高度特性
提问于 2020-12-03 20:21:15
考虑到我们只想将BST转换为红黑树，只需着色，而不做任何其他更改。
为什么高度为2*log n的二进制搜索树并不总是使用上述事实转换为红黑树，而完全平衡的BST总是可以通过着色转换为红黑树？
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-12-04 00:18:24
要求树具有一定的高度会限制最大深度，但不会限制最小深度。你可以有一个高度为2log n的树，其中有一个浅的左子树和一个深的右子树：
*
/ \
/ \
* *
/ \
/ \
/ \
/ \
/ \
/___________\所有节点的黑色高度必须相同，这意味着左子树将黑色高度限制为最多2。但是，如果每条路径上只有两个黑色节点，则无法避免右子树中的红色边缘。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/65133554
复制相关文章
相似问题
腾讯云开发者
