首页 > 代码库 > 红黑树
红黑树
具有以下特性的二叉查找树:(红黑树的深度可以保证是对数级的,它的深度通常和AVL树是一样的)
1,每个结点都被标记为红色或者黑色
2,根是黑色的
3,如果某个结点是红色的,那么它的孩子是黑色的(连续的红色结点是不允许的)
4,每一条从某个结点到一个null链的路径必须包含相同数量的黑色结点
自下而上的插入:
1:(1)新的结点必须涂成红色的
1)新结点的父亲是黑色,操作完成
2)父亲是红色的,需要改变颜色和树旋转:
父亲的兄弟结点是黑色的,X是外部的孙子
X是内部的孙子
红黑树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。