锐客网

  1. 首页 > 睿知 > it技术 > >

java红黑树删除源代码 java的红黑树

IT技术删除

红黑树(Red-black tree)树 是一种 抽象数据类型  ， 或是实作这种抽象数据类型的数据结构 ， 用来模拟具有树状结构性质的 数据集合。
红黑树 是一种自平衡二叉查找树 ， 典型的用途是实现 关联数组 ，它是复杂的，但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的 O(logn ) 时间内做查找 ， 插入和删除，这里的 n 是树中元素的数目 。
一个由n个节点随机构成的二叉查找树的高度为(logn).证明如下java红黑树删除源代码：
而时间复杂度是以某个基础数据操作的重复次数作为量度 。红黑树的是二叉搜索树，左子树上所有节点的值均小于他的根节点的值 ， 右子树上所有节点均大于根节点的值，左右子节树相对根节点按大小分布 。如果把每次节点值的比较看成基础数据操作，那么最差的查找情况是一直查找到高度最大的根节点，那么查找的时间复杂度即与高度成正比，可表示成 O(logn )。
简单java红黑树删除源代码了解了红黑树的字面定义，下面动手感受下红黑树的相关操作 。当你插入或者删除一个节点时，可能会破坏红黑树的性质，所以需要对树节点进行重新着色或者旋转 ， 来保持红黑树的结构 。首先看下二叉树的旋转 。
假设pivot节点不为空，其右子树不为空，那么左旋即是：使pivot的右孩子Y为子树的根 ， pivot节点为子树根节点的左孩子，pivot左孩子、Y节点的右孩子不改变，Y节点左孩子变为pivot节点右孩子 。
假设pivot节点不为空 ， 其左子树不为空，那么右旋：使pivot的左孩子Y为子树的根，pivot节点为子树根节点的右孩子，pivot的右孩子、Y节点的左孩子不变，Y节点的右孩子变为pivot节点的左孩子 。
实战演练之增加、删除节点时，如何保证红黑树的性质不被破坏 。
往一个空的红黑树中，依次插入数据：12 1 9 2 0 11 7 19 4
节点为根节点，所以为黑色，两个null节点为黑色节点 。
按照二叉搜索树的逻辑，9小于12、大于1 ， 应该是1节点的右孩子 。但，新增的两个NIL节点已经使得12，1 ， 9 ， NI这条路径的黑色节点至少为两个，而12，NIL这条路径的黑色节点只有两个 。所以要对1节点进行左旋 ， 9节点变为12节点的左孩子，发现问题还是存在 。继续 ， 对12节点进行右旋，9节点为根节点，1、12分别为9节点的左右孩子 。尝试着色 ， 9节点必须为黑色，而1，12节点可以为红色 ， 也可以为黑色 。
0节点直接作为1节点的左孩子，保持跟2节点相同的颜色即可 。左右子树依旧保持平衡 。
从二叉查找树的性质看，7节点作为2节点的右孩子即可 。这时来分析着色问题，我们先看最短路径的黑色分布，9，12 ， NIL这条路径，有三个黑色节点 ， 以此为参考 ， 尝试改变9节点左子树的着色 。目前最长的路径是9，1，2，7 ， NIL这条路径 。保持三个黑色节点的话，9跟NIL已经为黑色节点，而红色节点又不能挨着，所以只能是1为红色节点，2为黑色节点 ， 7为红色节点 。那么9，1，0，NIIL这条路径，0就要为黑色节点 。调整完毕 。
19节点作为12节点的右孩子，与左孩子保持一样的红色即可 。
4节点应该作为7节点的左子树 ， 无论着什么颜色 ， 以1节点为根节点的子树，都要破坏红黑性质 。所以应该进行旋转 。先以7为根节点进行一次右旋 ， 再以2为根节点进行一次左旋 。尝试着色即可 。
类似插入节点的分析、总结，删除节点也可以针对每种场景找到固定的着色方法，就像玩一个游戏，有自己的推理跟玩法 。我先做个PPT，这块稍后补充 。

推荐阅读


上一篇：服务器不支持ssl，服务器不支持ssl连线

下一篇：如何创建单位微信视频号呢，单位如何申请微信视频号