黑马程序员技术交流社区

标题: [Android] 武汉校区独家分享：数据结构之红黑树 [打印本页]

---

作者: 武汉分校-小舞    时间: 2016-3-14 17:12
标题: [Android] 武汉校区独家分享：数据结构之红黑树

武汉校区独家分享：数据结构之红黑树

平衡二叉树追求绝对平衡，红黑树则不追求完全平衡，与平衡二叉树查找效率差不多情况下，红黑树在添加删除时更高效。应用最多的也是红黑树，但要搞懂红黑树却是要费一番周折。
红黑树也是二叉查找树，为了查找复杂度稳定为O(logn)，不依赖输入序列的顺序，通过旋转和对节点涂色来达到二叉树的相对平衡。
红黑树的5个性质，请反复读几遍：
1、每个节点，要么为红，要么为黑
2、根节点为黑
3、每个叶子节点都为黑（空指针认为是黑，所以左节点为空则左节点认为是黑节点，右节点为空则认为右节点为空，左右节点都为空，则左右节点都为黑节点）
4、红节点的左右儿子节点都为黑
5、对于任意结点，其到叶子结点每条路径都包含相同数目的黑结点

红黑树添加节点时，不同情况的不同操作
1、情况：父黑（父节点为黑）
动作：不做任何操作
2、情况：父红，叔黑，父左（父节点为红，父节点的另一子节点（叔节点）为黑，插入节点在父节点的左侧）
动作：右旋
3、情况：父红，叔黑，父右（父节点为红，叔节点为黑，插入节点在父节点的右侧）
动作：左旋
4、情况：父红，叔红（父节点为红，叔节点为红）
动作：黑父，黑叔（将父节点和叔节点的颜色改为黑色）

每种情况操作完成后，可能会变为另一种情况继续操作，最多不会超过3次旋转。

下面我通过一个添加节点的实例，一步一步的说明，遇到哪种情况做什么操作，能够一步一步读懂，对红黑树就有了初步的理解。

点开图片放大了看，顺序为一列一列看。
为了简单，图中的叶子节点没有画出空指针的黑节点，你知道空指针对应的是黑节点就行了。


本帖持续跟新，想最快获最新独家分享请加QQ 1641907557 ，后期会分享更多与实体班同步教程，助你冲击月薪20K！

推荐阅读：

《黑马程序员Android实体班同步项目Demo源码汇总，挑战月薪20K！》
《【武汉校区】Java/Android实体班同步笔记+配套面试/项目宝典》

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2