基础算法汇总之平衡二叉树(AVL)树实现

2021/10/26 1:10:32

本文主要是介绍基础算法汇总之平衡二叉树(AVL)树实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一. 什么是AVL树?

在说AVL树之前,先回顾一下我们之前研究过的二分查找树(二分搜索树),在极端的情况下,二分搜索树会从一棵二叉树变为链表(按顺序插入数据)这样的查询效率会大打折扣。
在这里插入图片描述

测试上一节二叉查找树在极端情况下的例子:
在这里插入图片描述

为了解决这个问题,就需要通过增加一些属性和变化,将二叉查找树转为(在创建二叉树时候进行旋转让二叉树再次平衡)二叉平衡树。

AVL树(由G.M.Adelson-Velsky和Evgenii Landis发明,AVL命名是使用两个人的名字缩写组成)是最早的自平衡二叉搜索树,AVL树中,任一结点对应的两棵子树的最大高度差不超过1

在二叉树中满二叉树(除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上。)和完全二叉树(二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边)天生就是一棵平衡二叉树
在这里插入图片描述

注意: 平衡二叉树不一定是完全二叉树。

平衡二叉树:对于任意一个结点左右子树高度差不能超过1。

所以AVL可以理解是在二分查找树的基础上兼顾了其平衡性。AVL又名平衡二叉查找树简称为平衡二叉树。

二. 平衡因子

先回顾一下二叉树结点的高度和深度:

  • 深度:深度是从根结点开始算,表示从根到某一个结点唯一的路径的长(该路径长边的条数)。

  • 高度:表示某一个结点到叶子结点最长路径的长。

下面看一个例子:
在这里插入图片描述

接着看一个什么是平衡因子 :某个结点的左子树的高度减去右子树的高度得到的差值。

下图是一个非平衡二叉树平衡二叉树平衡因子的展示:
在这里插入图片描述

三. AVL初始化

3.1. 结点定义

定义AVL树结点:

// TreeNode AVL结点定义
type TreeNode struct {
  data  int       // 结点数据
  height  int       // 结点高度
  left  *TreeNode // 左孩子
  right *TreeNode // 右孩子
}

// NewTreeNode 构建一个新结点
func NewTreeNode(data int) *TreeNode {
  return &TreeNode{
    height: 0,
    left: nil,
    right: nil,
    data: data,
  }
}

可以在二叉查找树的基础上进行修改,这里重点实现插入和删除的操作,其他一些基本上都和二叉树操作一样。

type AVLTree struct {
  root *TreeNode
}

// Insert 插入
func (a *AVLTree) Insert(data int) {
    // TODO
}

// Delete 删除
func (a *AVLTree) Delete(data int) {
    // TODO
}

下面还需要增加一些辅助函数,帮助后面插入和删除的操作。

3.2. 结点高度

在结点中包含了height的属性,如果结点是nil的时候返回0,否则返回结点中height高度。

// height 获取结点的高度
func (a *AVLTree) height(node *TreeNode) int {
  if node == nil {
    return -1
  }
  return node.height
}

3.3. 计算平衡因子

平衡因子:某个结点的左子树的高度减去右子树的高度得到的差值。

// balanceFactor 获取结点的平衡因子
func (a *AVLTree) balanceFactor(node *TreeNode) int {
  if node == nil {
    return 0
  }
  return a.height(node.left) - a.height(node.right)
}

3.4. 判断当前二叉树是否为平衡二叉树

这个方法,后面结点调整会用到; 当插入数据之后,判断当前二叉树是否为平衡二叉树,不是的话需要调整。

// IsBalanceTree 判断是是否为平衡二叉树
func (a *AVLTree) IsBalanceTree() bool {
  return a.isBalanceTree(a.root)
}
// isBalanceTree 递归判断
func (a AVLTree) isBalanceTree(node *TreeNode) bool {
  // node是nil的,返回 true
  if node == nil {
    return true
  }
  // 获取当前结点的平衡因子
  factor := a.balanceFactor(node)
  // 如果平衡因子大于1的话,说明是非平衡二叉树
  if factor * factor > 1 {
    return false
  }
  // 判断左右子树平衡因子大于1
  return a.isBalanceTree(node.left) && a.isBalanceTree(node.right)
}

3.5. 结点增加

这里先使用上一节二叉查找树的中序遍历,进行数据展示。接着用递归实现二叉树查找树的插入:

// Insert 插入数据
func (a *AVLTree) Insert(data int) {
  a.root = a.insert(a.root, data)
}

// max x,y两个树之间的最大值
func max(x, y int) int {
  if x > y {
    return x
  }
  return y
}

// insert 内置的递归函数构建二叉查找树
func (a *AVLTree) insert(node *TreeNode, data int) *TreeNode {
  // 当前结点如果是nil,创建新结点并返回
  if node == nil {
    return NewTreeNode(data)
  }
  // 如果当前结点的data小于data值
  if node.data < data {
    // 从右子树添加
    node.right = a.insert(node.right, data)
  }
  // 如果当前结点的data大于data值
  if node.data > data {
    // 从左子树添加
    node.left = a.insert(node.left, data)
  }
  // 更新高度值
  node.height = 1 + max(a.height(node.left), a.height(node.right))
  // 计算当前结点的平衡因子
  balanceFactor := a.balanceFactor(node)

  fmt.Printf("结点:%d:%d => %d\n", node.data, node.height, balanceFactor)
  return node
}

3.6. 测试

这里通过生成1000个随机数,输出构建的二叉查树。

func TestNewTreeNode(t *testing.T) {
  rand.Seed(time.Now().UnixNano())
  tree := AVLTree{}
  for i := 0; i < 1000; i++ {
    tree.Insert(rand.Intn(1000))
  }
  tree.InOrderTraverse()
}

四. 插入维护平衡

当有一个结点插入之后,会出现二叉树平衡性被打破,此时就需要去维护二叉树查找树,使二叉查找树保存平衡因子不超过1。

3.5中在构建二叉查找树过程中只设置height和计算平衡因子。但是并没有维护插入结点之后对于整棵树的平衡性。

// insert 内置的递归函数构建二叉查找树
func (a *AVLTree) insert(node *TreeNode, data int) *TreeNode {
  // 当前结点如果是nil,创建新结点并返回
  if node == nil {
    return NewTreeNode(data)
  }
  // 如果当前结点的data小于data值
  if node.data < data {
    // 从右子树添加
    node.right = a.insert(node.right, data)
  }
  // 如果当前结点的data大于data值
  if node.data > data {
    // 从左子树添加
    node.left = a.insert(node.left, data)
  }
  // 更新高度值
  node.height = 1 + max(a.height(node.left), a.height(node.right))
  // 计算当前结点的平衡因子
  balanceFactor := a.balanceFactor(node)
  
  // TODO 维护平衡
  
  return node
}

这里我们就需要讨论一下,当插入结点之后会出现不平衡的情况已经如何去维护平衡。

注意:在结点增加之前,二叉树查找树是平衡二叉树;在增加之后才会破坏原来的平衡状态。

4.1. RR型:右旋转

当增加结点的一直往左子树上增加,平衡因子超过1之后就会不平衡,如下图:
在这里插入图片描述

从图中可以看出,触发右旋转的条件:当前结点的平衡因子大于1并且当前结点的左子树的平衡因子大于等于0,这样可以保证二叉树是向左侧偏的。接着看一下应该如何右旋转:
在这里插入图片描述

从上图可知:将B结点指向D2的指针指向A结点,再将A结点的左指针指向原来B结点指向的D2结点;最后还需要修改A、B两个结点的高度。

代码实现:

// rightSpin 右旋转
func (a *AVLTree) rightSpin(node *TreeNode) *TreeNode {
  // 先保存指针指向的地址
  lCh := node.left
  lRCh := lCh.right

  // 旋转
  lCh.right = node
  node.left = lRCh
  
  // 更新height,先更新node结点(旋转之后node结点变成了,lCh的子结点),接着在更新lCh结点的高度
  node.height = max(a.height(node.left), a.height(node.right)) + 1
  lCh.height = max(a.height(lCh.left), a.height(lCh.right)) + 1
  
  // 返回旋转之后的根结点
  return lCh
}

4.2. LL:左旋转

左旋转和右旋转是想反的操作。增加的结点一直向右侧偏移,平衡因子超过-1说明当前二叉树不是平衡二叉树。
在这里插入图片描述

从图中可以知道触发左旋转的条件是:当前结点的平衡因子小于-1并且当前结点的右子树的平衡因子小于等于0,这样可以保证二叉树是向右侧偏的。接着看一下应该如何左旋转:
在这里插入图片描述

实现和右旋转是相反的,代码实现:

// leftSpin 左旋转
func (a *AVLTree) leftSpin(node *TreeNode) *TreeNode {
  
  // 先保存指针指向的地址
  rCh := node.right
  rLCh := rCh.left
  
  // 选装
  rCh.left = node
  node.right = rLCh
  
  // 更新高度
  node.height = max(a.height(node.left), a.height(node.right)) + 1
  rCh.height = max(a.height(rCh.left), a.height(rCh.right)) + 1
  
  // 返回旋转之后的根结点
  return rCh
}

4.3. LR:左旋转;右旋转

这种情况对应下图,指的是在某一个结点的左孩子的右子树上增加结点导致不平衡。
在这里插入图片描述

将失衡的状态,需要先进行左旋转转换为我们熟悉的RR型,然后按照RR型进行右旋转。
在这里插入图片描述

4.4. RL:右旋转;左旋转

这种情况对应下图,指的是在某一个结点的右孩子的左子树上增加结点导致不平衡。
在这里插入图片描述

将失衡的状态,需要先进行右旋转转换为我们熟悉的LL型,然后按照LL型进行左旋转。
在这里插入图片描述

4.5. 完善插入方法

将上面四种情况整合回溯的维护平衡的部分;这样就可以将二叉查找树转为AVL树。

先将维护平衡地方抽取成一个方法:

// maintain 维护平衡
func (a *AVLTree) maintain(node *TreeNode) *TreeNode {
  // 计算当前结点的平衡因子
  balanceFactor := a.balanceFactor(node)

  // 右旋转
  if balanceFactor > 1 && a.balanceFactor(node.left) >= 0 {
    return a.rightSpin(node)
  }
  // 左旋转
  if balanceFactor < -1 && a.balanceFactor(node.right) <= 0 {
    return a.leftSpin(node)
  }

  // LR
  if balanceFactor > 1 && a.balanceFactor(node.left) < 0 {
    node.left = a.leftSpin(node.left)
    return a.rightSpin(node)
  }

  // RL
  if balanceFactor < -1 && a.balanceFactor(node.right) > 0 {
    node.right = a.rightSpin(node.right)
    return a.leftSpin(node)
  }

  return node
}

插入方法的实现:

// Insert 插入数据
func (a *AVLTree) Insert(data int) {
  a.root = a.insert(a.root, data)
}

// insert 递归插入数据
func (a *AVLTree) insert(node *TreeNode, data int) *TreeNode {
  // 当前结点如果是nil,创建新结点并返回
  if node == nil {
    return NewTreeNode(data)
  }
  // 如果当前结点的data小于data值
  if node.data < data {
    // 从右子树添加
    node.right = a.insert(node.right, data)
  }
  // 如果当前结点的data大于data值
  if node.data > data {
    // 从左子树添加
    node.left = a.insert(node.left, data)
  }
  // 更新高度值
  node.height = 1 + max(a.height(node.left), a.height(node.right))
  
  // 维护平衡
  return a.maintain(node)
}

最后测试一下极端情况(顺序写入结点数据):

func TestNewTreeNode(t *testing.T) {
  tree := AVLTree{}
  for i := 0; i < 10000; i++ {
    tree.Insert(i)
  }
  t.Log(tree.IsBalanceTree())  // true
}

在这里插入图片描述

可以很明显看到,经过调整之后极端情况之后并没有退换为链表。

五. 结点删除

结点的删除,可以再原来二叉查找树的基础上修改。在删除之前当前是一棵二叉平衡树, 在删除之后,将可能不再是一棵平衡二叉树,这时候就需要重新平衡。

重新平衡就是对删除结点所在的路径,进行回溯旋转让其重新平衡。

// Remove 移除节点
func (a *AVLTree) Remove(data int) {
  a.root = a.remove(a.root, data)
}

// remove 递归移除
func (a *AVLTree) remove(node *TreeNode, data int) *TreeNode {

  // 如果当前结点是nil
  if node == nil {
    return nil
  }

  var newNode *TreeNode

  if data < node.data {
    node.left = a.remove(node.left, data)
    newNode = node
  } else if data > node.data {
    node.right = a.remove(node.right, data)
    newNode = node
  } else {
    // data 和当前结点的data的数据是一致的,根据当前结点左右子树分情况去讨论

    // 待删除的结点左子树为空
    if node.left == nil {
      right := node.right
      node.right = nil
      newNode = right
    } else if node.right == nil {
      // 待删除的结点的右子树为空
      left := node.left
      node.left = nil
      newNode = left
    } else {
      // 待删除的结点的左右子树否不为空

      // 找到待删除结点右子树中最小的结点
      minMode := a.min(node.right)
      // 移除待删除结点的右子树中最小的结点
      minMode.right = a.remove(node.right, minMode.data)
      minMode.left = node.left

      // 将待删除结点的左右子树都设置为nil
      node.left = nil
      node.right = nil

      // 将新的结点返回
      newNode = minMode
    }

  }

  if newNode == nil {
    return nil
  }
  // 更新高度值
  newNode.height = 1 + max(a.height(newNode.left), a.height(newNode.right))
  // 维护平衡
  return a.maintain(newNode)
}


这篇关于基础算法汇总之平衡二叉树(AVL)树实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程