二叉树的左旋和右旋

硅谷探秘者 4897 0 0

在关于树的多种算法中都用到了树的旋转来使树保持相对平衡,比如avl树,红黑树等...

1.树的左旋(pivot为旋转中心点)

QQ截图20190106190453.png

2.来个动图

20180722220546910.gif

3.代码演示:

        /**
	 * 左旋
	 * p为旋转的中心点
	 */
	public void rotateLeft(Node<T,E> p) {
	    if (p != null) {
		Node<T,E> r = p.right;
	        p.right = r.left;
	        if (r.left != null)
	            r.left.parent = p;
	        r.parent = p.parent;
	        if (p.parent == null)
	            root = r;
	        else if (p.parent.left == p)
	            p.parent.left = r;
	        else
	            p.parent.right = r;
	        r.left = p;
	        p.parent = r;
	    }
	}

4.树的右旋(pivot为旋转中心点)

QQ截图20190106190855.png

5.动图演示:

1550028220533078315.gif

6.代码演示:

	/**
	 * 右旋
	 * p为旋转的中心点
	 */
	public void rotateRight(Node<T,E> p) {
	    if (p != null) {
	        Node<T,E> l = p.left;
	        p.left = l.right;
	        if (l.right != null) l.right.parent = p;
	        l.parent = p.parent;
	        if (p.parent == null)
	            root = l;
	        else if (p.parent.right == p)
	            p.parent.right = l;
	        else p.parent.left = l;
	        l.right = p;
	        p.parent = l;
	    }
	}


为后面的红黑树等做铺垫


图片来自于网络.........



评论区
请写下您的评论...
暂无评论...
猜你喜欢
数据结构与算法 4212 avl:AVL本质上是一颗查找1.avl性质高度之差绝对值不超过1每个都是AVL每个节点都有一个平衡因子(balancefactor--bf
weblog 3528 本篇文章为红黑预备知识,暂且不涉及节点颜色。 过程是将x绕x逆时针转,使得x成为x父节点,同时修改相关节点引用。转之后,查找属性仍然满足
数据结构与算法 7422 题目:判断下方两棵是否为例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
数据结构与算法 5158 整理遍历-(递归法)(非递归法)-笔记先序遍历、中序遍历、后续遍历、层级遍历。1.节点信息:packagetree;publicclassNodeE{ privateEe;//数据域
official 1023 。本题中,一棵高度平衡定义为:一个每个节点两个子高度差绝对值不超过1。示例1案例输入:root=[3,9,20,null,null,15,7],输出:true示例2案例输入:r
official 1211 一个head为第一个节点链表。如果在中,存在一条一直向下路径,且每个点数值恰好一一对应以head为首链表中每个节点值,那么请你返回True,否则返回False。一直向下路径意思
official 853 像顺时针转90度。你必须在原地转图像,这意味着你需要直接修改输入维矩阵。请不要使用另一个矩阵来转图像。示例1输入:matrix=[[1,2,3],[4,5,6],[7,8,9]] 输出:[[7
weblog 5656 什么是前驱节点后继节点?某节点前驱节点val值小于该节点val值并且值是最大那个节点。某节点后继节点val值大于该节点val值并且值是最小那个节点。下面给出一个节点类
归档
2018-11  12 2018-12  33 2019-01  28 2019-02  28 2019-03  32 2019-04  27 2019-05  33 2019-06  6 2019-07  12 2019-08  12 2019-09  21 2019-10  8 2019-11  15 2019-12  25 2020-01  9 2020-02  5 2020-03  16 2020-04  4 2020-06  1 2020-07  7 2020-08  13 2020-09  9 2020-10  5 2020-12  3 2021-01  1 2021-02  5 2021-03  7 2021-04  4 2021-05  4 2021-06  1 2021-07  7 2021-08  2 2021-09  8 2021-10  9 2021-11  16 2021-12  14 2022-01  7 2022-05  1 2022-08  3 2022-09  2 2022-10  2 2022-12  5 2023-01  3 2023-02  1 2023-03  4 2023-04  2 2023-06  3 2023-07  4 2023-08  1 2023-10  1 2024-02  1 2024-03  1 2024-04  1
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job rabbitmq haproxy srs 音视频 webrtc javascript
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。