二叉查找树的树高度影响了查找的效率,需要尽量减小树的高度,AVL树正是这样的树。

一、AVL树介绍

AVL树是一棵严格自平衡的二叉查找树,1962年,发明者 Adelson-VelskyLandis 发表了论文,以两个作者的名字命名了该数据结构,这是较早发明的平衡二叉树。

定义如下:

  1. 首先它是一棵二叉查找树。
  2. 任意一个节点的左右子树最大高度差为1。

由于树特征定义,我们可以计算出其高度 h 的上界 h<=1.44log(n),也就是最坏情况下,树的高度约等于 1.44log(n)

假设高度 h 的AVL树最少有 f(h) 个节点,因为左右子树的高度差不能大于1,所以左子树和右子树最少节点为: f(h-1)f(h-2)

因此,树根节点加上左右子树的节点,满足公式 f(h) = 1 + f(h-1) + f(h-2),初始条件 f(0)=0,f(1)=1

经过数学的推算可以得出 h<=1.44log(n),由于计算过程超纲了,在此不进行演算。

树的高度被限制于 1.44log(n), 所以查找元素时使用二分查找,最坏查找 1.44log(n) 次,此时最坏时间复杂度为 1.44log(n),去掉常数项,时间复杂度为:log(n)

为了维持AVL树的特征,每次添加和删除元素都需要一次或多次旋转来调整树的平衡。调整的依据来自于二叉树节点的平衡因子:节点的左子树与右子树的高度差称为该节点的平衡因子,约束范围为 [-1,0,1]

平衡二叉查找树比较难以理解的是添加和删除元素时的调整操作,我们将会具体分析。

二、AVL树基本结构

AVL树的数据结构如下:

  1. // AVL树
  2. type AVLTree struct {
  3. Root *AVLTreeNode // 树根节点
  4. }
  5. // AVL节点
  6. type AVLTreeNode struct {
  7. Value int64 // 值
  8. Times int64 // 值出现的次数
  9. Height int64 // 该节点作为树根节点,树的高度,方便计算平衡因子
  10. Left *AVLTreeNode // 左子树
  11. Right *AVLTreeNode // 右字树
  12. }
  13. // 初始化一个AVL树
  14. func NewAVLTree() *AVLTree {
  15. return new(AVLTree)
  16. }

其中 Height 表示以该节点作为树的根节点时该树的高度,方便计算平衡因子。

更新树的高度,代码如下:

  1. // 更新节点的树高度
  2. func (node *AVLTreeNode) UpdateHeight() {
  3. if node == nil {
  4. return
  5. }
  6. var leftHeight, rightHeight int64 = 0, 0
  7. if node.Left != nil {
  8. leftHeight = node.Left.Height
  9. }
  10. if node.Right != nil {
  11. rightHeight = node.Right.Height
  12. }
  13. // 哪个子树高算哪棵的
  14. maxHeight := leftHeight
  15. if rightHeight > maxHeight {
  16. maxHeight = rightHeight
  17. }
  18. // 高度加上自己那一层
  19. node.Height = maxHeight + 1
  20. }

计算树的平衡因子,也就是左右子树的高度差,代码如下:

  1. // 计算平衡因子
  2. func (node *AVLTreeNode) BalanceFactor() int64 {
  3. var leftHeight, rightHeight int64 = 0, 0
  4. if node.Left != nil {
  5. leftHeight = node.Left.Height
  6. }
  7. if node.Right != nil {
  8. rightHeight = node.Right.Height
  9. }
  10. return leftHeight - rightHeight
  11. }

三、AVL树添加元素

添加元素前需要定位到元素的位置,也就是使用二分查找找到该元素需要插入的地方。

插入后,需要满足所有节点的平衡因子在 [-1,0,1] 范围内,如果不在,需要进行旋转调整。

旋转有四种情况:

  1. 在右子树上插上右儿子导致失衡,左旋,转一次。
  2. 在左子树上插上左儿子导致失衡,右旋,转一次。
  3. 在左子树上插上右儿子导致失衡,先左后右旋,转两次。
  4. 在右子树上插上左儿子导致失衡,先右后左旋,转两次。

旋转规律记忆法:单旋和双旋,单旋反方向,双旋同方向。

以下示意图摘自维基百科,阅读代码时可以参考。

AVL树 - 图1

3.1. 左子树插左儿子:单右旋

在左子树上插上左儿子导致失衡,需要单右旋:

AVL树 - 图2

因为红色元素 2 的产生,其最近的父亲节点 Root 失衡了,元素 2 导致了元素 Root=5 的失衡,需要调整。

Pivot=3 代替元素 5 的位置成为新的 Root,然后元素 5 委屈一下成为 3 的右儿子,而 3 的右儿子变成了 5 的左儿子,如上图。

相应调整后树的高度降低了,该失衡消失。我们可以看到红色元素 2 有两个儿子,实际上在添加操作时它是一个新的节点,是没有儿子的,这种有儿子的情况只发生在删除操作。

如果一时难以理解,可以多看几次图好好思考。

代码如下:

  1. // 单右旋操作,看图说话
  2. func RightRotation(Root *AVLTreeNode) *AVLTreeNode {
  3. // 只有Pivot和B,Root位置变了
  4. Pivot := Root.Left
  5. B := Pivot.Right
  6. Pivot.Right = Root
  7. Root.Left = B
  8. // 只有Root和Pivot变化了高度
  9. Root.UpdateHeight()
  10. Pivot.UpdateHeight()
  11. return Pivot
  12. }

3.2. 右子树插右儿子:单左旋

在右子树上插上右儿子导致失衡,需要单左旋:

AVL树 - 图3

代码如下:

  1. // 单左旋操作,看图说话
  2. func LeftRotation(Root *AVLTreeNode) *AVLTreeNode {
  3. // 只有Pivot和B,Root位置变了
  4. Pivot := Root.Right
  5. B := Pivot.Left
  6. Pivot.Left = Root
  7. Root.Right = B
  8. // 只有Root和Pivot变化了高度
  9. Root.UpdateHeight()
  10. Pivot.UpdateHeight()
  11. return Pivot
  12. }

3.3. 左子树插右儿子:先左后右旋

在左子树上插上右儿子导致失衡,先左后右旋:

AVL树 - 图4

代码如下:

  1. // 先左后右旋操作,看图说话
  2. func LeftRightRotation(node *AVLTreeNode) *AVLTreeNode {
  3. node.Left = LeftRotation(node.Left)
  4. return RightRotation(node)
  5. }

直接复用了之前左旋和右旋的代码,虽然难以理解,但是画一下图,确实这样调整后树高度降了,不再失衡,一切 perfect。

3.4. 右子树插左儿子:先右后左旋

在右子树上插上左儿子导致失衡,先右后左旋:

AVL树 - 图5

代码如下:

  1. // 先右后左旋操作,看图说话
  2. func RightLeftRotation(node *AVLTreeNode) *AVLTreeNode {
  3. node.Right = RightRotation(node.Right)
  4. return LeftRotation(node)
  5. }

3.5. 具体实现

四种旋转代码实现后,我们开始进行添加元素操作:

  1. // 添加元素
  2. func (tree *AVLTree) Add(value int64) {
  3. // 往树根添加元素,会返回新的树根
  4. tree.Root = tree.Root.Add(value)
  5. }
  6. func (node *AVLTreeNode) Add(value int64) *AVLTreeNode {
  7. // 添加值到根节点node,如果node为空,那么让值成为新的根节点,树的高度为1
  8. if node == nil {
  9. return &AVLTreeNode{Value: value, Height: 1}
  10. }
  11. // 如果值重复,什么都不用做,直接更新次数
  12. if node.Value == value {
  13. node.Times = node.Times + 1
  14. return node
  15. }
  16. // 辅助变量
  17. var newTreeNode *AVLTreeNode
  18. if value > node.Value {
  19. // 插入的值大于节点值,要从右子树继续插入
  20. node.Right = node.Right.Add(value)
  21. // 平衡因子,插入右子树后,要确保树根左子树的高度不能比右子树低一层。
  22. factor := node.BalanceFactor()
  23. // 右子树的高度变高了,导致左子树-右子树的高度从-1变成了-2。
  24. if factor == -2 {
  25. if value > node.Right.Value {
  26. // 表示在右子树上插上右儿子导致失衡,需要单左旋:
  27. newTreeNode = LeftRotation(node)
  28. } else {
  29. //表示在右子树上插上左儿子导致失衡,先右后左旋:
  30. newTreeNode = RightLeftRotation(node)
  31. }
  32. }
  33. } else {
  34. // 插入的值小于节点值,要从左子树继续插入
  35. node.Left = node.Left.Add(value)
  36. // 平衡因子,插入左子树后,要确保树根左子树的高度不能比右子树高一层。
  37. factor := node.BalanceFactor()
  38. // 左子树的高度变高了,导致左子树-右子树的高度从1变成了2。
  39. if factor == 2 {
  40. if value < node.Left.Value {
  41. // 表示在左子树上插上左儿子导致失衡,需要单右旋:
  42. newTreeNode = RightRotation(node)
  43. } else {
  44. //表示在左子树上插上右儿子导致失衡,先左后右旋:
  45. newTreeNode = LeftRightRotation(node)
  46. }
  47. }
  48. }
  49. if newTreeNode == nil {
  50. // 表示什么旋转都没有,根节点没变,直接刷新树高度
  51. node.UpdateHeight()
  52. return node
  53. } else {
  54. // 旋转了,树根节点变了,需要刷新新的树根高度
  55. newTreeNode.UpdateHeight()
  56. return newTreeNode
  57. }
  58. }

一开始从树根节点开始插入新值:tree.Root = tree.Root.Add(value),因为插入值后会返回新的根节点,也就是说调整过程中树根节点会变化,所以要重新将新根节点赋予老的根节点。

func (node *AVLTreeNode) Add(value int64) 函数中,如果根节点为空,那么需要返回新的根节点:

  1. // 添加值到根节点node,如果node为空,那么让值成为新的根节点,树的高度为1
  2. if node == nil {
  3. return &AVLTreeNode{Value: value, Height: 1}
  4. }

接着,如果插入的值和节点的值一样,直接更新 Times

  1. // 如果值重复,什么都不用做,直接更新次数
  2. if node.Value == value {
  3. node.Times = node.Times + 1
  4. return node
  5. }

否则根据值的大小,旋转插入到左子树或右子树,我们只分析插入右子树的代码:

  1. if value > node.Value {
  2. // 插入的值大于节点值,要从右子树继续插入
  3. node.Right = node.Right.Add(value)
  4. // 平衡因子,插入右子树后,要确保树根左子树的高度不能比右子树低一层。
  5. factor := node.BalanceFactor()
  6. // 右子树的高度变高了,导致左子树-右子树的高度从-1变成了-2。
  7. if factor == -2 {
  8. if value > node.Right.Value {
  9. // 表示在右子树上插上右儿子导致失衡,需要单左旋:
  10. newTreeNode = LeftRotation(node)
  11. } else {
  12. //表示在右子树上插上左儿子导致失衡,先右后左旋:
  13. newTreeNode = RightLeftRotation(node)
  14. }
  15. }
  16. }

因为值添加到了右子树,所以转换成了在右子树添加元素:node.Right = node.Right.Add(value),之后要判断根节点的平衡因子是否变化了。

值插入右子树后,要确保树根左子树的高度不能比右子树低一层。当平衡因子 factor == -2 表示右子树的高度变高了,导致 左子树-右子树 的高度从 -1 变成了 -2,所以要旋转。

判断新插入的值是在右子树的左儿子还是右儿子上:

  1. if value > node.Right.Value {
  2. // 表示在右子树上插上右儿子导致失衡,需要单左旋:
  3. newTreeNode = LeftRotation(node)
  4. } else {
  5. //表示在右子树上插上左儿子导致失衡,先右后左旋:
  6. newTreeNode = RightLeftRotation(node)
  7. }

如果在右子树上插上右儿子导致失衡,需要单左旋:LeftRotation(node),如果在右子树上插上左儿子导致失衡,先右后左旋:RightLeftRotation(node)

最后需要更新树根节点的高度,并返回树根(如果曾经旋转,表示树根变了,需要返回新的树根):

  1. if newTreeNode == nil {
  2. // 表示什么旋转都没有,根节点没变,直接刷新树高度
  3. node.UpdateHeight()
  4. return node
  5. } else {
  6. // 旋转了,树根节点变了,需要刷新新的树根高度
  7. newTreeNode.UpdateHeight()
  8. return newTreeNode
  9. }

3.6. 时间复杂度分析

添加元素时先要找到元素插入的位置,找到位置后逐层自底向上更新每个子树的树高度,并根据子树平衡是否被破坏,需要进行旋转操作。

由于树的高度最高为 1.44log(n),查找元素插入位置,最坏次数为 1.44log(n) 次。逐层更新子树高度并判断平衡是否被破坏,最坏需要 1.44log(n) 次,因此可以得知添加元素最坏时间复杂度为:2.88log(n),去掉常数项,时间复杂度为:log(n)

关于旋转次数,当插入节点后,某子树不平衡时最多旋转 2次,也就是双旋该子树即可恢复平衡,该调整为局部特征,调整完后其父层不再需要旋转。也就是说,插入操作最坏旋转两次即可。

由于代码的递归实现方式,当某子树旋转过后其父层子树仍然需要判断平衡因子,判断是否需要旋转,该操作是不必要的,因为子树旋转过后全局已经平衡了,不必再判断父层的平衡因子。

对此可以进行代码优化,在左子树或右子树插入元素后,除了返回根节点,还返回其是否旋转过的辅助变量,如:func (node *AVLTreeNode) Add(value int64) (newNode *AVLTreeNode, rotate bool) ,根据返回的辅助变量 rotate,可以:

  1. node.Right, rotate= node.Right.Add(value)
  2. if !rotate {
  3. // 子树没有旋转过,那么需要判断是否需要旋转
  4. // 平衡因子,插入右子树后,要确保树根左子树的高度不能比右子树低一层。
  5. factor := node.BalanceFactor()
  6. // 右子树的高度变高了,导致左子树-右子树的高度从-1变成了-2。
  7. if factor == -2 {
  8. if value > node.Right.Value {
  9. // 表示在右子树上插上右儿子导致失衡,需要单左旋:
  10. newTreeNode = LeftRotation(node)
  11. } else {
  12. //表示在右子树上插上左儿子导致失衡,先右后左旋:
  13. newTreeNode = RightLeftRotation(node)
  14. }
  15. }
  16. }else{
  17. // do nothing
  18. }

但此优化意义不大,因为返回辅助变量后仍然需要判断,判断辅助变量和判断平衡因子,时间复杂度一样。

插入元素进行调整后,需要递归向上更新每一棵子树高度,其时间复杂度为 log(n),但可以优化,当两棵子树高度都没有变化时,那么上面的父层子树们都不需要更新树高度,直接退出,由于是递归程序,如何向上传递这个信息,引入了额外空间成本,且不可避免仍然会出现所有层级的父节点都必须更新树高度,优化意义不是很大。

四、AVL树查找元素等操作

其他操作与二叉查找树通用,代码如下:

  1. // 找出最小值的节点
  2. func (tree *AVLTree) FindMinValue() *AVLTreeNode {
  3. if tree.Root == nil {
  4. // 如果是空树,返回空
  5. return nil
  6. }
  7. return tree.Root.FindMinValue()
  8. }
  9. func (node *AVLTreeNode) FindMinValue() *AVLTreeNode {
  10. // 左子树为空,表面已经是最左的节点了,该值就是最小值
  11. if node.Left == nil {
  12. return node
  13. }
  14. // 一直左子树递归
  15. return node.Left.FindMinValue()
  16. }
  17. // 找出最大值的节点
  18. func (tree *AVLTree) FindMaxValue() *AVLTreeNode {
  19. if tree.Root == nil {
  20. // 如果是空树,返回空
  21. return nil
  22. }
  23. return tree.Root.FindMaxValue()
  24. }
  25. func (node *AVLTreeNode) FindMaxValue() *AVLTreeNode {
  26. // 右子树为空,表面已经是最右的节点了,该值就是最大值
  27. if node.Right == nil {
  28. return node
  29. }
  30. // 一直右子树递归
  31. return node.Right.FindMaxValue()
  32. }
  33. // 查找指定节点
  34. func (tree *AVLTree) Find(value int64) *AVLTreeNode {
  35. if tree.Root == nil {
  36. // 如果是空树,返回空
  37. return nil
  38. }
  39. return tree.Root.Find(value)
  40. }
  41. func (node *AVLTreeNode) Find(value int64) *AVLTreeNode {
  42. if value == node.Value {
  43. // 如果该节点刚刚等于该值,那么返回该节点
  44. return node
  45. } else if value < node.Value {
  46. // 如果查找的值小于节点值,从节点的左子树开始找
  47. if node.Left == nil {
  48. // 左子树为空,表示找不到该值了,返回nil
  49. return nil
  50. }
  51. return node.Left.Find(value)
  52. } else {
  53. // 如果查找的值大于节点值,从节点的右子树开始找
  54. if node.Right == nil {
  55. // 右子树为空,表示找不到该值了,返回nil
  56. return nil
  57. }
  58. return node.Right.Find(value)
  59. }
  60. }
  61. // 中序遍历
  62. func (tree *AVLTree) MidOrder() {
  63. tree.Root.MidOrder()
  64. }
  65. func (node *AVLTreeNode) MidOrder() {
  66. if node == nil {
  67. return
  68. }
  69. // 先打印左子树
  70. node.Left.MidOrder()
  71. // 按照次数打印根节点
  72. for i := 0; i <= int(node.Times); i++ {
  73. fmt.Println(node.Value)
  74. }
  75. // 打印右子树
  76. node.Right.MidOrder()
  77. }

查找操作逻辑与通用的二叉查找树一样,并无区别。

五、AVL树删除元素

删除元素有四种情况:

  1. 删除的节点是叶子节点,没有儿子,直接删除后看离它最近的父亲节点是否失衡,做调整操作。
  2. 删除的节点下有两个子树,选择高度更高的子树下的节点来替换被删除的节点,如果左子树更高,选择左子树中最大的节点,也就是左子树最右边的叶子节点,如果右子树更高,选择右子树中最小的节点,也就是右子树最左边的叶子节点。最后,删除这个叶子节点,也就是变成情况1。
  3. 删除的节点只有左子树,可以知道左子树其实就只有一个节点,被删除节点本身(假设左子树多于2个节点,那么高度差就等于2了,不符合AVL树定义),将左节点替换被删除的节点,最后删除这个左节点,变成情况1。
  4. 删除的节点只有右子树,可以知道右子树其实就只有一个节点,被删除节点本身(假设右子树多于2个节点,那么高度差就等于2了,不符合AVL树定义),将右节点替换被删除的节点,最后删除这个右节点,变成情况1。

后面三种情况最后都变成 情况1,就是将删除的节点变成叶子节点,然后可以直接删除该叶子节点,然后看其最近的父亲节点是否失衡,失衡时对树进行平衡。

举个例子,删除叶子节点,如图:

AVL树 - 图6

删除节点 24,导致节点 26 的子树不平衡了,这时需要对该子树进行旋转,旋转后如图:

AVL树 - 图7

可以发现这时树仍然不平衡,这时是节点 22 的子树不平衡,需要继续旋转,旋转后如图:

AVL树 - 图8

实现代码如下:

  1. func (node *AVLTreeNode) Delete(value int64) *AVLTreeNode {
  2. if node == nil {
  3. // 如果是空树,直接返回
  4. return nil
  5. }
  6. if value < node.Value {
  7. // 从左子树开始删除
  8. node.Left = node.Left.Delete(value)
  9. // 删除后要更新该子树高度
  10. node.Left.UpdateHeight()
  11. } else if value > node.Value {
  12. // 从右子树开始删除
  13. node.Right = node.Right.Delete(value)
  14. // 删除后要更新该子树高度
  15. node.Right.UpdateHeight()
  16. } else {
  17. // 找到该值对应的节点
  18. // 该节点没有左右子树
  19. // 第一种情况,删除的节点没有儿子,直接删除即可。
  20. if node.Left == nil && node.Right == nil {
  21. return nil // 直接返回nil,表示直接该值删除
  22. }
  23. // 该节点有两棵子树,选择更高的哪个来替换
  24. // 第二种情况,删除的节点下有两个子树,选择高度更高的子树下的节点来替换被删除的节点,如果左子树更高,选择左子树中最大的节点,也就是左子树最右边的叶子节点,如果右子树更高,选择右子树中最小的节点,也就是右子树最左边的叶子节点。最后,删除这个叶子节点。
  25. if node.Left != nil && node.Right != nil {
  26. // 左子树更高,拿左子树中最大值的节点替换
  27. if node.Left.Height > node.Right.Height {
  28. maxNode := node.Left
  29. for maxNode.Right != nil {
  30. maxNode = maxNode.Right
  31. }
  32. // 最大值的节点替换被删除节点
  33. node.Value = maxNode.Value
  34. node.Times = maxNode.Times
  35. // 把最大的节点删掉
  36. node.Left = node.Left.Delete(maxNode.Value)
  37. // 删除后要更新该子树高度
  38. node.Left.UpdateHeight()
  39. } else {
  40. // 右子树更高,拿右子树中最小值的节点替换
  41. minNode := node.Right
  42. for minNode.Left != nil {
  43. minNode = minNode.Left
  44. }
  45. // 最小值的节点替换被删除节点
  46. node.Value = minNode.Value
  47. node.Times = minNode.Times
  48. // 把最小的节点删掉
  49. node.Right = node.Right.Delete(minNode.Value)
  50. // 删除后要更新该子树高度
  51. node.Right.UpdateHeight()
  52. }
  53. } else {
  54. // 只有左子树或只有右子树
  55. // 只有一个子树,该子树也只是一个节点,将该节点替换被删除的节点,然后置子树为空
  56. if node.Left != nil {
  57. //第三种情况,删除的节点只有左子树,因为树的特征,可以知道左子树其实就只有一个节点,它本身,否则高度差就等于2了。
  58. node.Value = node.Left.Value
  59. node.Times = node.Left.Times
  60. node.Height = 1
  61. node.Left = nil
  62. } else if node.Right != nil {
  63. //第四种情况,删除的节点只有右子树,因为树的特征,可以知道右子树其实就只有一个节点,它本身,否则高度差就等于2了。
  64. node.Value = node.Right.Value
  65. node.Times = node.Right.Times
  66. node.Height = 1
  67. node.Right = nil
  68. }
  69. }
  70. // 找到值后,进行替换删除后,直接返回该节点
  71. return node
  72. }
  73. // 左右子树递归删除节点后需要平衡
  74. var newNode *AVLTreeNode
  75. // 相当删除了右子树的节点,左边比右边高了,不平衡
  76. if node.BalanceFactor() == 2 {
  77. if node.Left.BalanceFactor() >= 0 {
  78. newNode = RightRotation(node)
  79. } else {
  80. newNode = LeftRightRotation(node)
  81. }
  82. // 相当删除了左子树的节点,右边比左边高了,不平衡
  83. } else if node.BalanceFactor() == -2 {
  84. if node.Right.BalanceFactor() <= 0 {
  85. newNode = LeftRotation(node)
  86. } else {
  87. newNode = RightLeftRotation(node)
  88. }
  89. }
  90. if newNode == nil {
  91. node.UpdateHeight()
  92. return node
  93. } else {
  94. newNode.UpdateHeight()
  95. return newNode
  96. }
  97. }

当删除的值不等于当前节点的值时,在相应的子树中递归删除,递归过程中会自底向上维护AVL树的特征。

  1. 小于删除的值 value < node.Value,在左子树中递归删除:node.Left = node.Left.Delete(value)
  2. 大于删除的值 value > node.Value,在右子树中递归删除:node.Right = node.Right.Delete(value)

因为删除后可能因为旋转调整,导致树根节点变了,这时会返回新的树根,递归删除后需要将返回的新根节点赋予原来的老根节点。

情况1,找到要删除的值时,该值是叶子节点,直接删除该节点即可:

  1. // 第一种情况,删除的节点没有儿子,直接删除即可。
  2. if node.Left == nil && node.Right == nil {
  3. return nil // 直接返回nil,表示直接该值删除
  4. }

情况2,删除的节点有两棵子树,选择高度更高的子树下的节点来替换被删除的节点:

  1. // 该节点有两棵子树,选择更高的哪个来替换
  2. // 第二种情况,删除的节点下有两个子树,选择高度更高的子树下的节点来替换被删除的节点,如果左子树更高,选择左子树中最大的节点,也就是左子树最右边的叶子节点,如果右子树更高,选择右子树中最小的节点,也就是右子树最左边的叶子节点。最后,删除这个叶子节点。
  3. if node.Left != nil && node.Right != nil {
  4. // 左子树更高,拿左子树中最大值的节点替换
  5. if node.Left.Height > node.Right.Height {
  6. maxNode := node.Left
  7. for maxNode.Right != nil {
  8. maxNode = maxNode.Right
  9. }
  10. // 最大值的节点替换被删除节点
  11. node.Value = maxNode.Value
  12. node.Times = maxNode.Times
  13. // 把最大的节点删掉
  14. node.Left = node.Left.Delete(maxNode.Value)
  15. // 删除后要更新该子树高度
  16. node.Left.UpdateHeight()
  17. } else {
  18. // 右子树更高,拿右子树中最小值的节点替换
  19. minNode := node.Right
  20. for minNode.Left != nil {
  21. minNode = minNode.Left
  22. }
  23. // 最小值的节点替换被删除节点
  24. node.Value = minNode.Value
  25. node.Times = minNode.Times
  26. // 把最小的节点删掉
  27. node.Right = node.Right.Delete(minNode.Value)
  28. // 删除后要更新该子树高度
  29. node.Right.UpdateHeight()
  30. }
  31. }

情况3和情况4,如果被删除的节点只有一个子树,那么该子树一定没有儿子,不然树的高度就大于1了,所以直接替换值后删除该子树节点:

  1. // 只有左子树或只有右子树
  2. // 只有一个子树,该子树也只是一个节点,将该节点替换被删除的节点,然后置子树为空
  3. if node.Left != nil {
  4. //第三种情况,删除的节点只有左子树,因为树的特征,可以知道左子树其实就只有一个节点,它本身,否则高度差就等于2了。
  5. node.Value = node.Left.Value
  6. node.Times = node.Left.Times
  7. node.Height = 1
  8. node.Left = nil
  9. } else if node.Right != nil {
  10. //第四种情况,删除的节点只有右子树,因为树的特征,可以知道右子树其实就只有一个节点,它本身,否则高度差就等于2了。
  11. node.Value = node.Right.Value
  12. node.Times = node.Right.Times
  13. node.Height = 1
  14. node.Right = nil
  15. }

核心在于删除后的旋转调整,如果删除的值不匹配当前节点的值,对当前节点的左右子树进行递归删除,递归删除后该节点为根节点的子树可能不平衡,我们需要判断后决定要不要旋转这棵树。

每次递归都是自底向上,从很小的子树到很大的子树,如果自底向上每棵子树都进行调整,约束在树的高度差不超过1,那么整棵树自然也符合AVL树的平衡规则。

删除元素后,如果子树失衡,需要进行调整操作,主要有两种:删除后左子树比右子树高,删除后右子树比左子树高。

5.1. 删除后,左子树比右子树高

如果删除了右子树的节点,左边比右边高了,不平衡了:

  1. // 相当删除了右子树的节点,左边比右边高了,不平衡
  2. if node.BalanceFactor() == 2 {
  3. if node.Left.BalanceFactor() >= 0 {
  4. newNode = RightRotation(node)
  5. } else {
  6. newNode = LeftRightRotation(node)
  7. }
  8. }

为什么要这么调整呢,看图说话,有两幅图参考:

AVL树 - 图9

这幅图可以看到:

  1. 黄色点5.BalanceFactor() == 2,对应:node.BalanceFactor() == 2
  2. 绿色点3.BalanceFactor() == 1,对应:node.Left.BalanceFactor() == 1

所以应该需要右旋:newNode = RightRotation(node)

AVL树 - 图10

这幅图可以看到:

  1. 黄色点5.BalanceFactor() == 2,对应:node.BalanceFactor() == 2
  2. 绿色点3.BalanceFactor() == -1,对应:node.Left.BalanceFactor() == -1

所以应该需要先左后右旋:newNode = LeftRightRotation(node)

还有一种特殊情况,和上面的都不一样,如图:

AVL树 - 图11

我们如果删除节点 22 或节点 23,这个时候根节点 20 失衡了。

  1. 根节点 20 的左子树比右子树高了 2 层,对应:node.BalanceFactor() == 2
  2. 左子树节点 13 并没有失衡,对应:node.BalanceFactor() == 0

这个时候,无论使用右旋,还是先左旋后右旋都可以使树恢复平衡,我们的 if 判断条件使用了右旋。

如果是先左旋后右旋,那么旋转后恢复平衡,如图对根结点进行旋转:

AVL树 - 图12

如果使用右旋也可以,如图对根结点进行旋转:

AVL树 - 图13

5.2. 删除后,右子树比左子树高

如果删除了左子树的节点,右边比左边高了,不平衡了:

  1. // 相当删除了左子树的节点,右边比左边高了,不平衡
  2. if node.BalanceFactor() == -2 {
  3. if node.Right.BalanceFactor() <= 0 {
  4. newNode = LeftRotation(node)
  5. } else {
  6. newNode = RightLeftRotation(node)
  7. }
  8. }

为什么要这么调整呢,看图说话,有两幅图参考:

AVL树 - 图14

这幅图可以看到:

  1. 绿色点3.BalanceFactor() == -2,对应:node.BalanceFactor() == -2
  2. 黄色点5.BalanceFactor() == -1,对应:node.Left.BalanceFactor() == -1

所以应该需要左旋:newNode = LeftRotation(node)

AVL树 - 图15

这幅图可以看到:

  1. 绿色点3.BalanceFactor() == -2,对应:node.BalanceFactor() == -2
  2. 黄色点5.BalanceFactor() == 1,对应:node.Left.BalanceFactor() == 1

所以应该需要先右后左旋:newNode = RightLeftRotation(node)

当然,还有另外一种特殊情况,与 5.1 章节类似,使用左旋还是先右旋后左旋都可以,在这里就不阐述了。

5.3. 删除后,调整树高度

进行调整操作后,需要更新该子树的高度。如果没有旋转过,更新之前节点的树高度。如果曾经旋转过,树根变了,更新新的树根节点高度。

  1. if newNode == nil {
  2. node.UpdateHeight()
  3. return node
  4. } else {
  5. newNode.UpdateHeight()
  6. return newNode
  7. }

5.4. 时间复杂度分析

删除操作是先找到删除的节点,然后将该节点与一个叶子节点交换,接着删除叶子节点,最后对叶子节点的父层逐层向上旋转调整。

删除操作的时间复杂度和添加操作一样。区别在于,添加操作最多旋转两次就可以达到树的平衡,而删除操作可能会旋转超过两次。

如图是一棵比较糟糕的 AVL 树:

AVL树 - 图16

删除节点1,旋转可以一直旋转到根节点,比插入旋转最多旋转两次的次数更多。

六、验证是否是一棵AVL树

如何确保我们的代码实现的就是一棵 AVL 树呢,可以进行验证:

  1. // 验证是不是棵AVL树
  2. func (tree *AVLTree) IsAVLTree() bool {
  3. if tree == nil || tree.Root == nil {
  4. return true
  5. }
  6. // 判断节点是否符合 AVL 树的定义
  7. if tree.Root.IsRight() {
  8. return true
  9. }
  10. return false
  11. }
  12. // 判断节点是否符合 AVL 树的定义
  13. func (node *AVLTreeNode) IsRight() bool {
  14. if node == nil {
  15. return true
  16. }
  17. // 左右子树都为空,那么是叶子节点
  18. if node.Left == nil && node.Right == nil {
  19. // 叶子节点高度应该为1
  20. if node.Height == 1 {
  21. return true
  22. } else {
  23. fmt.Println("leaf node height is ", node.Height)
  24. return false
  25. }
  26. } else if node.Left != nil && node.Right != nil {
  27. // 左右子树都是满的
  28. // 左儿子必须比父亲小,右儿子必须比父亲大
  29. if node.Left.Value < node.Value && node.Right.Value > node.Value {
  30. } else {
  31. // 不符合 AVL 树定义
  32. fmt.Printf("father is %v lchild is %v, rchild is %v\n", node.Value, node.Left.Value, node.Right.Value)
  33. return false
  34. }
  35. bal := node.Left.Height - node.Right.Height
  36. if bal < 0 {
  37. bal = -bal
  38. }
  39. // 子树高度差不能大于1
  40. if bal > 1 {
  41. fmt.Println("sub tree height bal is ", bal)
  42. return false
  43. }
  44. // 如果左子树比右子树高,那么父亲的高度等于左子树+1
  45. if node.Left.Height > node.Right.Height {
  46. if node.Height == node.Left.Height+1 {
  47. } else {
  48. fmt.Printf("%#v height:%v,left sub tree height: %v,right sub tree height:%v\n", node, node.Height, node.Left.Height, node.Right.Height)
  49. return false
  50. }
  51. } else {
  52. // 如果右子树比左子树高,那么父亲的高度等于右子树+1
  53. if node.Height == node.Right.Height+1 {
  54. } else {
  55. fmt.Printf("%#v height:%v,left sub tree height: %v,right sub tree height:%v\n", node, node.Height, node.Left.Height, node.Right.Height)
  56. return false
  57. }
  58. }
  59. // 递归判断子树
  60. if !node.Left.IsRight() {
  61. return false
  62. }
  63. // 递归判断子树
  64. if !node.Right.IsRight() {
  65. return false
  66. }
  67. } else {
  68. // 只存在一棵子树
  69. if node.Right != nil {
  70. // 子树高度只能是1
  71. if node.Right.Height == 1 && node.Right.Left == nil && node.Right.Right == nil {
  72. if node.Right.Value > node.Value {
  73. // 右节点必须比父亲大
  74. } else {
  75. fmt.Printf("%v,(%#v,%#v) child", node.Value, node.Right, node.Left)
  76. return false
  77. }
  78. } else {
  79. fmt.Printf("%v,(%#v,%#v) child", node.Value, node.Right, node.Left)
  80. return false
  81. }
  82. } else {
  83. if node.Left.Height == 1 && node.Left.Left == nil && node.Left.Right == nil {
  84. if node.Left.Value < node.Value {
  85. // 左节点必须比父亲小
  86. } else {
  87. fmt.Printf("%v,(%#v,%#v) child", node.Value, node.Right, node.Left)
  88. return false
  89. }
  90. } else {
  91. fmt.Printf("%v,(%#v,%#v) child", node.Value, node.Right, node.Left)
  92. return false
  93. }
  94. }
  95. }
  96. return true
  97. }

运行请看完整代码。

七、AVL树完整代码

  1. package main
  2. import (
  3. "fmt"
  4. )
  5. // AVL树
  6. type AVLTree struct {
  7. Root *AVLTreeNode // 树根节点
  8. }
  9. // AVL节点
  10. type AVLTreeNode struct {
  11. Value int64 // 值
  12. Times int64 // 值出现的次数
  13. Height int64 // 该节点作为树根节点,树的高度,方便计算平衡因子
  14. Left *AVLTreeNode // 左子树
  15. Right *AVLTreeNode // 右字树
  16. }
  17. // 初始化一个AVL树
  18. func NewAVLTree() *AVLTree {
  19. return new(AVLTree)
  20. }
  21. // 更新节点的树高度
  22. func (node *AVLTreeNode) UpdateHeight() {
  23. if node == nil {
  24. return
  25. }
  26. var leftHeight, rightHeight int64 = 0, 0
  27. if node.Left != nil {
  28. leftHeight = node.Left.Height
  29. }
  30. if node.Right != nil {
  31. rightHeight = node.Right.Height
  32. }
  33. // 哪个子树高算哪棵的
  34. maxHeight := leftHeight
  35. if rightHeight > maxHeight {
  36. maxHeight = rightHeight
  37. }
  38. // 高度加上自己那一层
  39. node.Height = maxHeight + 1
  40. }
  41. // 计算平衡因子
  42. func (node *AVLTreeNode) BalanceFactor() int64 {
  43. var leftHeight, rightHeight int64 = 0, 0
  44. if node.Left != nil {
  45. leftHeight = node.Left.Height
  46. }
  47. if node.Right != nil {
  48. rightHeight = node.Right.Height
  49. }
  50. return leftHeight - rightHeight
  51. }
  52. // 单右旋操作,看图说话
  53. func RightRotation(Root *AVLTreeNode) *AVLTreeNode {
  54. // 只有Pivot和B,Root位置变了
  55. Pivot := Root.Left
  56. B := Pivot.Right
  57. Pivot.Right = Root
  58. Root.Left = B
  59. // 只有Root和Pivot变化了高度
  60. Root.UpdateHeight()
  61. Pivot.UpdateHeight()
  62. return Pivot
  63. }
  64. // 单左旋操作,看图说话
  65. func LeftRotation(Root *AVLTreeNode) *AVLTreeNode {
  66. // 只有Pivot和B,Root位置变了
  67. Pivot := Root.Right
  68. B := Pivot.Left
  69. Pivot.Left = Root
  70. Root.Right = B
  71. // 只有Root和Pivot变化了高度
  72. Root.UpdateHeight()
  73. Pivot.UpdateHeight()
  74. return Pivot
  75. }
  76. // 先左后右旋操作,看图说话
  77. func LeftRightRotation(node *AVLTreeNode) *AVLTreeNode {
  78. node.Left = LeftRotation(node.Left)
  79. return RightRotation(node)
  80. }
  81. // 先右后左旋操作,看图说话
  82. func RightLeftRotation(node *AVLTreeNode) *AVLTreeNode {
  83. node.Right = RightRotation(node.Right)
  84. return LeftRotation(node)
  85. }
  86. // 添加元素
  87. func (tree *AVLTree) Add(value int64) {
  88. // 往树根添加元素,会返回新的树根
  89. tree.Root = tree.Root.Add(value)
  90. }
  91. func (node *AVLTreeNode) Add(value int64) *AVLTreeNode {
  92. // 添加值到根节点node,如果node为空,那么让值成为新的根节点,树的高度为1
  93. if node == nil {
  94. return &AVLTreeNode{Value: value, Height: 1}
  95. }
  96. // 如果值重复,什么都不用做,直接更新次数
  97. if node.Value == value {
  98. node.Times = node.Times + 1
  99. return node
  100. }
  101. // 辅助变量
  102. var newTreeNode *AVLTreeNode
  103. if value > node.Value {
  104. // 插入的值大于节点值,要从右子树继续插入
  105. node.Right = node.Right.Add(value)
  106. // 平衡因子,插入右子树后,要确保树根左子树的高度不能比右子树低一层。
  107. factor := node.BalanceFactor()
  108. // 右子树的高度变高了,导致左子树-右子树的高度从-1变成了-2。
  109. if factor == -2 {
  110. if value > node.Right.Value {
  111. // 表示在右子树上插上右儿子导致失衡,需要单左旋:
  112. newTreeNode = LeftRotation(node)
  113. } else {
  114. //表示在右子树上插上左儿子导致失衡,先右后左旋:
  115. newTreeNode = RightLeftRotation(node)
  116. }
  117. }
  118. } else {
  119. // 插入的值小于节点值,要从左子树继续插入
  120. node.Left = node.Left.Add(value)
  121. // 平衡因子,插入左子树后,要确保树根左子树的高度不能比右子树高一层。
  122. factor := node.BalanceFactor()
  123. // 左子树的高度变高了,导致左子树-右子树的高度从1变成了2。
  124. if factor == 2 {
  125. if value < node.Left.Value {
  126. // 表示在左子树上插上左儿子导致失衡,需要单右旋:
  127. newTreeNode = RightRotation(node)
  128. } else {
  129. //表示在左子树上插上右儿子导致失衡,先左后右旋:
  130. newTreeNode = LeftRightRotation(node)
  131. }
  132. }
  133. }
  134. if newTreeNode == nil {
  135. // 表示什么旋转都没有,根节点没变,直接刷新树高度
  136. node.UpdateHeight()
  137. return node
  138. } else {
  139. // 旋转了,树根节点变了,需要刷新新的树根高度
  140. newTreeNode.UpdateHeight()
  141. return newTreeNode
  142. }
  143. }
  144. // 找出最小值的节点
  145. func (tree *AVLTree) FindMinValue() *AVLTreeNode {
  146. if tree.Root == nil {
  147. // 如果是空树,返回空
  148. return nil
  149. }
  150. return tree.Root.FindMinValue()
  151. }
  152. func (node *AVLTreeNode) FindMinValue() *AVLTreeNode {
  153. // 左子树为空,表面已经是最左的节点了,该值就是最小值
  154. if node.Left == nil {
  155. return node
  156. }
  157. // 一直左子树递归
  158. return node.Left.FindMinValue()
  159. }
  160. // 找出最大值的节点
  161. func (tree *AVLTree) FindMaxValue() *AVLTreeNode {
  162. if tree.Root == nil {
  163. // 如果是空树,返回空
  164. return nil
  165. }
  166. return tree.Root.FindMaxValue()
  167. }
  168. func (node *AVLTreeNode) FindMaxValue() *AVLTreeNode {
  169. // 右子树为空,表面已经是最右的节点了,该值就是最大值
  170. if node.Right == nil {
  171. return node
  172. }
  173. // 一直右子树递归
  174. return node.Right.FindMaxValue()
  175. }
  176. // 查找指定节点
  177. func (tree *AVLTree) Find(value int64) *AVLTreeNode {
  178. if tree.Root == nil {
  179. // 如果是空树,返回空
  180. return nil
  181. }
  182. return tree.Root.Find(value)
  183. }
  184. func (node *AVLTreeNode) Find(value int64) *AVLTreeNode {
  185. if value == node.Value {
  186. // 如果该节点刚刚等于该值,那么返回该节点
  187. return node
  188. } else if value < node.Value {
  189. // 如果查找的值小于节点值,从节点的左子树开始找
  190. if node.Left == nil {
  191. // 左子树为空,表示找不到该值了,返回nil
  192. return nil
  193. }
  194. return node.Left.Find(value)
  195. } else {
  196. // 如果查找的值大于节点值,从节点的右子树开始找
  197. if node.Right == nil {
  198. // 右子树为空,表示找不到该值了,返回nil
  199. return nil
  200. }
  201. return node.Right.Find(value)
  202. }
  203. }
  204. // 删除指定的元素
  205. func (tree *AVLTree) Delete(value int64) {
  206. if tree.Root == nil {
  207. // 如果是空树,直接返回
  208. return
  209. }
  210. tree.Root = tree.Root.Delete(value)
  211. }
  212. func (node *AVLTreeNode) Delete(value int64) *AVLTreeNode {
  213. if node == nil {
  214. // 如果是空树,直接返回
  215. return nil
  216. }
  217. if value < node.Value {
  218. // 从左子树开始删除
  219. node.Left = node.Left.Delete(value)
  220. // 删除后要更新该子树高度
  221. node.Left.UpdateHeight()
  222. } else if value > node.Value {
  223. // 从右子树开始删除
  224. node.Right = node.Right.Delete(value)
  225. // 删除后要更新该子树高度
  226. node.Right.UpdateHeight()
  227. } else {
  228. // 找到该值对应的节点
  229. // 该节点没有左右子树
  230. // 第一种情况,删除的节点没有儿子,直接删除即可。
  231. if node.Left == nil && node.Right == nil {
  232. return nil // 直接返回nil,表示直接该值删除
  233. }
  234. // 该节点有两棵子树,选择更高的哪个来替换
  235. // 第二种情况,删除的节点下有两个子树,选择高度更高的子树下的节点来替换被删除的节点,如果左子树更高,选择左子树中最大的节点,也就是左子树最右边的叶子节点,如果右子树更高,选择右子树中最小的节点,也就是右子树最左边的叶子节点。最后,删除这个叶子节点。
  236. if node.Left != nil && node.Right != nil {
  237. // 左子树更高,拿左子树中最大值的节点替换
  238. if node.Left.Height > node.Right.Height {
  239. maxNode := node.Left
  240. for maxNode.Right != nil {
  241. maxNode = maxNode.Right
  242. }
  243. // 最大值的节点替换被删除节点
  244. node.Value = maxNode.Value
  245. node.Times = maxNode.Times
  246. // 把最大的节点删掉
  247. node.Left = node.Left.Delete(maxNode.Value)
  248. // 删除后要更新该子树高度
  249. node.Left.UpdateHeight()
  250. } else {
  251. // 右子树更高,拿右子树中最小值的节点替换
  252. minNode := node.Right
  253. for minNode.Left != nil {
  254. minNode = minNode.Left
  255. }
  256. // 最小值的节点替换被删除节点
  257. node.Value = minNode.Value
  258. node.Times = minNode.Times
  259. // 把最小的节点删掉
  260. node.Right = node.Right.Delete(minNode.Value)
  261. // 删除后要更新该子树高度
  262. node.Right.UpdateHeight()
  263. }
  264. } else {
  265. // 只有左子树或只有右子树
  266. // 只有一个子树,该子树也只是一个节点,将该节点替换被删除的节点,然后置子树为空
  267. if node.Left != nil {
  268. //第三种情况,删除的节点只有左子树,因为树的特征,可以知道左子树其实就只有一个节点,它本身,否则高度差就等于2了。
  269. node.Value = node.Left.Value
  270. node.Times = node.Left.Times
  271. node.Height = 1
  272. node.Left = nil
  273. } else if node.Right != nil {
  274. //第四种情况,删除的节点只有右子树,因为树的特征,可以知道右子树其实就只有一个节点,它本身,否则高度差就等于2了。
  275. node.Value = node.Right.Value
  276. node.Times = node.Right.Times
  277. node.Height = 1
  278. node.Right = nil
  279. }
  280. }
  281. // 找到值后,进行替换删除后,直接返回该节点
  282. return node
  283. }
  284. // 左右子树递归删除节点后需要平衡
  285. var newNode *AVLTreeNode
  286. // 相当删除了右子树的节点,左边比右边高了,不平衡
  287. if node.BalanceFactor() == 2 {
  288. if node.Left.BalanceFactor() >= 0 {
  289. newNode = RightRotation(node)
  290. } else {
  291. newNode = LeftRightRotation(node)
  292. }
  293. // 相当删除了左子树的节点,右边比左边高了,不平衡
  294. } else if node.BalanceFactor() == -2 {
  295. if node.Right.BalanceFactor() <= 0 {
  296. newNode = LeftRotation(node)
  297. } else {
  298. newNode = RightLeftRotation(node)
  299. }
  300. }
  301. if newNode == nil {
  302. node.UpdateHeight()
  303. return node
  304. } else {
  305. newNode.UpdateHeight()
  306. return newNode
  307. }
  308. }
  309. // 中序遍历
  310. func (tree *AVLTree) MidOrder() {
  311. tree.Root.MidOrder()
  312. }
  313. func (node *AVLTreeNode) MidOrder() {
  314. if node == nil {
  315. return
  316. }
  317. // 先打印左子树
  318. node.Left.MidOrder()
  319. // 按照次数打印根节点
  320. for i := 0; i <= int(node.Times); i++ {
  321. fmt.Println("value:", node.Value, " tree height:", node.BalanceFactor())
  322. }
  323. // 打印右子树
  324. node.Right.MidOrder()
  325. }
  326. // 验证是不是棵AVL树
  327. func (tree *AVLTree) IsAVLTree() bool {
  328. if tree == nil || tree.Root == nil {
  329. return true
  330. }
  331. // 判断节点是否符合 AVL 树的定义
  332. if tree.Root.IsRight() {
  333. return true
  334. }
  335. return false
  336. }
  337. // 判断节点是否符合 AVL 树的定义
  338. func (node *AVLTreeNode) IsRight() bool {
  339. if node == nil {
  340. return true
  341. }
  342. // 左右子树都为空,那么是叶子节点
  343. if node.Left == nil && node.Right == nil {
  344. // 叶子节点高度应该为1
  345. if node.Height == 1 {
  346. return true
  347. } else {
  348. fmt.Println("leaf node height is ", node.Height)
  349. return false
  350. }
  351. } else if node.Left != nil && node.Right != nil {
  352. // 左右子树都是满的
  353. // 左儿子必须比父亲小,右儿子必须比父亲大
  354. if node.Left.Value < node.Value && node.Right.Value > node.Value {
  355. } else {
  356. // 不符合 AVL 树定义
  357. fmt.Printf("father is %v lchild is %v, rchild is %v\n", node.Value, node.Left.Value, node.Right.Value)
  358. return false
  359. }
  360. bal := node.Left.Height - node.Right.Height
  361. if bal < 0 {
  362. bal = -bal
  363. }
  364. // 子树高度差不能大于1
  365. if bal > 1 {
  366. fmt.Println("sub tree height bal is ", bal)
  367. return false
  368. }
  369. // 如果左子树比右子树高,那么父亲的高度等于左子树+1
  370. if node.Left.Height > node.Right.Height {
  371. if node.Height == node.Left.Height+1 {
  372. } else {
  373. fmt.Printf("%#v height:%v,left sub tree height: %v,right sub tree height:%v\n", node, node.Height, node.Left.Height, node.Right.Height)
  374. return false
  375. }
  376. } else {
  377. // 如果右子树比左子树高,那么父亲的高度等于右子树+1
  378. if node.Height == node.Right.Height+1 {
  379. } else {
  380. fmt.Printf("%#v height:%v,left sub tree height: %v,right sub tree height:%v\n", node, node.Height, node.Left.Height, node.Right.Height)
  381. return false
  382. }
  383. }
  384. // 递归判断子树
  385. if !node.Left.IsRight() {
  386. return false
  387. }
  388. // 递归判断子树
  389. if !node.Right.IsRight() {
  390. return false
  391. }
  392. } else {
  393. // 只存在一棵子树
  394. if node.Right != nil {
  395. // 子树高度只能是1
  396. if node.Right.Height == 1 && node.Right.Left == nil && node.Right.Right == nil {
  397. if node.Right.Value > node.Value {
  398. // 右节点必须比父亲大
  399. } else {
  400. fmt.Printf("%v,(%#v,%#v) child", node.Value, node.Right, node.Left)
  401. return false
  402. }
  403. } else {
  404. fmt.Printf("%v,(%#v,%#v) child", node.Value, node.Right, node.Left)
  405. return false
  406. }
  407. } else {
  408. if node.Left.Height == 1 && node.Left.Left == nil && node.Left.Right == nil {
  409. if node.Left.Value < node.Value {
  410. // 左节点必须比父亲小
  411. } else {
  412. fmt.Printf("%v,(%#v,%#v) child", node.Value, node.Right, node.Left)
  413. return false
  414. }
  415. } else {
  416. fmt.Printf("%v,(%#v,%#v) child", node.Value, node.Right, node.Left)
  417. return false
  418. }
  419. }
  420. }
  421. return true
  422. }
  423. func main() {
  424. values := []int64{2, 3, 7, 10, 10, 10, 10, 23, 9, 102, 109, 111, 112, 113}
  425. // 初始化二叉查找树并添加元素
  426. tree := NewAVLTree()
  427. for _, v := range values {
  428. tree.Add(v)
  429. }
  430. // 找到最大值或最小值的节点
  431. fmt.Println("find min value:", tree.FindMinValue())
  432. fmt.Println("find max value:", tree.FindMaxValue())
  433. // 查找不存在的99
  434. node := tree.Find(99)
  435. if node != nil {
  436. fmt.Println("find it 99!")
  437. } else {
  438. fmt.Println("not find it 99!")
  439. }
  440. // 查找存在的9
  441. node = tree.Find(9)
  442. if node != nil {
  443. fmt.Println("find it 9!")
  444. } else {
  445. fmt.Println("not find it 9!")
  446. }
  447. // 删除存在的9后,再查找9
  448. tree.Delete(9)
  449. tree.Delete(10)
  450. tree.Delete(2)
  451. tree.Delete(3)
  452. tree.Add(4)
  453. tree.Add(3)
  454. tree.Add(10)
  455. tree.Delete(111)
  456. node = tree.Find(9)
  457. if node != nil {
  458. fmt.Println("find it 9!")
  459. } else {
  460. fmt.Println("not find it 9!")
  461. }
  462. // 中序遍历,实现排序
  463. tree.MidOrder()
  464. if tree.IsAVLTree() {
  465. fmt.Println("is a avl tree")
  466. } else {
  467. fmt.Println("is not avl tree")
  468. }
  469. }

运行结果:

  1. find min value: &{2 0 1 <nil> <nil>}
  2. find max value: &{113 0 1 <nil> <nil>}
  3. not find it 99!
  4. find it 9!
  5. not find it 9!
  6. value: 3 tree height: 0
  7. value: 4 tree height: 1
  8. value: 7 tree height: 0
  9. value: 10 tree height: 0
  10. value: 23 tree height: 1
  11. value: 102 tree height: 1
  12. value: 109 tree height: 0
  13. value: 112 tree height: 0
  14. value: 113 tree height: 0
  15. is a avl tree

可以看到,它确实是一棵 AVL 树。

PS:我们的程序是递归程序,如果改写为非递归形式,效率和性能会更好,在此就不实现了,理解AVL树添加和删除的总体思路即可。

八、应用场景

AVL 树作为严格平衡的二叉查找树,在 windows 对进程地址空间的管理被使用到。