红黑树的原理
红黑树的原理为：红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。所有数据块都存储在节点中。这些节点中的某一个节点总是担当起始位置的功能，称之为根节点或根。
红黑树是一种自平衡二叉查找树，是计算机科学领域中的一种数据结构，典型的用途是实现关联数组，存储有序的数据。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的。它可以在O(logn)时间内做查找，插入和删除，这里的n是树的结点个数。
数据结构二叉树代码
1 定义
2 前序遍历（根左右）
前序遍历 通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。
图3.13所示二叉树访问如下：
则3.13所示二叉树的前序遍历输出为：
ABDHIEJCFG
3 中序遍历(左根右)
中序遍历 就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。
图3.13所示二叉树中序访问如下：
则3.13所示二叉树的中序遍历输出为：
HDIBJEAFCG
4 后序遍历(左右根)
后序遍历 就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。
图3.13所示二叉树后序访问如下：
则图3.13所示二叉树的后序遍历输出为：
HIDJEBFGCA
1 定义
2 图解实例
选取一个节点为参照根节点，会发现所有的左侧子节点小于等于参照点，右侧大于等于参照点。
比如根节点9， 9所有的 左侧子节点（5、2、7、1、3） 都小于等于9.
比如根节点13，13所有的 左侧子节点（11、10、12） 都大于等于13.
3 查找
查找节点 10：根节点9开始，10>9 右侧，10<13 左侧，10<11 左侧，找到10.
下图是二叉查找树的极端情况
二叉查找树就是为了提高查询效率，而当前这种和我们写了一堆for循环是一样的。
为了应对这种情况：又出现了平衡二叉树--红黑树。后面会提到。
1 定义
红黑树的特性 :
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。也就是不能有连在一起的红色节点，但是可以有连在一起的黑色节点
（5）满足所有的二叉查找树的性质
红黑树示意图如下：
2 变换规则
左旋又分为两种情况，
（1）我们操作的结点E是整棵树的根节点，那么左旋实现为下面步骤
（2）我们操作的结点E有父结点，那么左旋实现为下面步骤
3）右旋
右旋同样分为两种情况，与左旋情况类似，故实际操作参考左旋。
3 插入
注意 ：上述描述中一个很重要的点是，在插入元素时，是将元素作为叶子结点插入的，插入到原红黑树的外部结点。
插入结点染色情况
插入结点后调整和平衡过程
1.变颜色的情况： 当前结点的父亲是红色，且它的祖父结点的另一个结点（也就是叔叔结点）也是红色：
2.左旋：当前父结点是红色，叔叔结点是黑色的时候，且当前的结点时右子树，则进行左旋。左旋过程不需要进行颜色变换。
3.右旋：当前父结点时红色，叔叔结点是黑色的时候，且当前的结点是左子树，则进行右旋。右旋过程中需要进行颜色变换，具体右旋过程如下。
实例讲解
参考视频：
https://www.bilibili.com/video/BV1tE411f7tP?p=4&spm_id_from=pageDriver
红黑树的添加删除算法
不懂
红黑树之原理详解
性质1: 每个节点要么是 黑色 ,要么是 红色 。
性质2: 根节点是 黑色 。
性质3: 每个叶子节点(NIL)是黑色。
性质4: 每个 红色 节点的两个子节点一定都是 黑色 。
性质5: 任意一个节点到每个叶子节点的路径都包含 数量相同 的 黑节点 。俗称: 黑高 !
从性质5又可以推出:
性质5.1: 如果一个节点存在黑子节点,那么该结点肯定有两个子节点。
插入操作包括两部分工作:
注意: 插入结点,必须为 红色 ,理由很简单,红色在父节点(如果存在)为黑色节点时,红黑树的黑色平衡没被破坏,不需要做自平衡操作。如果插入结点是黑色,那么插入位置所在的子树黑色结点总是1,必须做自平衡。
最简单的一种情景,直接把插入结点作为根结点就行
注意: 根据红黑树性质2: 根结点是黑色。还需要把插入结点设为黑色。
处理: 更新当前结点的值,为插入结点的值
由于插入的结点是红色的,当插入结点的父结点为黑色时,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。
再次回想红黑树的性质2: 根结点是黑色。如果插入结点的父结点为 红结点 ,那么该父结点不可能为根结点,所以插入结点总是存在祖父结点。这一点很重要,因为后序的旋转操作肯定需要祖父结点的参与。
依据红黑树 性质4可知,红色结点不能相连===>祖父结点肯定为黑结点
因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是:黑红红。显然最简单的处理方式是把其改为: 红黑红
处理:
1.将P和U结点改为黑色
2.将PP改为红色
3.将PP设置为当前结点,进行后序处理
注意: 单纯从插入前来看,叔叔结点非红即空(NIL结点),否则的话破坏了红黑树性质5,此路径比其它路径多一个黑色结点。
处理:
处理:
该情景对应情景4.2,只是方向反转,直接看图
处理:
处理:
concurrenthashmap底层有用到AQS吗
1、ConcurrentHashMap底层数据结构是一个数组table
2、table数组上挂着单向链表或红黑树
3、new ConcurrentHashMap();如果没有指定长度的话，默认是16，并且数组长度必须是2的n次幂，若自定义初始化的长度不是2的n次幂，那么在初始化数组时，会吧数组长度设置为大于自定义长度的最近的2的n次幂。（如：自定义长度为7，那么实际初始化数组后的长度为8）
4、底层是使用synchronized作为同步锁，并且锁的粒度是数组的具体索引位（有些人称之为分段锁）。
5、Node节点，hash>0，当hash冲突时，会形成一个单向链表挂在数组上。
6、ForwardindNode，继承至Node，其hash=-1，表示当前索引位的数据已经被迁移到新数组上了
7、ReservationNode，继承至Node，其hash=-3，表示当前索引位被占用了（compute方法）
8、TreenBin，继承至Node，其hash=-2，代表当前索引下挂着一颗红黑树
9、lockState为ConcurrentHashMap底层自己实现的基于cas的读写锁，锁粒度是具体的某颗树。当向红黑树进行增，删操作时，首先会先上sync同步锁，然后自平衡的时候会上lockState写锁，当读红黑树的时候，会上lockState读锁，然后判断此时是否有线程正持有写锁，或是否有线程正在等待获取写锁，若有，则读线程会直接去读双向链表，而不是去读红黑树。
10、TreeNode，hash>0，为红黑树具体节点。TreeBin的root代表红黑树的根节点，first代表双向链表的第一个节点
11、双向链表：构建红黑树时还维护了一个双向链表，其目的为：(1)当并发写读同一颗红黑树的时候，读线程判断到有线程正持有写锁，那么会跑去读取双向链表，避免因为并发写读导致读线程等待或阻塞。(2)当扩容的时候，会去遍历双向链表，重新计算节点hash，根据新的hash判断放在新数组的高位还是地位
1、触发扩容的规则：
1）添加完元素后，若判断到当前容器元素个数达到了扩容的阈值（数组长度*0.75），则会触发扩容
2）添加完元素后，所在的单向链表长度>=8，则会转为红黑树，不过在转红黑树之前会判断数组长度是否小于64，若小于64则会触发扩容
2、table为扩容前的数组，nextTable为扩容中创建的新数组，迁移数据完毕后需要将nextTable赋值给table
3、扩容后的数组是元素组长度的2倍
4、ln，hn分别表示高位和低位的链表（高链，低链）。即，扩容时，会用n&h==0来判断元素应该放在新数组的i位置还是i+n位置。n：元素组长度；h：元素hash值；i：元素所在的原数组索引位；。这样就会出现有些元素会被挂在低位，有些元素会被挂在高位，从而达到打散元素的目的。
5、红黑树扩容时，会遍历双向链表，并且计算n&h==0来判断元素放在低位（lo）还是高位（ho），确定完元素的去处之后，会判断分别判断两个双向链表（lo,ho）的长度是否大于6，若大于6则将还是以一颗红黑树的结构挂在数组上，若<=6的话，则转为单向链表，挂在数组上
以上就是关于红黑树的原理，数据结构二叉树代码的全部内容，以及红黑树的原理的相关内容,希望能够帮到您。
版权声明：本文来自用户投稿，不代表【易百科】立场，本平台所发表的文章、图片属于原权利人所有，因客观原因，或会存在不当使用的情况，非恶意侵犯原权利人相关权益，敬请相关权利人谅解并与我们联系（邮箱：350149276@qq.com）我们将及时处理，共同维护良好的网络创作环境。
