avl树的旋转

硅谷探秘者 4066 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



评论区
请写下您的评论...
暂无评论...
猜你喜欢
数据结构与算法 4734 在关于多种算法中都用到了来使保持相对平衡,比如avl,红黑等...1.(pivot为中心点)2.来个动图3.代码演示:/** *左 *p为中心点
数据结构与算法 2942 packageavlTree;importjava.util.LinkedList;/***avl(平衡二叉)*@authorAdministrator**/publicclassAvlTree
official 764 像顺时针90度。你必须在原地图像,这意味着你需要直接修改输入二维矩阵。请不要使用另一个矩阵来图像。示例1输入:matrix=[[1,2,3],[4,5,6],[7,8,9]] 输出:[[7
weblog 3130 本篇文章为红黑预备知识,暂且不涉及节点颜色。 二叉过程是将x右子绕x逆时针,使得x右子成为x父节点,同时修改相关节点引用。之后,二叉查找属性仍然满足
数据结构与算法 3179 载:https://www.cnblogs.com/willwu/p/6007555.html1.定义是一种数据结构,它是由n(n=1)个有限节点组成一个具有层次关系集合。把它叫做“”是
weblog 4604 红黑简介 红黑(RedBlackTree)是一种自平衡二叉查找,是在计算机科学中用到一种数据结构,典型用途是实现关联数组。红黑AVL类似,都是在进行插入和删除操作时通过特定
数据结构与算法 7268 题目:判断下方两棵二叉右方二叉是否为左方二叉例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
official 1068 和一个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  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
标签
算法基础 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
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。