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

一、AVL树介绍

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

定义如下：

  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. }
  6. // AVL节点
  7. type AVLTreeNode struct {
  8.     Value  int64                 // 值
  9.     Times  int64                 // 值出现的次数
  10.     Height int64                 // 该节点作为树根节点，树的高度，方便计算平衡因子
  11.     Left   *AVLTreeNode // 左子树
  12.     Right  *AVLTreeNode // 右字树
  13. }
  15. // 初始化一个AVL树
  16. func NewAVLTree() *AVLTree {
  17.     return new(AVLTree)
  18. }

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

更新树的高度，代码如下：

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

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

  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
  9.     // 只有Root和Pivot变化了高度
  10.     Root.UpdateHeight()
  11.     Pivot.UpdateHeight()
  12.     return Pivot
  13. }

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
  9.     // 只有Root和Pivot变化了高度
  10.     Root.UpdateHeight()
  11.     Pivot.UpdateHeight()
  12.     return Pivot
  13. }

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

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

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

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

四、AVL树查找元素等操作

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

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

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

五、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.         }
  24.         // 该节点有两棵子树，选择更高的哪个来替换
  25.         // 第二种情况，删除的节点下有两个子树，选择高度更高的子树下的节点来替换被删除的节点，如果左子树更高，选择左子树中最大的节点，也就是左子树最右边的叶子节点，如果右子树更高，选择右子树中最小的节点，也就是右子树最左边的叶子节点。最后，删除这个叶子节点。
  26.         if node.Left != nil && node.Right != nil {
  27.             // 左子树更高，拿左子树中最大值的节点替换
  28.             if node.Left.Height > node.Right.Height {
  29.                 maxNode := node.Left
  30.                 for maxNode.Right != nil {
  31.                     maxNode = maxNode.Right
  32.                 }
  34.                 // 最大值的节点替换被删除节点
  35.                 node.Value = maxNode.Value
  36.                 node.Times = maxNode.Times
  38.                 // 把最大的节点删掉
  39.                 node.Left = node.Left.Delete(maxNode.Value)
  40.                 // 删除后要更新该子树高度
  41.                 node.Left.UpdateHeight()
  42.             } else {
  43.                 // 右子树更高，拿右子树中最小值的节点替换
  44.                 minNode := node.Right
  45.                 for minNode.Left != nil {
  46.                     minNode = minNode.Left
  47.                 }
  49.                 // 最小值的节点替换被删除节点
  50.                 node.Value = minNode.Value
  51.                 node.Times = minNode.Times
  53.                 // 把最小的节点删掉
  54.                 node.Right = node.Right.Delete(minNode.Value)
  55.                 // 删除后要更新该子树高度
  56.                 node.Right.UpdateHeight()
  57.             }
  58.         } else {
  59.             // 只有左子树或只有右子树
  60.             // 只有一个子树，该子树也只是一个节点，将该节点替换被删除的节点，然后置子树为空
  61.             if node.Left != nil {
  62.                 //第三种情况，删除的节点只有左子树，因为树的特征，可以知道左子树其实就只有一个节点，它本身，否则高度差就等于2了。
  63.                 node.Value = node.Left.Value
  64.                 node.Times = node.Left.Times
  65.                 node.Height = 1
  66.                 node.Left = nil
  67.             } else if node.Right != nil {
  68.                 //第四种情况，删除的节点只有右子树，因为树的特征，可以知道右子树其实就只有一个节点，它本身，否则高度差就等于2了。
  69.                 node.Value = node.Right.Value
  70.                 node.Times = node.Right.Times
  71.                 node.Height = 1
  72.                 node.Right = nil
  73.             }
  74.         }
  76.         // 找到值后，进行替换删除后，直接返回该节点
  77.         return node
  78.     }
  80.     // 左右子树递归删除节点后需要平衡
  81.     var newNode *AVLTreeNode
  82.     // 相当删除了右子树的节点，左边比右边高了，不平衡
  83.     if node.BalanceFactor() == 2 {
  84.         if node.Left.BalanceFactor() >= 0 {
  85.             newNode = RightRotation(node)
  86.         } else {
  87.             newNode = LeftRightRotation(node)
  88.         }
  89.         //  相当删除了左子树的节点，右边比左边高了，不平衡
  90.     } else if node.BalanceFactor() == -2 {
  91.         if node.Right.BalanceFactor() <= 0 {
  92.             newNode = LeftRotation(node)
  93.         } else {
  94.             newNode = RightLeftRotation(node)
  95.         }
  96.     }
  98.     if newNode == nil {
  99.         node.UpdateHeight()
  100.         return node
  101.     } else {
  102.         newNode.UpdateHeight()
  103.         return newNode
  104.     }
  105. }

当删除的值不等于当前节点的值时，在相应的子树中递归删除，递归过程中会自底向上维护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.                 }
  11.                 // 最大值的节点替换被删除节点
  12.                 node.Value = maxNode.Value
  13.                 node.Times = maxNode.Times
  15.                 // 把最大的节点删掉
  16.                 node.Left = node.Left.Delete(maxNode.Value)
  17.                 // 删除后要更新该子树高度
  18.                 node.Left.UpdateHeight()
  19.             } else {
  20.                 // 右子树更高，拿右子树中最小值的节点替换
  21.                 minNode := node.Right
  22.                 for minNode.Left != nil {
  23.                     minNode = minNode.Left
  24.                 }
  26.                 // 最小值的节点替换被删除节点
  27.                 node.Value = minNode.Value
  28.                 node.Times = minNode.Times
  30.                 // 把最小的节点删掉
  31.                 node.Right = node.Right.Delete(minNode.Value)
  32.                 // 删除后要更新该子树高度
  33.                 node.Right.UpdateHeight()
  34.             }
  35.         }

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

运行请看完整代码。

七、AVL树完整代码

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

运行结果：

  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 对进程地址空间的管理被使用到。