红黑树
本文共 522 字，大约阅读时间需要 1 分钟。
平衡二叉树
任意节点的左右子树高度相差不能大于1
红黑树
是一种不严格的平衡二叉树，一类节点被标记为红色，一类节点被标记为黑色，同时满足以下几个要求：
- 根节点是黑色的
- 每个叶子节点都是黑色的空节点，也就是说，叶子节点不存储数据
- 红色节点不能相邻
- 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点
红黑树近似平衡
要想分析红黑树是否是近似平衡的，只要分析红黑树的高度大约是logn就可以了。
首先把红色节点去掉，没有父节点的，直接拿祖父节点，那么就会出现四叉树，肯定会比完全二叉树的高度要小，所以去掉红色节点的红黑树的高度不会超过logn,再把红色节点加回去，红色节点不相邻，那么最多也就是2logn，红黑树的性能下降的不多。红黑树的操作
插入操作
插入的节点必须是红色的，新插入的节点都是放在叶子节点上。
- 如果插入的节点的父节点是黑色的，不需要调整
- 如果插入的节点是根节点，直接改变颜色为黑色就行
变换规则：
旋转和颜色变换规则：所有插入的点默认为红色- 变颜色的情况：当节点的父亲是红色，且它的祖父节点的另一个子节点（叔叔节点）也是红色 1 把父节点设为黑色 2 把叔叔节点设为黑色 3 把祖父也就是父亲的父亲设为红色
转载地址：http://lobjn.baihongyu.com/
你可能感兴趣的文章
蓝桥杯大小写转换
查看>>
字符串合并
查看>>
贪心算法
查看>>
斐波那契数列
查看>>
java蓝桥杯2017年A组
查看>>
编写代码与初步运行
查看>>
汇编语言之debug篇
查看>>
随机行走
查看>>
树与二叉树
查看>>
荷兰国旗问题
查看>>
Java实现 第十一届 蓝桥杯 （本科组）省内模拟赛（1）
查看>>
螺旋矩阵/正整数摆动
查看>>
小明植树
查看>>
8.2 可编程并行接口芯片8255A
查看>>
户户通---Java蓝桥杯
查看>>
历年数学建模大赛优秀论文解读
查看>>
最优化模型
查看>>
范式题
查看>>
80X86指令系统（2）---数据传送指令
查看>>
图的应用-----关键路径
查看>>