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

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

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


总结的几点为:


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


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


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


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


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


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

2019072820372459.png

20131105210403718.jpg

目录
相关文章
|
9月前
|
存储 算法 Java
红黑树原理和算法分析
红黑树原理和算法分析
105 0
|
算法
建筑抢修 (大根堆+贪心+优先队列+快速排序+2重思想比较)
建筑抢修 (大根堆+贪心+优先队列+快速排序+2重思想比较)
64 0
|
算法
算法之小细节(细节~链表的特殊结点~提升优化度)~反转链表、删除排序链表中的重复元素
算法之小细节(细节~链表的特殊结点~提升优化度)~反转链表、删除排序链表中的重复元素
116 0
|
算法
一步一步写算法(之链表逆转)
原文: 一步一步写算法(之链表逆转) 【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】     链表逆转是面试环境中经常遇到的一道题目,也是我们在实际开发中可能会遇到的开发需求。
912 0
|
存储 算法
【数据结构】图以及图的遍历(深度遍历和广度遍历)
【数据结构】图以及图的遍历(深度遍历和广度遍历)
217 0
|
算法
算法基础~链表~链表求环解法二,快慢指针法【数学思路】
算法基础~链表~链表求环解法二,快慢指针法【数学思路】
147 0
算法基础~链表~链表求环解法二,快慢指针法【数学思路】
|
算法 索引
重温算法之环形链表 II
有时候一些题目如果借助额外的空间,比如hash这种会事半功倍,但是其实这种算是一种'投机取巧'的做法,在现有的前提是实现算法,解题的最佳方法应该是不借助额外的空间,即减小其时间复杂度。
110 0
重温算法之环形链表 II
|
10月前
leetcode94二叉树的中序遍历(迭代做法)
leetcode94二叉树的中序遍历(迭代做法)
60 0