您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

数据结构 --- AVL树

时间:2022-03-15 11:06:35  来源:  作者:程序驱动世界

AVL(Adelson-Velsky and Landis Tree) 树是一种自平衡二叉树, 也是最早发明的一种自动平衡二叉树。原因是由于BST(二叉搜索树)在用有序列表不断插入时会退化成链表而大大影响其效率,因此最早计算机科学家G. M. Adelson-Velsky和Evgenii Landis在1962年发明了AVL树。首先要明确AVL树是一种二叉搜索树(BST),不了解BST的同学可以看我之前的一篇文章<<数据结构---二叉搜索树>>。AVL树中的任意节点的两颗子树高度差<=1。因此AVL树是高度平衡的。如下图所示的就是一颗AVL树。每个节点都标注了其高度。

数据结构 --- AVL树

 

在AVL树中把每个节点的左子树高度减去其右子树高度差定义为平衡因子。在AVL树中只有平衡因子大于等于-1并且小于等于1才是平衡的。因此平衡因子只能取3个值-1, 0和1。平衡因子取其它值被认为是不平衡的,就需要对该AVL树进行调整,以使其达到平衡。

当一颗AVL树不平衡时,我们需要对其进行一系列操作使其保持平衡,下面介绍AVL树的基本操作。

  1. 左旋
数据结构 --- AVL树

 

上图是节点的原始状态,绕y节点进行左旋的步骤如下:

  • 如果β不为空将β的parent设为x,同时将x的右孩子设为β。
数据结构 --- AVL树

 

  • 如果p是NULL,将y设为根节点。
  • 否则如果x是p的左孩子,将y设为p的左孩子
  • 否则将y设为p的右孩子
  • 将p设为y的父节点
数据结构 --- AVL树

 

  • 将y设为x的父节点,将x设为y的左孩子,完成左旋。
数据结构 --- AVL树

 

  1. 右旋
数据结构 --- AVL树

 

上图是节点的原始状态,绕x节点进行右旋的步骤如下:

  • 如果β不为空,将β的父节点设为y,同时将y的左孩子设为β。
数据结构 --- AVL树

 

  • 如果p是NULL,将x设为根节点
  • 否则,如果y是p的右孩子,将p的右孩子设为x
  • 否则,将p的左孩子设为x
  • 将x的父节点设为p
数据结构 --- AVL树

 

  • 将x设为y的父节点,将y设为x的右孩子,完成右旋
数据结构 --- AVL树

 

  1. 左右旋转(LR)

如下图,左右旋转是将x以y为中心左旋。

数据结构 --- AVL树

 

然后再以y为中心对z进行右旋,完成平衡调整。

数据结构 --- AVL树

 

  1. 右左旋转(RL)

如下图,先以y为中心对x进行右旋。

数据结构 --- AVL树

 

然后再以y为中心对z进行左旋,完成平衡调整。

数据结构 --- AVL树

 

上面我们介绍了AVL树的基本操作,下面我们介绍AVL树的插入和删除算法。

  1. 插入算法

假设当前AVL树的初始状态如下图所示:

数据结构 --- AVL树

 

上图所示的AVL数每个节点的值和平衡因子都标了出来。它现在处于平衡状态,因为它的每个节点的平衡因子(左子树高度减去右子树高度的值)都满足要求(大于等于-1并且小于等于1)。现在假设我插入一个值为9的节点,我们来分步看看插入算法的整个过程。

  • 首先按照BST的插入算法,插入值为9的节点。插入后,如下图所示:
数据结构 --- AVL树

 

  • 可以看到,上面的树不再平衡,因为树中有三个节点的平衡因子为2,所以需要对其进行调整使其满足AVL树的性质。调整如下:

看下图棕色虚线框的部分,也就是插入节点后导致不平衡的部分,它满足左右旋转的特点。因此对其进行左右旋转。

数据结构 --- AVL树

 

左右旋转后得到下图:

数据结构 --- AVL树

 

从上图可以看出,该AVL树已经平衡。

  1. 删除算法

从AVL树中删除一个节点,可以按照BST删除节点的方法先删除该节点,由于删除后AVL树可能不平衡,因此需要进行调整。假设要删除下面这颗AVL树的值为13的节点。删除过程如下:

数据结构 --- AVL树

 

  • 按照BST的方法删除值为13的节点,删除后结果如下图所示:
数据结构 --- AVL树

 

  • 重新计算各个节点的平衡因子,如下图所示:
数据结构 --- AVL树

 

值为21的节点平衡因子为2,因此需要调整。

  • 调整该AVL数,使其平衡。
数据结构 --- AVL树

 

以上图中棕色框值为9的节点为中心,将值为21的节点右旋,右旋后得到下图:

数据结构 --- AVL树

 

再对上图的各个节点重新计算平衡因子得到下图:

数据结构 --- AVL树

 

从上图可以看出,各个节点的平衡因子均大于等-1并且小于等于1,所以调整完成。该AVL数达到平衡状态。

对于AVL数的遍历,查找均和BST树一样,不再介绍,同学们可以参考我之前的文章<<数据结构---二叉搜索树>>。

下面是AVL树的Python/ target=_blank class=infotextkey>Python代码实现:

# AVL tree implementation in Python

import sys

# Create a tree node

class TreeNode(object):

def __init__(self, key):

self.key = key

self.left = None

self.right = None

self.height = 1

class AVLTree(object):

# Function to insert a node

def insert_node(self, root, key):

# Find the correct location and insert the node

if not root:

return TreeNode(key)

elif key < root.key:

root.left = self.insert_node(root.left, key)

else:

root.right = self.insert_node(root.right, key)

root.height = 1 + max(self.getHeight(root.left),

self.getHeight(root.right))

# Update the balance factor and balance the tree

balanceFactor = self.getBalance(root)

if balanceFactor > 1:

if key < root.left.key:

return self.rightRotate(root)

else:

root.left = self.leftRotate(root.left)

return self.rightRotate(root)

if balanceFactor < -1:

if key > root.right.key:

return self.leftRotate(root)

else:

root.right = self.rightRotate(root.right)

return self.leftRotate(root)

return root

# Function to delete a node

def delete_node(self, root, key):

# Find the node to be deleted and remove it

if not root:

return root

elif key < root.key:

root.left = self.delete_node(root.left, key)

elif key > root.key:

root.right = self.delete_node(root.right, key)

else:

if root.left is None:

temp = root.right

root = None

return temp

elif root.right is None:

temp = root.left

root = None

return temp

temp = self.getMinValueNode(root.right)

root.key = temp.key

root.right = self.delete_node(root.right,

temp.key)

if root is None:

return root

# Update the balance factor of nodes

root.height = 1 + max(self.getHeight(root.left),

self.getHeight(root.right))

balanceFactor = self.getBalance(root)

# Balance the tree

if balanceFactor > 1:

if self.getBalance(root.left) >= 0:

return self.rightRotate(root)

else:

root.left = self.leftRotate(root.left)

return self.rightRotate(root)

if balanceFactor < -1:

if self.getBalance(root.right) <= 0:

return self.leftRotate(root)

else:

root.right = self.rightRotate(root.right)

return self.leftRotate(root)

return root

# Function to perform left rotation

def leftRotate(self, z):

y = z.right

T2 = y.left

y.left = z

z.right = T2

z.height = 1 + max(self.getHeight(z.left),

self.getHeight(z.right))

y.height = 1 + max(self.getHeight(y.left),

self.getHeight(y.right))

return y

# Function to perform right rotation

def rightRotate(self, z):

y = z.left

T3 = y.right

y.right = z

z.left = T3

z.height = 1 + max(self.getHeight(z.left),

self.getHeight(z.right))

y.height = 1 + max(self.getHeight(y.left),

self.getHeight(y.right))

return y

# Get the height of the node

def getHeight(self, root):

if not root:

return 0

return root.height

# Get balance factore of the node

def getBalance(self, root):

if not root:

return 0

return self.getHeight(root.left) - self.getHeight(root.right)

def getMinValueNode(self, root):

if root is None or root.left is None:

return root

return self.getMinValueNode(root.left)

def preOrder(self, root):

if not root:

return

print("{0} ".format(root.key), end="")

self.preOrder(root.left)

self.preOrder(root.right)

# Print the tree

def printHelper(self, currPtr, indent, last):

if currPtr != None:

sys.stdout.write(indent)

if last:

sys.stdout.write("R----")

indent += " "

else:

sys.stdout.write("L----")

indent += "| "

print(currPtr.key)

self.printHelper(currPtr.left, indent, False)

self.printHelper(currPtr.right, indent, True)

myTree = AVLTree()

root = None

nums = [33, 13, 52, 9, 21, 61, 8, 11]

for num in nums:

root = myTree.insert_node(root, num)

myTree.printHelper(root, "", True)

key = 13

root = myTree.delete_node(root, key)

print("After Deletion: ")

myTree.printHelper(root, "", True)



Tags:AVL树   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
一文搞懂二叉搜索树、B树、B+树、AVL树、红黑树
我们假设B+树一个节点可以有100个关键字,那么3层的B树可以容纳大概1000000多个关键字(100+101100+101101*100)。而红黑树要存储这么多至少要20层。所以使用B树相对于红黑树和A...【详细内容】
2023-08-29  Search: AVL树  点击:(411)  评论:(0)  加入收藏
数据结构 --- AVL树
AVL(Adelson-Velsky and Landis Tree) 树是一种自平衡二叉树, 也是最早发明的一种自动平衡二叉树。原因是由于BST(二叉搜索树)在用有序列表不断插入时会退化成链表而大大影...【详细内容】
2022-03-15  Search: AVL树  点击:(348)  评论:(0)  加入收藏
▌简易百科推荐
小红书、视频号、抖音流量算法解析,干货满满,值得一看!
咱们中国现在可不是一般的牛!网上的网友已经破了十个亿啦!到了这个互联网的新时代,谁有更多的人流量,谁就能赢得更多的掌声哦~抖音、小红书、、视频号,是很多品牌必争的流量洼地...【详细内容】
2024-02-23  二手车小胖说    Tags:流量算法   点击:(17)  评论:(0)  加入收藏
雪花算法详解与Java实现:分布式唯一ID生成原理
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2024-02-03   一安未来  微信公众号  Tags:雪花算法   点击:(53)  评论:(0)  加入收藏
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  架构师老卢  今日头条  Tags:算法   点击:(46)  评论:(0)  加入收藏
百度推荐排序技术的思考与实践
本文将分享百度在推荐排序方面的思考与实践。在整个工业界的推广搜场景上,特征设计通常都是采用离散化的设计,需要保证两方面的效果,一方面是记忆,另一方面是泛化。特征都是通过...【详细内容】
2024-01-09  DataFunTalk  微信公众号  Tags:百度推荐   点击:(78)  评论:(0)  加入收藏
什么是布隆过滤器?如何实现布隆过滤器?
以下我们介绍了什么是布隆过滤器?它的使用场景和执行流程,以及在 Redis 中它的使用,那么问题来了,在日常开发中,也就是在 Java 开发中,我们又将如何操作布隆过滤器呢?布隆过滤器(Blo...【详细内容】
2024-01-05  Java中文社群  微信公众号  Tags:布隆过滤器   点击:(91)  评论:(0)  加入收藏
面向推荐系统的深度强化学习算法研究与应用
随着互联网的快速发展,推荐系统在各个领域中扮演着重要的角色。传统的推荐算法在面对大规模、复杂的数据时存在一定的局限性。为了解决这一问题,深度强化学习算法应运而生。本...【详细内容】
2024-01-04  数码小风向    Tags:算法   点击:(100)  评论:(0)  加入收藏
非负矩阵分解算法:从非负数据中提取主题、特征等信息
非负矩阵分解算法(Non-negativeMatrixFactorization,简称NMF)是一种常用的数据分析和特征提取方法,主要用于从非负数据中提取主题、特征等有意义的信息。本文将介绍非负矩阵分解...【详细内容】
2024-01-02  毛晓峰    Tags:算法   点击:(72)  评论:(0)  加入收藏
再谈前端算法,你这回明白了吗?
楔子 -- 青蛙跳台阶一只青蛙一次可以跳上一级台阶,也可以跳上二级台阶,求该青蛙跳上一个n级的台阶总共需要多少种跳法。分析: 当n=1的时候,①只需要跳一次即可;只有一种跳法,即f(...【详细内容】
2023-12-28  前端爱好者  微信公众号  Tags:前端算法   点击:(111)  评论:(0)  加入收藏
三分钟学习二分查找
二分查找是一种在有序数组中查找元素的算法,通过不断将搜索区域分成两半来实现。你可能在日常生活中已经不知不觉地使用了大脑里的二分查找。最常见的例子是在字典中查找一个...【详细内容】
2023-12-22  小技术君  微信公众号  Tags:二分查找   点击:(79)  评论:(0)  加入收藏
强化学习算法在资源调度与优化中的应用
随着云计算和大数据技术的快速发展,资源调度与优化成为了现代计算系统中的重要问题。传统的资源调度算法往往基于静态规则或启发式方法,无法适应动态变化的环境和复杂的任务需...【详细内容】
2023-12-14  职场小达人欢晓    Tags:算法   点击:(169)  评论:(0)  加入收藏
相关文章
    无相关信息
站内最新
站内热门
站内头条