AVL树的讲解

算法拾遗三十八AVL树

      • AVL树
        • AVL树平衡性
        • AVL树加入节点
        • AVL删除节点
        • AVL树代码

AVL树

AVL树具有最严苛的平衡性，（增、删、改、查）时间复杂度为O（logN），AVL树任何一个节点，左树的高度和右树的高度差不超过1（<2）
和SB树，红黑树时间复杂度一样，只是不同的人搞出了不同的平衡性。
AVL树就是一颗搜索二叉树和搜索二叉树的区别主要是做完属于搜索二叉树的调整之后有专属于自己平衡性的补丁。
搜索二叉树加节点，则小于根节点的挂左边，大于根节点的挂右边
搜索二叉树删除节点分情况：
1、当找到了要删除的节点X之后，X既没有左子树也没有右子树，则直接删除
2、找到了要删除的节点X之后，X有左但无右，那么直接让这个删除节点的X的左子树完全替代X
3、如果要删除的节点X，X无左有右，那么直接让右子树替代X
4、如果要删除的X既有左又有右，可以找左树的最右节点（最大节点）或者右树的最左节点（最小节点）代替X

AVL树平衡性

破坏平衡性操作：
LL：
在这里插入图片描述
需要调整为如下：
在这里插入图片描述
LR：
在这里插入图片描述
同理还有RR和RL型违规破坏平衡性。

如下图（LR型违规：只要是LR型违规。则让那个孙节点跑上去保持平衡）：
在这里插入图片描述
可知树的不平衡原因为：B的右子树导致的整棵树不平衡，则需要让C来到A节点的位置，那么需要在BC这棵树上对B来一个左旋，得到下图结果：
在这里插入图片描述
然后再对A来一个右旋C就上去了：
在这里插入图片描述
RL型违规：
在这里插入图片描述
则让它的孙子节点顶上来就完事了，先在B上面执行一个右旋，让C顶上来，再在整棵树上执行一个A的左旋那么最后的C就上来了。

有一个细节：
有没有可能既是LL型违规又是LR型违规：
一棵树的左子树对应的左子树高度和这棵树的右子树对应的右子树高度一样所造成的不平衡是LL和LR型违规
在这里插入图片描述
如上图假设平衡二叉树左树高度为7右树高度为6，在某个时间右树删除一个数导致右树高度为5了，B的左树和右树高度都是6，我的失误既来自LL型又来自LR型
在这里插入图片描述
此时一定要按照LL型来调整，直接右旋(总能保证有效)。

如果用LR的方式来调整，则可能不对：有如下图
在这里插入图片描述
A的左树高度是7A的右树高度为5，如果这个例子按照LL型调整：会发现这棵树的高度是异常平衡的
在这里插入图片描述
如果按照LR方式来调整：如果将S的高度调整成4的话
这样调整出来的K，S则不平了
在这里插入图片描述
再来一个不平衡的：
在这里插入图片描述
按照LR方式进行调整，z替代y的位置
在这里插入图片描述
y接受了z的左空子树，y的右边是没有东西的，最后调整成这样：
在这里插入图片描述
综上：
总结：LL型违规只用进行一次右旋，LR型违规则需要进行一次小范围的左旋，再执行整棵树的右旋，RL型违规则需要先进行小范围上的右旋，再进行整棵树的左旋，RR型只需要进行一次左旋，时间复杂度均为O（1）

AVL树加入节点

加入一个节点之后需要依次查询加入的节点中了哪种类型的违规，如果未找到违规则找其对应的父节点，如果父节点未违规则继续找父节点对应的父节点，一直找到根节点未违规为止。
所以AVL树调整不是只对一个节点查是沿途所有节点都需要查（防止旋转一次后其上的节点还需要旋转），整体时间复杂度为O（logN）的调整代价，

如下图加入一个节点X首先看当前X节点是平的，再看X对应的父节点也是平的，最终找到方框标记的节点发现不再平衡了，左树高度为1，右树高度为3，而且是RR型违规
在这里插入图片描述
则需要进行左旋
在这里插入图片描述

AVL删除节点

分为以下情况：
1、X节点既没有左也没有右子树，这种情况只需要从删除节点开始算上面每一个父都要全查一遍。
2、X节点有右无左，直接拿右孩子替换原来的X，然后从右孩子来到的位置往上查询一遍
3、X节点既有左又有右孩子，看如下例子
在这里插入图片描述
如果此处要删掉7，则需要找到7对应右孩子的最小值8去替换7的位置，调整成如下图的样子，此时只需要从9开始查它的父节点依次调整即可，
在这里插入图片描述

AVL树代码

右旋步骤：
在这里插入图片描述

1、当前树的左边去接管左孩子的右
在这里插入图片描述
2、左孩子的右会接管cur
在这里插入图片描述
参照代码：

	//右旋
		private AVLNode<K, V> rightRotate(AVLNode<K, V> cur) {
			//记录左孩子
			AVLNode<K, V> left = cur.l;
			//左孩子的右树挂载当前树的左边
			cur.l = left.r;
			//左孩子的右接管cur
			left.r = cur;
			//高度也得接管（现在左孩子和右孩子的高度最大的那个再加1）
			cur.h = Math.max((cur.l != null ? cur.l.h : 0), (cur.r != null ? cur.r.h : 0)) + 1;
			left.h = Math.max((left.l != null ? left.l.h : 0), (left.r != null ? left.r.h : 0)) + 1;
			//右旋以left做头节点返回
			return left;
		}

再看AVL树add节点：
当前来到cur节点，要加的key是啥要加的value是啥，搜索二叉树潜台词为加入的key都不一样

public class Code_AVLTreeMap {

	public static class AVLNode<K extends Comparable<K>, V> {
		public K k;
		public V v;
		//左孩子及右孩子
		public AVLNode<K, V> l;
		public AVLNode<K, V> r;
		//高度
		public int h;

		public AVLNode(K key, V value) {
			k = key;
			v = value;
			h = 1;
		}
	}

	public static class AVLTreeMap<K extends Comparable<K>, V> {
		//根节点
		private AVLNode<K, V> root;
		//一共加入多少个节点
		private int size;

		public AVLTreeMap() {
			root = null;
			size = 0;
		}

		//右旋
		private AVLNode<K, V> rightRotate(AVLNode<K, V> cur) {
			//记录左孩子
			AVLNode<K, V> left = cur.l;
			//左孩子的右树挂载当前树的左边
			cur.l = left.r;
			//左孩子的右接管cur
			left.r = cur;
			//高度也得接管（现在左孩子和右孩子的高度最大的那个再加1）
			cur.h = Math.max((cur.l != null ? cur.l.h : 0), (cur.r != null ? cur.r.h : 0)) + 1;
			left.h = Math.max((left.l != null ? left.l.h : 0), (left.r != null ? left.r.h : 0)) + 1;
			//右旋以left做头节点返回
			return left;
		}

		//左旋
		private AVLNode<K, V> leftRotate(AVLNode<K, V> cur) {
			AVLNode<K, V> right = cur.r;
			cur.r = right.l;
			right.l = cur;
			cur.h = Math.max((cur.l != null ? cur.l.h : 0), (cur.r != null ? cur.r.h : 0)) + 1;
			right.h = Math.max((right.l != null ? right.l.h : 0), (right.r != null ? right.r.h : 0)) + 1;
			return right;
		}

		//平衡性调整
		private AVLNode<K, V> maintain(AVLNode<K, V> cur) {
			if (cur == null) {
				return null;
			}
			int leftHeight = cur.l != null ? cur.l.h : 0;
			int rightHeight = cur.r != null ? cur.r.h : 0;
			//此时左右树高度差大于1不平衡了
			if (Math.abs(leftHeight - rightHeight) > 1) {
				//左树高还是右树高
				if (leftHeight > rightHeight) {
					//左树高
					int leftLeftHeight = cur.l != null && cur.l.l != null ? cur.l.l.h : 0;
					int leftRightHeight = cur.l != null && cur.l.r != null ? cur.l.r.h : 0;
					//左树的左树高度大于等于右树的右树高度则LL型
					if (leftLeftHeight >= leftRightHeight) {
						//LL型违规
						cur = rightRotate(cur);
					} else {
						//LR型违规
						cur.l = leftRotate(cur.l);
						cur = rightRotate(cur);
					}
				} else {
					int rightLeftHeight = cur.r != null && cur.r.l != null ? cur.r.l.h : 0;
					int rightRightHeight = cur.r != null && cur.r.r != null ? cur.r.r.h : 0;
					if (rightRightHeight >= rightLeftHeight) {
						//RR
						cur = leftRotate(cur);
					} else {
						//RL
						cur.r = rightRotate(cur.r);
						cur = leftRotate(cur);
					}
				}
			}
			return cur;
		}

		private AVLNode<K, V> findLastIndex(K key) {
			AVLNode<K, V> pre = root;
			AVLNode<K, V> cur = root;
			while (cur != null) {
				pre = cur;
				if (key.compareTo(cur.k) == 0) {
					break;
				} else if (key.compareTo(cur.k) < 0) {
					cur = cur.l;
				} else {
					cur = cur.r;
				}
			}
			return pre;
		}

		private AVLNode<K, V> findLastNoSmallIndex(K key) {
			AVLNode<K, V> ans = null;
			AVLNode<K, V> cur = root;
			while (cur != null) {
				if (key.compareTo(cur.k) == 0) {
					ans = cur;
					break;
				} else if (key.compareTo(cur.k) < 0) {
					ans = cur;
					cur = cur.l;
				} else {
					cur = cur.r;
				}
			}
			return ans;
		}

		private AVLNode<K, V> findLastNoBigIndex(K key) {
			AVLNode<K, V> ans = null;
			AVLNode<K, V> cur = root;
			while (cur != null) {
				if (key.compareTo(cur.k) == 0) {
					ans = cur;
					break;
				} else if (key.compareTo(cur.k) < 0) {
					cur = cur.l;
				} else {
					ans = cur;
					cur = cur.r;
				}
			}
			return ans;
		}

		//AVL树加节点
		private AVLNode<K, V> add(AVLNode<K, V> cur, K key, V value) {
			if (cur == null) {
				//如果当前树为null，则新建节点
				return new AVLNode<K, V>(key, value);
			} else {
				//如果key小于当前树的k
				if (key.compareTo(cur.k) < 0) {
					//我去左树上面找，头部调整为当前节点的左树
					//之所以用cur.l = xxx 是因为这条记录挂在左树上是可能换头的
					//需要将返回值由我的头指针的左子树重新指一下接住
					cur.l = add(cur.l, key, value);
				} else {
					//右树上挂
					cur.r = add(cur.r, key, value);
				}
				//我自己的高度调整对
				cur.h = Math.max(cur.l != null ? cur.l.h : 0, cur.r != null ? cur.r.h : 0) + 1;
				//做平衡调整
				return maintain(cur);
			}
		}

		// 在cur这棵树上，删掉key所代表的节点
		// 返回cur这棵树的新头部
		private AVLNode<K, V> delete(AVLNode<K, V> cur, K key) {
			if (key.compareTo(cur.k) > 0) {
				cur.r = delete(cur.r, key);
			} else if (key.compareTo(cur.k) < 0) {
				cur.l = delete(cur.l, key);
			} else {
				if (cur.l == null && cur.r == null) {
					cur = null;
				} else if (cur.l == null && cur.r != null) {
					cur = cur.r;
				} else if (cur.l != null && cur.r == null) {
					cur = cur.l;
				} else {
					AVLNode<K, V> des = cur.r;
					while (des.l != null) {
						des = des.l;
					}
					//调用右树删除整个k，同时调整了平衡
					cur.r = delete(cur.r, des.k);
					des.l = cur.l;
					des.r = cur.r;
					cur = des;
				}
			}
			if (cur != null) {
				cur.h = Math.max(cur.l != null ? cur.l.h : 0, cur.r != null ? cur.r.h : 0) + 1;
			}
			return maintain(cur);
		}

		public int size() {
			return size;
		}

		public boolean containsKey(K key) {
			if (key == null) {
				return false;
			}
			AVLNode<K, V> lastNode = findLastIndex(key);
			return lastNode != null && key.compareTo(lastNode.k) == 0 ? true : false;
		}

		public void put(K key, V value) {
			if (key == null) {
				return;
			}
			AVLNode<K, V> lastNode = findLastIndex(key);
			if (lastNode != null && key.compareTo(lastNode.k) == 0) {
				lastNode.v = value;
			} else {
				size++;
				root = add(root, key, value);
			}
		}

		public void remove(K key) {
			if (key == null) {
				return;
			}
			if (containsKey(key)) {
				size--;
				root = delete(root, key);
			}
		}

		public V get(K key) {
			if (key == null) {
				return null;
			}
			AVLNode<K, V> lastNode = findLastIndex(key);
			if (lastNode != null && key.compareTo(lastNode.k) == 0) {
				return lastNode.v;
			}
			return null;
		}

		public K firstKey() {
			if (root == null) {
				return null;
			}
			AVLNode<K, V> cur = root;
			while (cur.l != null) {
				cur = cur.l;
			}
			return cur.k;
		}

		public K lastKey() {
			if (root == null) {
				return null;
			}
			AVLNode<K, V> cur = root;
			while (cur.r != null) {
				cur = cur.r;
			}
			return cur.k;
		}

		public K floorKey(K key) {
			if (key == null) {
				return null;
			}
			AVLNode<K, V> lastNoBigNode = findLastNoBigIndex(key);
			return lastNoBigNode == null ? null : lastNoBigNode.k;
		}

		public K ceilingKey(K key) {
			if (key == null) {
				return null;
			}
			AVLNode<K, V> lastNoSmallNode = findLastNoSmallIndex(key);
			return lastNoSmallNode == null ? null : lastNoSmallNode.k;
		}

	}

}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/82011.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【操作系统】虚拟内存相关分段分页页面置换算法

【操作系统】虚拟内存相关分段分页页面置换算法

虚拟内存是什么&#xff1f; 【进程地址空间虚拟地址空间C/C程序地址空间就是那个4G的空间】 虚拟内存是操作系统内核为了对进程地址空间进行管理&#xff0c;而设计的一个逻辑意义上的内存空间概念。在程序运行过程中&#xff0c;虚拟内存中需要被访问的部分会被映射到物理内…
阅读更多...
JVM元空间溢出的排除思路

JVM元空间溢出的排除思路

背景&#xff1a; java的应用我们为了防止元空间的无限扩展&#xff0c;一般都会设置MaxMetaSpace参数&#xff0c;一般来说只要这个值是512M或者1G左右就足够了&#xff0c;不过今天遇到一个meta空间溢出问题&#xff0c;简单记录下排除的思路 meta元空间溢出 最开始的现象…
阅读更多...
ARM--day6(实现字符、字符串收发的代码和现象，分析RCC、GPIO、UART章节)

ARM--day6(实现字符、字符串收发的代码和现象，分析RCC、GPIO、UART章节)

uart4.h #ifndef __UART4_H__ #define __UART4_H__#include "stm32mp1xx_rcc.h" #include "stm32mp1xx_gpio.h" #include "stm32mp1xx_uart.h"//RCC/GPIO/UART4章节初始化 void hal_uart4_init();//发送一个字符函数 void hal_put_char(const c…
阅读更多...
简单理解Linux中的一切皆文件

简单理解Linux中的一切皆文件

一款操作系统要管理各种各样不同的硬件&#xff0c;因为硬件的不同所以它们使用的文件系统也不同。但是按道理来说&#xff0c;文件系统的不同对于用户来说可不是一件好事&#xff0c;操作不同的硬件就要使用不同的方法。 但是Linux有一切皆文件。 简单来说&#xff0c;Linux…
阅读更多...
Android 多渠道打包及VasDolly使用

Android 多渠道打包及VasDolly使用

目录 1.添加productFlavors的配置buildConfigFieldmanifestPlaceholdersresValue 2.设置apk文件的名称&#xff0c;便于识别3.添加vasdolly、添加gradle脚本&#xff08;windows&#xff09; 作用&#xff1a;一次性可以打多个apk包&#xff0c;名字、包名、logo等可以不相同。…
阅读更多...
Java调用https接口添加证书

Java调用https接口添加证书

使用InstallCert.Java生成证书 /** Copyright 2006 Sun Microsystems, Inc. All Rights Reserved.** Redistribution and use in source and binary forms, with or without* modification, are permitted provided that the following conditions* are met:** - Redistri…
阅读更多...
R语言实现非等比例风险生存资料分析（1）

R语言实现非等比例风险生存资料分析（1）

#非等比例风险的生存资料分析 ###1 生成模拟数据### library(flexsurv) set.seed(123) # 生成样本数量 n <- 100 # 生成时间数据 time <- sample(1:1000,n,replaceF) # 调整shape和scale参数以控制生存曲线形状 # 生成事件数据&#xff08;假设按比例风险模型&#xff0…
阅读更多...
透视俄乌网络战之一：数据擦除软件

透视俄乌网络战之一：数据擦除软件

数据擦除破坏 1. WhisperGate2. HermeticWiper3. IsaacWiper4. WhisperKill5. CaddyWiper6. DoubleZero7. AcidRain8. RURansom 数据是政府、社会和企业组织运行的关键要素。数据擦除软件可以在不留任何痕迹的情况下擦除数据并阻止操作系统恢复摧&#xff0c;达到摧毁或目标系统…
阅读更多...
C++------利用C++实现二叉搜索树【数据结构】

C++------利用C++实现二叉搜索树【数据结构】

文章目录 二叉搜索树概念二叉搜索树的操作查找插入删除 二叉搜索树的应用 二叉搜索树 概念 什么是二叉搜索树&#xff0c;二叉搜索树就是指左孩子永远比根小右孩子永远比根大。这个规则适用于所有的子树。 上面的就是一棵二叉搜索树&#xff0c;我们还可以发现这棵树走一个中…
阅读更多...
stm32开关控制led灯泡（附Proteus电路图）

stm32开关控制led灯泡（附Proteus电路图）

说明&#xff1a;我的灯泡工作电压2V&#xff0c;电流设置为10um,注意了不是10毫安时微安啊&#xff0c;要不然电流太小亮不起来的。 2&#xff1a;我用的开关不是按钮button而是switch, 3&#xff1a;PB0,PB1默认都是低电平&#xff0c;采用了PULLDOWN模式&#xff0c;如果设…
阅读更多...
【排序】插入排序 希尔排序（改进）

【排序】插入排序 希尔排序（改进）

文章目录 插入排序时间复杂度空间复杂度 代码希尔排序时间复杂度空间复杂度 代码 以从小到大排序为例进行说明。 插入排序 插入排序就是从前向后&#xff08;i1开始&#xff09;进行选择&#xff0c;如果找到在i之前&#xff08;分配一个j下标进行寻找&#xff09;有比array[i…
阅读更多...
uniapp选择只选择月份demo效果（整理）

uniapp选择只选择月份demo效果（整理）

<template><view style"margin-top: 200rpx;"><!-- mode"multiSelector" 多列选择器 --><view><picker :range"years" :value"echoVal" change"yearChange" mode"multiSelector">{…
阅读更多...
Android Studio 新建module报错：No signature of method

Android Studio 新建module报错：No signature of method

android平台uni原生插件开发过程中&#xff0c;使用Android Studio 新增 module 报错 选择app --> create new module &#xff0c;填写相关信息 Android Studio 新建module报错&#xff1a; 原因&#xff1a;Android Studio 版本过高&#xff0c;新增了namespace&#x…
阅读更多...
Elasticsearch复合查询之Boosting Query

Elasticsearch复合查询之Boosting Query

前言 ES 里面有 5 种复合查询&#xff0c;分别是&#xff1a; Boolean QueryBoosting QueryConstant Score QueryDisjunction Max QueryFunction Score Query Boolean Query在之前已经介绍过了&#xff0c;今天来看一下 Boosting Query 用法&#xff0c;其实也非常简单&…
阅读更多...
轻松搭建书店小程序

轻松搭建书店小程序

在现今数字化时代&#xff0c;拥有一个自己的小程序成为了许多企业和个人的追求。而对于书店经营者来说&#xff0c;拥有一个能够提供在线购书服务的小程序将有助于吸引更多的读者&#xff0c;并提升销售额。本文将为您介绍如何轻松搭建书店小程序&#xff0c;并将其成功上线。…
阅读更多...
B树和B+树MySQL为什么用B+树?

B树和B+树MySQL为什么用B+树?

文章目录 B树和B树B树B树的定义B树的插入操作删除操作 B树B树的定义B树的插入操作删除操作 B树和B树的区别?MySQL数据库为啥用B树作为索引&#xff0c;而不用B树? B树和B树 原文链接&#xff1a;https://blog.csdn.net/jinking01/article/details/115130286 B树 B树的定义…
阅读更多...
NLP序列标注问题，样本不均衡怎么解决？

NLP序列标注问题，样本不均衡怎么解决？

【学而不思则罔&#xff0c;思而不学则殆】 1.问题 NLP序列标注问题&#xff0c;样本不均衡怎么解决&#xff1f; 2.解释 以命名实体识别&#xff08;NER&#xff09;为例&#xff0c;这个样本不均衡有两种解释&#xff1a; &#xff08;1&#xff09;实体间类别数量不均衡…
阅读更多...
关于vant2 组件van-dropdown-item，在IOS手机上，特定条件下无法点击问题的探讨

关于vant2 组件van-dropdown-item，在IOS手机上，特定条件下无法点击问题的探讨

情景重现 先贴有问题的代码 <template><div :class"showBar ? homeContain : homeContain-nobar"><div class"contant" id"content"><van-dialog v-model"loading" :before-close"onBeforeClose" :…
阅读更多...
【Python从入门到进阶】32、bs4的基本使用

【Python从入门到进阶】32、bs4的基本使用

接上篇《31、使用JsonPath解析淘票票网站地区接口数据》 上一篇我们介绍了如何使用JSONPath来解析淘票票网站的地区接口数据&#xff0c;本篇我们来学习BeautifulSoup的基本概念&#xff0c;以及bs4的基本使用。 一、BeautifulSoup简介 1、bs4基本概念 BeautifulSoup是一个P…
阅读更多...
.Net Core 动态加载和卸载程序集

.Net Core 动态加载和卸载程序集

从 .Net Core 3.0开始支持程序集的加载和卸载&#xff0c;在 .Net FrameWork中使用独立的应用程序域来实现同样的功能&#xff0c;.Net Core 不支持创建多个应用程序域&#xff0c;所以无法使用多个应用程序域来实现程序集动态加载和卸载。 AssemblyLoadContext 程序集加载上下…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站