红黑树
时间:2021-09-07 05:36:39
收藏:0
阅读:9
红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。
红黑树的5个特性
- 根节点是黑色。
- 每个节点要么是红色要么是黑色。
- 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)都是黑的。
- 如果一个结点是红的,那么它的两个儿子都是黑的。
- 对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。
原文:https://www.cnblogs.com/GoslingWu/p/15233726.html
评论(0)