红黑树

墨尘 108 0

树结构的常用术语:

路径:顺着节点的边从一个节点走到另一个节点,所经过的顺序排列就称之为"路径"

根:树顶端的节点称为根,一颗树只有一个根,如果要把一个节点和边的集合称之为树,那么从根到其他任何一个节点都必须有且只有一条路径,A是根节点

父节点:若一个节点含有一个父节点,则这个节点称为其子节点的父节点

子节点:一个节点含有的子树的节点称为该节点的子节点

兄弟节点:具有相同父节点的子节点,称为兄弟节点

子树:每个节点都可以作为子树的根,它和它所有的子节点、子节点的字节点等都包含在子树中

节点的层次:从根开始定义,根为第一层,根的子节点为第二层,以此类推

深度:对于任意节点NN的深度为从根到N的唯一路径长,根的深度为0;(从上往下看)

高度:对于任意节点NN的高度为从N到一片树叶的最长路径长,所有树叶的高度为0:(从下网上看)

二叉树:树的每个节点最多只能有两个子节点

二叉搜索树:也是二叉树的一种

若它的左子树不为空,则左子树上所有的节点的值均小于它的根节点的值

若它的右子树不为空,则右子树上所有的节点的值均大于它的根节点的值

它的左、右子树也分别为二叉排序树

 

二叉搜索树——查找:

查找某个节点,我们必须从根节点开始查找,

1、查找的值比当前节点大,则搜索右子树

2、查找值等于当前节点值,停止搜索

3、查找值小于当前节点,则搜索左子树

 

image.png


比如查找值为5的叶子,先从根节点10开始比较,查找值5小于10,所以查找左子树,然后去和8比较,查找值5小于8节点,所以查左边子树,然后查找值与4节点比较,查找值5大于4节点,所以查询右子树

 

二叉搜索树———插入

插入与查找相似,也是将你要插入的值和每个节点相比较,然后根据二叉树的定义,去插入即可

二叉搜索树———遍历

有三种遍历方式:前序遍历,中序遍历,后序遍历

一般情况使用中序遍历,因为中序遍历是从小到大的结果

比如上面的二叉树中序遍历结果:4>5>8>9>10>11>15>20

二叉搜索树———删除

删除一个子节点:

同理,与查找一样,将你要删除的子节点与每个节点比较,相同的话,将他制空,

删除一个带有子节点的节点:

我们只需要将其父节点原本指向该节点的引用,改为指向改子节点即可

删除有两个子节点的节点:

找到你要删除的这个节点的后继节点,然后将这个后继节点代替你删除的节点

 

删除有没有必要:

没有太大删除的必要,只要在上面加上个属性值进行判断即可,判断是否被删除,进行逻辑删即可,不需要改变二叉树结构


二叉搜索树———时间复杂度分析:

[12345678910.。。。。100]

暴力算法:运气好时 性能不错 运气不好时,性能暴跌

二分查找算法:数据源必须是有序数组,性能好 每次迭代查询可以查询掉一半的查询结果

如何解决二叉搜索树 造成线性链表问题?

如果插入元素时  树可以自动调整两边平衡 会保持不错的查找性能

AVL树(平衡树):

具有二叉朝朝树的全部特性

每个节点的左子树和右子树的高度至多等于1

 

为什么有了平衡树,还需要红黑树?

虽然平衡树解决了二叉查找树退化未近似链表的缺陷,能够把查找的时间控制在O(logn),不过却不是最佳的,

因为平衡树要求每个节点的左子树和右子树的高度差至多等于1,这个要求实在太严了,导致每次进行插入/删除节点的时候,几乎都会破坏平衡树的第二个规则,进而,我们需要通过左旋和右旋来进行调整,使之再次成为一颗符合要求的平衡树

 

显然,如果在哪种插入、删除很频繁的常景中,平衡树需要频繁的进行调整,这会使平衡树的性能大打折扣,为了解决这个问题于是就有了红黑树

红黑树:

红黑树的性质:

每个节点要么时黑色,要么是红色

根节点是黑色

每个叶子节点(NIL)是黑色。(NIL节点是null节点)

每个红色节点的两个节点一定是黑色。不能有两个红色节点相连。

任意一节点到每个叶子节点的路径都包含数量相同的黑节点,俗称:黑高

5.1如果一个节点存在黑子节点,那么改节点肯定有两个子节点

 

红黑树能自平衡  靠的是三种操作:左旋 右旋  变色

1、变色:节点的颜色由红遍黑或由黑变红

2、左旋:以某个结点作为支点(旋转结点),其右子节点变为旋转节点的父节点,右子结点的左子节点变为旋转节点的右子节点,左子节点保存不变

 

3、右旋:以某个结点作为支点(旋转结点),其左子节点变为旋转节点的父节点,左子结点的右子节点变为旋转节点的左子节点,右子节点保存不变

 

红黑树———查找

和二叉树的查询一样,也是比较,大于就找右,小于就找左

红黑树———插入

查找插入的位置,黑色插入一定会破坏平衡

插入后自平衡

插入的节点,必须是红色,以为红色在父节点(如果存在)为黑色节点的时候,红黑树的黑色平衡没被破坏,不需要做自平衡操作,但如果插入的节点是黑色的时候,那么插入的位置所在的子树的黑色节点始终总是多1,必须做自平衡


红黑树插入节点情节分析

情景1:红黑树为空树

最简单的一种情景,直接把插入节点作为根节点就行

注意:根据红黑树性质2:根节点是黑色,还需要把插入节点设为黑色

情景2:插入节点的Key已存在

处理:更新当前节点的值,为插入节点的值

 

情景3:插入节点的父节点为黑色节点

 直接插入即可  不影响树平衡

情景4.1:叔叔节点存在并且为红色节点

依据红黑树性质4可知,红色节点不能相连   祖父节点肯定为黑节点

因为不可以同时存在两个相连的红节点,那么此时该插入子树的红黑层数的情况是:黑红红,显然最简单的处理方式是把其改为:红黑红,

处理: 1、将祖父节点改为红色,

   2、将父节点和叔叔节点改为黑色

   3、将祖父节点设为当前节点,进行后续处理

情景4.2:叔叔节点不存在或为黑节点,并且插入节点的父亲节点是祖父节点的左子节点

注意:单纯从插入前来看,叔叔节点非红即空(NIL),否则的话破坏了红黑树性质,次路径会比其他路径多一个黑色节点

情景4.2.1:插入节点,为其父节点的左子节点(红色情况)

处理:

1、变颜色:将父节点设为黑色,祖父节点设为红色

2、对祖父节点右旋

情景4.2.2:新插入节点,为其父节点的右子节点

处理:对父亲节点进行左旋

将父亲节点设置为当前节点,得到LL红色情况

按照LL红色情况处理(1、变颜色2、对祖父节点右旋右旋)

情景4.3:叔叔节点不存在或者为黑节点,并且插入节点的父节点是祖父节点的右子节点

该情景对应情景4.2,只是方向反转

 处理:将父节点变黑,祖父节点变红,然后祖父节点为当前节点,然后左旋,

情景4.3.2:插入节点,为其父节点的左子节点(RL红色情况)

处理:对父节点进行右旋,然后就成了RR双红,然后将父节点变黑,祖父节点变红,然后祖父节点为当前节点,然后左旋。

 

代码实例:https://gitee.com/cyymochen_admin/rbtree

标签: #Java #HasMap

  • 评论列表

留言评论