红黑树+AVL+BST

发布于:2022-11-29 ⋅ 阅读:(277) ⋅ 点赞:(0)

目录

 二叉树搜索树(BST)

二叉平衡树(AVL)

红黑树

 为什么HashMap在jdk8数据结构从数组+链表变为数组+红黑树 

问:时间不是和高度成正比吗?其实我们把红节点去掉,红黑树就是平衡树,那么为啥红黑是logn

插入流程


 

 二叉树搜索树(BST)

 特点:左子树比中间小,右子树比中间大,查询的效率依赖于它的深度

下面例图,右子树都比root节点7大并且递归下去也都满足局部右子树比局部root大;左子树同理

 同理

发现不符合BST二叉搜索树,1小于root不能放在右子树 

效率:有序数组情况下,效率为logn,最差为on——>(连续自增或者连续自减就会变成线性的结构)

 

二叉平衡树(AVL)

特点:右子树高度-左子树高度<=1,本质是继承BST二叉搜索树的

比如下面这颗树——>F的平衡因子=right-left=-1,保证了查询效率logn

红黑树

黑节点:root和叶子节点null节点都是黑节点,所以黑节点数量>=1/2*所有节点数

红节点:新插入的节点就为红节点,红节点的子必须为黑

 特点:并且两条路径下的黑节点数要相同——>上界:两条路径的节点数相同;下界:节点数差一倍

下面图会发现:1.两条路径黑节点相同;2.节点总数差一倍

与AVL的区别:那么对比于AVL二叉平衡树:1.深度相同;2.左右深度相差为1(条件较为严苛,那么耗费的时间就会长一点)

而红黑树:1.深度相同;2.左右深度差一倍(条件没有那么严苛,所以时间会短一点)

 

 为什么HashMap在jdk8数据结构从数组+链表变为数组+红黑树 

首先BST二叉搜索树,自增自减会导致成一个链表,On

AVL二叉平衡树上面也已经说了,局限性较高,耗时间会长一些

问:时间不是和高度成正比吗?其实我们把红节点去掉,红黑树就是平衡树,那么为啥红黑是logn

我们展示最差情况——>红黑相间,一边路径是一边路径节点数的两倍,那么层数就是翻倍的,所以时间为2*lognb(nb=1/2n,黑节点至少占一半,所以最差为logn/2)——>logn/2=logn-1——logn (平衡条件较为宽松,但是还是能保证时间复杂度为logn)

插入流程

首先讲一下左旋,比如b节点值,b在a也就是父节点的右边,它要往左边走,也就是说a会在b左边(总结就是父节点到左边去了,左旋的节点到上边去了),那么如果左旋的节点下带子节点,也就是下面的*放哪呢?——>放在a节点右下,因为*原来在a的右边,所以挂在a的右下,不挂在c是因为c可能原来就有了自然就不能替换了,所以放在a右下

 红黑左旋右旋变色操作

1.比如一开始001插入,因为是root所以是黑节点——>2.然后002插入,判断父节点和叔节点,由上述图可知,父为黑节点就无需任何操作了,是插入所以002为红色——>003插入,判断父叔节点,003父为红,叔节点为null(为黑节点)根据图可知类型是右右(根据爷爷节点与当前节点路径判断),可知操作时左旋+变色,003左旋将002提上去作为root,001变为002的左节点——>(左旋变色操作)左旋完后根据红黑节点的定义知道002为root所以变为黑,001变为红

 

 4.然后004插入,发现父叔节点均为红色,均为红色,那么父叔变黑,祖父节点变红——>然后祖父节点进行递归,也就是重复这个规则,也就是当作一个刚插入的节点进行父叔为红的一个操作——>变黑

 

 5.在下图情况下插入,比如在下面情况下插入11,这时候判断父叔,一个红一个黑,并且11满足右左(爷爷节点先右再左得到11)类型——>所以先右旋再左旋,然后它是一个折型的,同样以b为支撑点,因为左旋右旋是直线的,右旋对下面也就是c节点进行上移,然后b变为右下(右旋:11上面去了,12放到下面)

 

 

 右旋完毕,11到上面,12在下面,此时11节点变为右右类型,所以为什么说右左是先右旋再左旋就是这个道理

 继续左旋,11到上面去,10到下面去,然后变色

 

 

本文含有隐藏内容,请 开通VIP 后查看