avl树的旋转

硅谷探秘者 3318 0 0


avl树:AVL树本质上是一颗二叉查找树

1.avl树的性质

        左子树和右子树的高度之差的绝对值不超过1

        树中的每个左子树和右子树都是AVL树

        每个节点都有一个平衡因子(balance factor--bf),任一节点的平衡因子是-1,0,1之一

2.avl树的操作

        AVL树的操作基本和二叉查找树一样,这里我们关注的是两个变化很大的操作:插入和删除

        AVL树不仅是一颗二叉查找树,它还有其他的性质。如果我们按照一般的二叉查找树的插入方式可能会破坏AVL树的平衡性。同理,在删除的时候也有可能会破坏树的平衡性,所以我们要做一些特殊的处理,包括:单旋转和双旋转!

/**
	 * 返回较大的值
	 * @param l
	 * @param r
	 * @return
	 */
	public int max(int l, int r){
	    return (l > r ? l : r);
	}
	/**
	 * 获取树高度
	 * @param n
	 * @return
	 */
	public int hight(Node<Integer> n) {
	    if(n==null)
	        return -1;
	    else
	        return n.high;
	}

3.单旋转:

单旋的第一种情况:右旋

	/**
	 * 整个树是右旋的单旋转
	 * @param head
	 * @return
	 */
	public Node<Integer> singleRotateRight(Node<Integer> head){
		Node<Integer> tmp = head.left;
	    head.left = tmp.right;
	    tmp.right = head; //旋转后深度随之变化,需要修改深度
	    head.high = max(hight(head.left), hight(head.right)) + 1;
	    tmp.high = max(hight(tmp.left), hight(tmp.right)) + 1;
	    return tmp;//返回新的子树根节点
	}


1.png

2.png

单旋的第二种情况:左旋

	/**
	 * 整个树是左旋的单旋转
	 * @param head
	 * @return
	 */
	public Node<Integer> singleRotateLeft(Node<Integer> head){
		Node<Integer> tmp = head.right;
	    head.right = tmp.left;
	    tmp.left = head;
	    head.high = max(hight(head.left), hight(head.right)) + 1;
	    tmp.high = max(hight(tmp.left), hight(tmp.right)) + 1;
	    return tmp;
	}


3.png

4.png

4.双旋转:

双旋的第一种情况:左右(先左后右)旋

	/**
	 * 整个树是右旋的双旋转
	 * @param head
	 * @return
	 */
	public Node<Integer> doubleRotateRight(Node<Integer> head){
	    head.left = singleRotateLeft(head.left);
	    return singleRotateRight(head);//再将整个树左旋
	}


5.png

6.png

双旋的第二种情况:右左(先右后左)旋

	/**
	 * 整个树是左旋的双旋转
	 * @param head
	 * @return
	 */
	public Node<Integer> doubleRotateLeft(Node<Integer> head){
	    head.right = singleRotateRight(head.right);
	    return singleRotateLeft(head);//再将整个树右旋
	}


7.png

8.png


猜你喜欢
数据结构与算法 3330 在关于多种算法中都用到了来使保持相对平衡,比如avl,红黑等...1.(pivot为中心点)2.来个动图3.代码演示:/** *左 *p为中心点
数据结构与算法 2176 packageavlTree;importjava.util.LinkedList;/***avl(平衡二叉)*@authorAdministrator**/publicclassAvlTree
official 175 像顺时针90度。你必须在原地图像,这意味着你需要直接修改输入二维矩阵。请不要使用另一个矩阵来图像。示例1输入:matrix=[[1,2,3],[4,5,6],[7,8,9]] 输出:[[7
weblog 1633 本篇文章为红黑预备知识,暂且不涉及节点颜色。 二叉过程是将x右子绕x逆时针,使得x右子成为x父节点,同时修改相关节点引用。之后,二叉查找属性仍然满足
数据结构与算法 2508 载:https://www.cnblogs.com/willwu/p/6007555.html1.定义是一种数据结构,它是由n(n=1)个有限节点组成一个具有层次关系集合。把它叫做“”是
weblog 2906 红黑简介 红黑(RedBlackTree)是一种自平衡二叉查找,是在计算机科学中用到一种数据结构,典型用途是实现关联数组。红黑AVL类似,都是在进行插入和删除操作时通过特定
数据结构与算法 6388 题目:判断下方两棵二叉右方二叉是否为左方二叉例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
official 216 和一个head为第一个节点链表。如果在二叉中,存在一条一直向下路径,且每个点数值恰好一一对应以head为首链表中每个节点值,那么请你返回True,否则返回False。一直向下路径意思
归档
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月  6
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议
目录
祝愿神州十三飞行乘组平安归来