二叉树的左旋和右旋

硅谷探秘者 3108 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;
	    }
	}


为后面的红黑树等做铺垫


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


猜你喜欢
数据结构与算法 3245 avl:AVL本质上是一颗查找1.avl性质高度之差绝对值不超过1每个都是AVL每个节点都有一个平衡因子(balancefactor--bf
weblog 1487 本篇文章为红黑预备知识,暂且不涉及节点颜色。 过程是将x绕x逆时针转,使得x成为x父节点,同时修改相关节点引用。转之后,查找属性仍然满足
数据结构与算法 6275 题目:判断下方两棵是否为例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
数据结构与算法 4089 整理遍历-(递归法)(非递归法)-笔记先序遍历、中序遍历、后续遍历、层级遍历。1.节点信息:packagetree;publicclassNodeE{ privateEe;//数据域
official 148 。本题中,一棵高度平衡定义为:一个每个节点两个子高度差绝对值不超过1。示例1案例输入:root=[3,9,20,null,null,15,7],输出:true示例2案例输入:r
official 127 一个head为第一个节点链表。如果在中,存在一条一直向下路径,且每个点数值恰好一一对应以head为首链表中每个节点值,那么请你返回True,否则返回False。一直向下路径意思
official 115 像顺时针转90度。你必须在原地转图像,这意味着你需要直接修改输入维矩阵。请不要使用另一个矩阵来转图像。示例1输入:matrix=[[1,2,3],[4,5,6],[7,8,9]] 输出:[[7
weblog 2929 什么是前驱节点后继节点?某节点前驱节点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
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo
目录