【计算机基础——数据结构——AVL平衡二叉树】

1. BST二叉查找树

1.1 BST二叉查找树的特性

• 左子树上所有结点的值均小于或等于它的根结点的值。
• 右子树上所有结点的值均大于或等于它的根结点的值。
• 左、右子树也分别为二叉排序树。

1.2 BST二叉查找树的缺点

• 二叉查找树是有缺点的，在不断插入的时候，有可能出现这样一种情况：很容易“退化”成链表，
• 如果bst 树的节点正好从大到小的插入，此时树的结构也类似于链表结构，这时候的查询或写入耗时与链表相同。

为了避免这种特殊的情况发生，引入了平衡二叉树（AVL）和红黑树（red-black tree）

2. AVL平衡二叉树

平衡二叉树也叫AVL（发明者名字简写），也属于二叉搜索树的一种，与其不同的是AVL通过机制保证其自身的平衡。

AVL树是最先发明的自平衡二叉查找树。
在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。
增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

2.1 AVL树的特性

AVL树本质上还是一棵二叉搜索树，它有以下特性：

• 特性1： 对于任何一颗子树的root根结点而言，它的左子树任何节点的key一定比root小，而右子树任何节点的key 一定比root大；
• 特性2：对于AVL树而言，其中任何子树仍然是AVL树；
• 特性3：每个节点的左右子节点的高度之差的绝对值最多为1；

在插入、删除树节点的时候，如果破坏了以上的原则，AVL树会自动进行调整使得以上三条原则仍然成立。

2.2 AVL树的平衡功能

举个例子，下左图为AVL树最长的2节点与最短的8节点高度差为1；

当插入一个新的节点后，根据上面第一条原则，它会出现在2节点的左子树，但这样一来就违反了原则3。

此时AVL树会通过节点的旋转进行进行平衡，

AVL调整的过程称之为左旋和右旋，左旋就是逆时针转，右旋是顺时针转

2.3 AVL平衡的调整过程

调整的过程：

1. 确定旋转支点（pivot）：这个旋转支点就是失去平衡这部分树，在自平衡之后的根节点，平衡的调整过程，需要根据pivot它来进行旋转。我们只关注失衡子树的根结点 及它的子节点和孙子节点即可。
2. 判断AVL失衡的类型：包含左左结构失衡（LL型失衡）、右右结构失衡（RR型失衡）、左右结构失衡（LR型失衡）、右左结构失衡（RL型失衡）
3. 根据失衡的类型进行相应的旋转

2.3.1 场景1：LL失衡-左左结构失衡（右旋）

在结点Root的 左结点（L） 的 左子树（L） 上做了插入元素的操作，我们称这种情况为 左左型 ，我们应该进行右旋转。

2.3.2 场景2：RR型失衡：右右结构失衡（左旋）

在结点Root的 右结点（R） 的 右子树（R） 上做了插入元素的操作，我们称这种情况为右右型 ，我们应该进行左旋转。

2.3.3 场景3： LR型失衡：左右失衡（左旋+右旋）：

在结点Root的 左结点（L） 的 右子树（R） 上做了插入元素的操作，我们称这种情况为左右型 ，我们应该进行左旋转+右旋转。

2.3.4 场景4：RL失衡: 右左结构 （右旋+左旋）：

在结点Root的 右结点（R） 的 左子树（L） 上做了插入元素的操作，我们称这种情况为右左型 ，我们应该进行右旋转+左旋转。

3. 代码实现+详细注解

3.1 基本结构+操作

package mainimport "fmt"// AVL树的节点
type Node struct {Key    intHeight intLeft   *NodeRight  *Node
}type AVLTree struct {Root *Node
}// 返回节点的高度
func height(n *Node) int {if n == nil {return 0}return n.Height
}func max(a, b int) int {if a > b {return a}return b
}// 返回当前节点的平衡因子
func getBalance(n *Node) int {if n == nil {return 0}return height(n.Left) - height(n.Right)
}// 右旋
func rightRotate(root *Node) *Node {//pivot是新的根节点，T2是要转移的子树的根pivot := root.LeftT2 := pivot.Rightpivot.Right = rootroot.Left = T2// 重新计算两个调整后的节点高度root.Height = max(height(root.Left), height(root.Right)) + 1pivot.Height = max(height(pivot.Left), height(pivot.Right)) + 1return pivot
}// 右旋
func leftRotate(root *Node) *Node {//pivot是新的根节点，T2是要转移的子树的根pivot := root.RightT2 := pivot.Leftpivot.Left = rootroot.Right = T2// 重新计算两个调整后的节点高度root.Height = max(height(root.Left), height(root.Right)) + 1pivot.Height = max(height(pivot.Left), height(pivot.Right)) + 1return pivot
}// 查找
func (t *AVLTree) Search(key int) *Node {return search(t.Root, key)
}func search(node *Node, key int) *Node {if node == nil {return nil}if key == node.Key {return node}if key < node.Key {return search(node.Left, key)}return search(node.Right, key)
}

3.2 插入操作

func (t *AVLTree) Insert(key int) {t.Root = insert(t.Root, key)
}func insert(node *Node, key int) *Node {// 1. 找到插入节点的位置if node == nil {return &Node{Key: key, Height: 1}}if key < node.Key {node.Left = insert(node.Left, key)} else if key > node.Key {node.Right = insert(node.Right, key)} else {//重复的key是不被允许的return node}// 2. 更新新插入节点的祖先节点的高度node.Height = max(height(node.Left), height(node.Right)) + 1// 3. 获得当前节点的平衡因子balance := getBalance(node)// 4. 平衡调整// 4.1说明新插入的节点插入到了当前节点的左节点的左孩子，需要进行右旋if balance > 1 && key < node.Left.Key {return rightRotate(node)}// 4.2说明新插入的节点插入到了当前节点的右节点的右孩子，需要进行左旋if balance < -1 && key > node.Right.Key {return leftRotate(node)}// 4.3说明新插入的节点插入到了当前节点的左节点的右孩子，需要进行左旋+右旋if balance > 1 && key > node.Right.Key {node.Left = leftRotate(node.Left)return rightRotate(node)}// 4.4说明新插入的节点插入到了当前节点的右节点的左孩子，需要进行右旋+左旋if balance < -1 && key < node.Left.Key {node.Right = rightRotate(node.Right)return leftRotate(node)}// 4.5 不要需要进行平衡调整return node
}

3.3 删除操作

func (t *AVLTree) Delete(key int) {t.Root = delete(t.Root, key)
}func delete(node *Node, key int) *Node {if node == nil {return nil}// 1. 找到要删除的节点if key < node.Key {node.Left = delete(node.Left, key)} else if key > node.Key {node.Right = delete(node.Right, key)} else {// 被删除的节点是叶子节点或者只有一个孩子节点if node.Left == nil {return node.Right} else if node.Right == nil {return node.Left}// 被删除的节点下面还有两个孩子节点// 先找到被删除节点下面最小的值temp := minValueNode(node.Right)// 将最小的值放到当前节点node.Key = temp.Key// 递归删除最小值node.Right = delete(node.Right, temp.Key)}if node == nil {return node}// 2. 更新新插入节点的祖先节点的高度node.Height = max(height(node.Left), height(node.Right)) + 1// 3. 获得当前节点的平衡因子balance := getBalance(node)// 4. 平衡调整// 4.1说明新删除的节点导致当前节点的平衡因子出了问题，//	  判断是当前节点左节点的左孩子造成的，需要进行右旋if balance > 1 && getBalance(node.Left) >= 0 {return rightRotate(node)}// 4.2说明新删除的节点导致当前节点的平衡因子出了问题，//	  判断是当前节点右节点的右孩子造成的，需要进行左旋if balance < -1 && getBalance(node.Right) <= 0 {return leftRotate(node)}// 4.3说明新删除的节点导致当前节点的平衡因子出了问题，//  判断是当前节点左节点的右孩子造成的，需要进行左旋+右旋if balance > 1 && getBalance(node.Left) < 0 {node.Left = leftRotate(node.Left)return rightRotate(node)}// 4.4说明新删除的节点导致当前节点的平衡因子出了问题，//    判断是当前节点右节点的左孩子造成的，需要进行右旋+左旋if balance < -1 && getBalance(node.Right) > 0 {node.Right = rightRotate(node.Right)return leftRotate(node)}// 4.5 不要需要进行平衡调整return node
}func minValueNode(node *Node) *Node {current := nodefor current.Left != nil {current = current.Left}return current
}

3.4 测试

func main() {tree := &AVLTree{}// 插入节点tree.Insert(10)tree.Insert(20)tree.Insert(30)tree.Insert(40)tree.Insert(50)tree.Insert(60)tree.Insert(70)// 层次遍历fmt.Println(LevelOrder(tree.Root))tree.Delete(10)tree.Delete(20)tree.Delete(30)fmt.Println(LevelOrder(tree.Root))
}// LevelOrder 返回层次遍历的结果（按层分组）
func LevelOrder(root *Node) [][]int {result := make([][]int, 0)if root == nil {return result}// 使用队列来存储节点queue := []*Node{root}for len(queue) > 0 {// 当前层的节点数levelSize := len(queue)// 存储当前层的值currentLevel := make([]int, 0, levelSize)// 遍历当前层的所有节点for i := 0; i < levelSize; i++ {// 获取队首节点node := queue[0]queue = queue[1:] // 出队// 将当前节点的值加入当前层的结果中currentLevel = append(currentLevel, node.Key)// 将子节点加入队列if node.Left != nil {queue = append(queue, node.Left)}if node.Right != nil {queue = append(queue, node.Right)}}// 将当前层的结果加入最终结果result = append(result, currentLevel)}return result
}

层次遍历的结果，符合预期