来看看，红黑树的广泛的应用：
所以掌握红黑树是非常有必要的！！！
BST二叉查找树什么是二叉查找树呢？
二叉查找树（BST）具备以下特性：
左边子树上的所有结点，其值都是小于或者等于它自身根结点的值的。右边子树上的所有结点，其值都是大于或者等于它自身根结点的值的。左边子树是二叉排序树。右边子树也是二叉排序树。这是二叉搜索树BST的完美情况。
在一般人们认知里的二叉树，其所指的也就是二叉搜索树BST，会凸显出一个问题，处在理想到极致的状况下，它呈现的样子大体是如此这般：
二叉搜索树的查找流程
如何查找值为7的节点？
对根节点8予以查看，原因是7 ，查看左子节点6 ，鉴于7大于6 ，故而再次查看其右子节点7。
3.查看右子节点7，因为7=7，所以就找到啦，
二叉搜索树的极端情况
二叉查找树具备缺点，在持续进行插入操作时，存在一种情形，即极易“退化”为链表。
倘若bst树的节点正是以从大到小的状态进行插入，在这种情形下，树的结构就类似于链表结构，在此时，查询或者写入所耗费的时间便同链表一样。
退化成为了 链表的特殊BST
一颗特殊BST，退化成为了 链表，如下图：
它和链表一样，搜索的时候，最坏情况的时间复杂度O(n) 。
那么我们怎么避免这种情况呢？
免得这种特别的情形出现，故而引入了平衡二叉树，这也就是 AVL ，还引入了红黑树，即 red - black tree。
AVL，采取自身建树准则来把控树的层数，以及节点位置，rbt亦是如此。
因为是由AVL演变而来，所以我们从了解AVL开始。
AVL平衡二叉树
名字简写是发明者名字的 AVL，它属于二叉搜索树的一种，被称作平衡二叉树，与之不同的是，AVL 借助机制确保自身平衡。
AVL树是最先发明的自平衡二叉查找树。
在AVL树里，对于任意节点而言，其两棵子树的高度之间，最大的差别是1，因而它又被称作高度平衡树。
增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
AVL树的特性
AVL树本质上还是一棵二叉搜索树，它有以下特性：
特性1表明，AVL 继承于 BST , 所以:
1.AVL本身首先是一棵BST 二叉搜索树。
2.AVL附带有平衡条件，此条件为，每个结点的左右子树的高度之差的绝对值，也就是平衡因子，最多为1。
于插入树节点之际，若破坏了上述原则其一，或者在删除树节点之时，若破坏了上述原则其一，那么AVL树会自行开展调整动作，以此促使上述三条原则依旧能够成立。
也就是说，AVL树，其本质是一种二叉查找树，这种二叉查找树带有平衡方面的功能，而二叉查找树也叫二叉排序树，又叫二叉搜索树。
AVL树的平衡功能
例举一个情形，在下边左边的那张图里，作为AVL树的最长的两个节点跟前边最短的八个节点，它们之间的高度差值是一。
插入一个新的节点后 ，依据上面第一条原则 ，它会出现在2节点的左子树 ，然而如此一来就违背了原则3。
此时AVL树会通过节点的旋转进行进行平衡，
AVL调整的过程称之为左旋和右旋，
AVL平衡的调整过程
在进行旋转操作之前，需要率先确定旋转的支点，也就是那个被称作pivot的内容： 这一旋转支点所指的具体是，那些失去平衡的树的部分，它恰好处于自平衡之后所形成的，根节点的位置处。
平衡的调整过程，需要根据pivot它来进行旋转。
我们于学习 AVL 树的旋转之际，切莫把失衡问题扩展至整个树去看待，如此这般会搅乱你的思路。
我们只关注失衡子树的根结点 及它的子节点和孙子节点即可。
事实上，对于AVL树的旋转，被我们暂且称作“AVL旋转”的这种操作，是存在规律能够摸索探寻的，原因在于，只要将注意力集中于出现失衡情况的子树，接着开展左旋、右旋的动作便可以了。
很多人在左旋和右旋有时候弄不明白，
其实左旋就是逆时针转，右旋是顺时针转
表明，这个文本在以pdf格式持续作出更新，更多最为新颖的尼恩3高pdf笔记，要从下面所给的链接去获得，它们分别是语雀，以及码云。
AVL子树失衡的四大场景
导致AVL失衡的场景就是有限的4个：
把元素删除掉，这同样会致使AVL失衡，进而得再来进行平衡操作，然而其平衡的原理跟插入元素时是相似的。
这里聚焦 介绍插入元素的平衡过程， 删除元素，不做介绍。
场景1: LL型失衡-左左结构失衡（右旋）：
场景： 插入的元素在子树root的左侧不平衡元素的左侧
这时，将root的左儿当作支点，也就是说，左侧的不平衡元素是pivot（支点），实施右旋。
来一个右旋的动画：
在进行右旋这个过程当中，要是pivot存在右子树的话，那就将其作为原本root的左子树，以此来保障AVL的特性1。
记忆要点
尼恩备注记忆要点，LL型失衡怎么 平衡呢？
旋转的反向，与失衡的方向相反，
LL 型失衡，与左边 相反的方向， 是右边，所以是右旋
场景2 RR型失衡：右右结构失衡（左旋）
场景：插入的元素在子树root右侧的不平衡子树的右侧
这时候，将root的右儿当作支点，也就是说，右侧的不平衡的元素是pivot（支点），开展左旋操作。
来一个左旋的动画：
处于左旋之时，假设存在左子树的话，那么它可当作原本的根节点的右子树的，是这样，没错的。
保障AVL的特性1，
记忆要点
尼恩备注记忆要点，RR型失衡怎么 平衡呢？
旋转的反向，与失衡的方向相反，
RR 型失衡，与右边 相反的方向， 是左边，所以是左旋
场景3 LR型失衡：左右结构失衡（左旋+右旋）：
场景： 插入的元素在左侧的不平衡元素的右侧
记忆要点
尼恩备注记忆要点，LR型失衡怎么 平衡呢？
旋转的反向，与失衡的方向相反，
LR型呈现失衡状态，与之方向完全相反的是RL，然而开始得先将底部予以旋转，随后再对顶部实施旋转，RL的进行次序是颠倒着的，LR。
所以， LR型失衡，旋转的方式，是先左旋， 再右旋
场景4 RL失衡: 右左结构 （右旋+左旋）：
场景： 插入的元素在右侧的不平衡元素的左侧
记忆要点
尼恩备注记忆要点，RL型失衡怎么 平衡呢？
旋转的反向，与失衡的方向相反，
RL型呈现失衡状态，与之方向完全相反的是LR，然而要先对底部实施旋转操作，之后再旋转顶部，基于这样的情况，LR的进行次序出现颠倒后成为RL。
最终， RL型失衡，旋转的方式，是先右旋， 再左旋
AVL树平衡总结
可见无论哪种情况的失衡，都可以通过旋转来调整。
似乎不难看出，旋转呈现在图上的样子，就如同把pivot（支点）节点朝着上方提升，也就是将其提升成为root节点，并且随后，在新root节点两侧，原本两边的节点会以物理方式分布开来。
接下来按照AVL二叉树的要求：
左子树小于root，右子树大于root进行调整。
能够从图LL结构察觉，在进行右旋操作的时候，原本pivot（7）的右子树（8），会变换到原root点（9）的左子树所在之处。
从图右右结构能够看出，当进行左旋操作时，原本pivot（18）的左子树，会分布到原root点（9）的右子树的位置。
无论左右结构，还是右左结构，无非是历经多次旋转从而达成稳定，旋转所采用的方式并无不同。
AVL树本质上还是一棵二叉搜索树，它有以下特性：
1.本身首先是一棵二叉搜索树。
具备平衡条件，即，针对每个结点而言，其左右子树的高度之差的绝对值，也就是平衡因子，最多为一。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
AVL树的删除
删除的判断标准
要删除的节点是什么类型的节点？；删除后是否会破坏平衡 ；
节点类型
叶子节点；节点只有左子树或只有右子树 ；既有左右子树都有。
处理的思路
若删除操作针对的是叶子节点，那么便直接将其删除，接着从该叶子节点的父亲节点起始，顺着往上查看，用来判定是否出现失衡情况；要是并未出现失衡现象，随后再去判断该父亲节点的父节点是否失衡，如此这般一直持续到根节点；一旦出现失衡状况，那就去判定失衡的具体类型（LL、LR、RR、RL），之后再开展相对应的调整操作。当删除的节点仅存在左子树或者仅有右子树之时，则进行节点删除的操作，采用左子树或者右子树完成代替，同时开展相应的平衡判定工作，要是出现失衡状况就予以调整，持续这个过程直至到达根节点 ；要是删除的节点既存在左子树同时还有右子树，那就寻觅其的前驱或者后驱节点来实施替换，接下来再判定是否处于失衡状态，随后按照失衡的具体情形加以调整，一直调整到根节点。
说明：本文会以pdf格式持续更新，更多最新尼恩3高pdf笔记，请从下面的链接获取：语雀 或者 码云
常见AVL面试题问：什么是AVL左旋和右旋？
加入节点后，左旋和右旋 ，维护AVL平衡性
右旋转
场景： 插入的元素在不平衡元素的左侧的左侧
x.right = y
y.left = xxx(原x.right)
对节点y进行向右旋转操作，返回旋转后新的根节点x
y x
/ \ / \
x T4 向右旋转 (y) z y
/ \ - - - - - - - -> / \ / \
z T3 T1 T2 T3 T4
/ \
T1 T2
场景：插入的元素在不平衡元素的右侧的右侧
// 向左旋转过程
x.left = y;
y.right =(原x.left )
对节点y进行向左旋转操作，返回旋转后新的根节点x
y x
/ \ / \
T1 x 向左旋转 (y) y z
/ \ - - - - - - - -> / \ / \
T2 z T1 T2 T3 T4
/ \
T3 T4
AVL树的问题
假设AVL树能够确保二叉树维持平衡状态，那么这便表明当进行AVL搜索操作之时，在其处于最坏情形的状况之下，耗费的时间复杂度为O(logn) ，此时间复杂度相较于普通二叉树BST以及链表在各自最坏情形下的O(n) 的时间复杂度而言，是更低的。
这般直接采用AVL树去替换链表就行得通，为何要选用红黑树呢，究竟出于何种缘由呢？
原因是：
因为AVL树得确保左右子树维持平衡，存在Max(最大树高减去最小树高)，红黑红。
1.将F和V节点改为黑色
2.将P改为红色
3.将P设置为当前节点，进行后续处理
可以看到，将P设置为红色了，
如果P的父节点是黑色，那么无需做处理；
然而要是P的父节点呈现红色，那么就违背红黑树性质了，因而把P来设置成当前节点，接着开展插入操作，进行自平衡处理，一直到整体达到平衡状态为止。
场景4.2：叔叔为黑色，父亲为红色，并且插在父亲的左节点
分为两种情况
叔叔呈现为黑色 ，或者不存在也就是NIL这种状态同样属于黑节点 ，并且节点的父亲节点身为祖父节点的左子节点。
要留意了：仅仅是从插入这个角度来讲，叔叔节点不是红色就是黑色（也就是NIL节点），不然的话会破坏红黑树性质5，在这个时候路径会比别的路径多出来一个黑色节点。
场景4.2.1 LL型失衡
特定的细分场景其一，首次插入全新的节点，该节点会成为其父亲节点的左侧子节点，此为LL红色状况，插入这个节点之后，便会形成LL型失衡。
自平衡处理：
1.变颜色：
将F设置为黑色，将P设置为红色
2.对F节点进行右旋
场景4.2.2 LR型失衡
细分场景2，新出现要插入的节点，此节点作为它父节点的右子节点，这属于LR红色情况，在进行插入操作之后，就形成了LR型失衡状态。
自平衡处理：
1.对F进行左旋
2.将F设置为当前节点，得到LL红色情况
3.按照LL红色情况处理(1.变色 2.右旋P节点)
情景4.3：叔叔处于黑节点状态，父亲呈现红色，而且父亲节点身为祖父节点的右子节点。
情景4.3.1：RR型失衡
新插入节点，为其父节点的右子节点(RR红色情况)
自平衡处理：
1.变色：
将F设置为黑色，将P设置为红色
2.对P节点进行左旋
情景4.3.2：RL型失衡
新插入节点，为其父节点的左子节点(RL红色情况)
自平衡处理：
1.对F进行右旋
2.将F设置为当前节点，得到RR红色情况
3.按照RR红色情况处理(1.变色 2.左旋 P节点)
说明：本文会以pdf格式持续更新，更多最新尼恩3高pdf笔记，请从下面的链接获取：语雀 或者 码云
RBT面试题：问：有了二叉搜索树，为什么还需要平衡二叉树？
二叉搜索树容易退化成一条链
此时，进行查找操作时，其时间复杂度会从 O ( log n），进而也会退化成 O ( N )。
带来一种对左右那些子树高度差存在限定的平衡二叉树AVL，以此确保查找这项操作的最坏时间复杂度同样是O ( log n）。
问：有了平衡二叉树，为什么还需要红黑树？
对于AVL而言，其左右子树的高度差值不许超过1，每当实施插入或者删除操作时，差不多都得经由旋转操作来维持平衡。
在那种频繁开展插入或者删除的场景里头，频繁出现的旋转操作致使AVL的性能大幅降低，大打折扣。
红黑树通过牺牲严格的平衡，换取插入/删除时少量的旋转操作，
整体性能优于AVL
问：红黑树那几个原则，你还记得么？
可以按照括号里边的分类，记住 红黑树的几个原则：
问：红黑树写入操作 ，是如何找到它的父节点的？
红黑树的节点 它就是继承Node结构，
先看看红黑树的节点结构
以中的红黑树的结构定义为例子：
static class Node implements Map.Entry {
final int hash;
final K key;
volatile V val;
volatile Node next;
}
/**
* Nodes for use in TreeBins
*/
static final class TreeNode extends Node {
TreeNode parent; // red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node next,
TreeNode parent) {
super(hash, key, val, next);
this.parent = parent;
}
额外添加了几个字段，在Node基础之上的这几个字段，其中一个指向父节点，另外一个用来指向左子节点left，还有一个则指向右子节点right。
然后还有表示颜色red属性
红黑树的插入操作：
首先是找到一个合适的插入点，就是找到插入节点的父节点，
由红黑树，它又契合BST二叉查找树的有序特性，因此这个找父节点的操作，与二叉查找树是全然相同的。
二叉查找树，左子节点小于当前节点，右子节点大于当前节点，
然后，针对每一回，进行向下查找一个层次的操作，如此便能够排除掉其中一半的数据，而查找所具备的效率呈现为log(N)。
最终查找到nil节点或者 key一样的节点。
要是最终寻觅到了，key相同的节点，那就开展更新操作。这一个.key跟当前put.key是全然一样的情形。而在此状况下这就用不着插入，只要替换value就行，并且父节点就是当下节点的父节点。
当最终查找得到nil节点时，开展插入操作，nil节点的父节点，即为当前节点的父节点，将插入的节点用以替换nil节点，随后实施红黑树的平衡处理。
问：红黑树的有那些内部操作
变色
实施对其采取把呈现为红色的节点予以转变从而成为黑色，或者是将呈现为黑色的节点给予转变进而成为红色，此行为便是属于针对于这个特定节点展开的变色操作行为。
旋转
与平衡二叉树的旋转操作类似。
红黑树与AVL树区别
1、调整平衡的实现机制不同
红黑树要依据路径之上黑色节点数量保持一致，以此来判断是不是失衡。要是失衡了，那就借助变色以及旋转的方式去恢复。
AVL依据树的平衡因子（此平衡因子指的是各个节点的左子树高度与右子树高度差的绝对值均不会超过1的状况）决定是否失衡，一旦失衡，便借助旋转予以恢复。
2、红黑树的插入效率更高
红黑树借助并非严格的那种平衡，去换来在增加以及删除节点之际，旋转次数的减轻状况，任何出现的不平衡情况，都会在三次旋转的范围之内得以解决。
红黑树并非追求那种所谓的“完全平衡”状况，它仅仅是要求能在一定程度上达成这般的平衡条件，使得对于进行旋转操作的要求有所降低，进而实现性能的提升。
AVL属于严格平衡树，也就是高度平衡的二叉搜索树，所以当进行节点增添或者删除操作时，因情况各异，其旋转次数相较于红黑树而言更多。
所以红黑树的插入效率更高
3、红黑树统计性能比AVL树更高
存在一种名为红黑树的数据结构，它可以在时间复杂度为O(log n)的情况之下，开展查询操作，还能够进行插入操作，并且也可以执行删除操作。
查找AVL树，插入AVL树，删除AVL树，这三种操作，在平均情况下是O(log n)，在最坏情况下也是O(log n)。
存在一种树，它的算法时间复杂度，与AVL树的是一样的，然而呢，它在统计性能这方面，则相较于AVL树是更高的，这种树就是红黑树。
4、适用性：AVL查找效率高
假如在你的应用里头，查询的频次远远高于插入以及删除，那么就要选择AVL树，要是查询与插入删除的频次大致差不多，就应当选择红黑树。
也就是说，有的时候，纯粹只是为了进行排序，这个排序的过程包括建立、遍历以及删除，并不进行查找或者查找的次数非常少，在这种情况下，R - B树会显得更合算一些。
说明：本文会以pdf格式持续更新，更多最新尼恩3高pdf笔记，请从下面的链接获取：语雀 或者 码云