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

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

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


总结的几点为:


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


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


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


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


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


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

2019072820372459.png

20131105210403718.jpg

目录
相关文章
|
10月前
leetcode94二叉树的中序遍历(迭代做法)
leetcode94二叉树的中序遍历(迭代做法)
57 0
|
4月前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
104 5
|
5月前
【初阶数据结构】打破递归束缚:掌握非递归版快速排序与归并排序
【初阶数据结构】打破递归束缚:掌握非递归版快速排序与归并排序
|
9月前
|
算法 架构师 NoSQL
「AVL平衡树专项」带你领略常用的AVL树与红黑树的奥秘(规则篇)
原先属于X的空结点被A“继承”。如果被删除结点是黑色结点,则可能造成树的黑色高度变化。
467 0
|
算法
用递归的思想实现二叉树前、中、后序迭代遍历
用递归的思想实现二叉树前、中、后序迭代遍历
97 1
|
9月前
|
存储 算法 Java
红黑树原理和算法分析
红黑树原理和算法分析
95 0
|
10月前
|
存储
二叉树遍历(五-最终篇)
二叉树遍历(五-最终篇)
|
算法
单链表(面试算法题3)---两链表相交问题
单链表(面试算法题3)---两链表相交问题
48 0
【基础算法】单链表的OJ练习(5) # 环形链表 # 环形链表II # 对环形链表II的解法给出证明(面试常问到)
【基础算法】单链表的OJ练习(5) # 环形链表 # 环形链表II # 对环形链表II的解法给出证明(面试常问到)
如何根据二叉树的两种遍历方式重建二叉树(理论篇)
如何根据二叉树的两种遍历方式重建二叉树(理论篇)
139 0