首页 > 代码库 > 红黑树

红黑树

具有以下特性的二叉查找树:(红黑树的深度可以保证是对数级的,它的深度通常和AVL树是一样的

1,每个结点都被标记为红色或者黑色

2,根是黑色的

3,如果某个结点是红色的,那么它的孩子是黑色的(连续的红色结点是不允许的

4,每一条从某个结点到一个null链的路径必须包含相同数量的黑色结点

自下而上的插入:

1:(1)新的结点必须涂成红色的

    1)新结点的父亲是黑色,操作完成

    2)父亲是红色的,需要改变颜色和树旋转:

        父亲的兄弟结点是黑色的,X是外部的孙子

 

          X是内部的孙子

 

        

 

红黑树