同步阅读进度,多语言翻译,过滤屏幕蓝光,评论分享,更多完整功能,更好读书体验,试试 阅读 ‧ 电子书库
结论
红黑树和其他的平衡二叉查找树一样,比简单的二叉查找树实现复杂得多。不过这个代价通常是值得的,因为我们可以很明显地看到性能的改进。红黑树有两个存储方面的需求。
·每一个节点需要存储其颜色,至少需要一个bit,但是事实上大多数实现都使用了至少一个字节。
·每一个节点都必须有一个父节点的链接,这个在二叉查找树中是不需要的。
红黑树的根节点必须是空值的。程序员能够让所有的叶子节点的指针都指向这个单个空值节点。
请支持我们,让我们可以支付服务器费用。
使用微信支付打赏