红黑树(中)完整建树过程

简介: 手撕JAVA(十四)一文中有些地方表述有误,笔者日后在做修改。这里用画图的方式展示两次红黑树的完整建图过程,一次简单,一次复杂,根据建图过程,就可以理解红黑树是如何实现的。总结的几点为:1.根节点必为黑色,任何调整动作都无法将根节点染红2.新插入节点的父节点和uncle节点同为红色,直接染黑父节点和uncle节点,染红祖父节点(如果祖父节点为根节点,就免疫)

手撕JAVA(十四)一文中有些地方表述有误,笔者日后在做修改。这里用画图的方式展示两次红黑树的完整建图过程,一次简单,一次复杂,根据建图过程,就可以理解红黑树是如何实现的。


总结的几点为:


1.根节点必为黑色,任何调整动作都无法将根节点染红


2.新插入节点的父节点和uncle节点同为红色,直接染黑父节点和uncle节点,染红祖父节点(如果祖父节点为根节点,就免疫)


3.新插入节点的父节点为红色,uncle节点为空或者黑色分以下两种情况处理:


         3.1连续红节点同侧(即父节点如果在树的右子树,子节点也是父节点的右节点),以父节点为基准,左旋。


         3.2.连续红节点异侧,先将祖父节点、父节点变色,然后以祖父节点为基准右旋。


3.旋转动作后变为叶子节点的节点染红,变为根节点的节点染黑。

2019072820372459.png

20131105210403718.jpg

目录
打赏
0
0
0
0
22
分享
相关文章
|
11月前
leetcode94二叉树的中序遍历(迭代做法)
leetcode94二叉树的中序遍历(迭代做法)
62 0
|
5月前
|
二叉树遍历:探索树结构的关键步骤
【10月更文挑战第29天】
46 1
经典算法之链表篇(三)
经典算法之链表篇(三)
118 4
经典算法之链表篇
经典算法之链表篇
|
6月前
|
经典算法之链表篇(二)
经典算法之链表篇(二)
用递归的思想实现二叉树前、中、后序迭代遍历
用递归的思想实现二叉树前、中、后序迭代遍历
102 1
「AVL平衡树专项」带你领略常用的AVL树与红黑树的奥秘(规则篇)
原先属于X的空结点被A“继承”。如果被删除结点是黑色结点,则可能造成树的黑色高度变化。
472 0
红黑树原理和算法分析
红黑树原理和算法分析
129 0
|
11月前
|
二叉树遍历(五-最终篇)
二叉树遍历(五-最终篇)
二叉树的遍历【学习算法】
二叉树的遍历【学习算法】
55 1