引言
AVL树，基于二叉搜索树通过平衡得到
前面我们知道，通过🔗二叉搜索树可以便捷快速地查找到数据，但是当序列有序时，就会退化成如下图所示的单链表，搜索效率降低为O(N)，为了解决这个问题，引出了平衡二叉树（AVL树）
定义
平衡二叉树，简称AVL树，它可以是一颗空树
如果不是空树，则需要满足 任何一个结点的左子树与右子树高度之差的绝对值不超过1
图一是AVL树
图二不是AVL树，因为虚线内部分高度差大于1
如何让二叉树变成AVL树呢
答案是通过旋转（左旋、右旋）操作，在说左旋和右旋操作之前，了解一个概念——平衡因子
是否为AVL树需要根据结点的左右子树高度差来判断，所以引出平衡因子的概念
平衡因子：结点左子树高度减去右子树高度
之后我们还可以通过平衡因子来判断需要哪种旋转方式（左旋、右旋）
将二叉树分为四种类型，分别是LL（left）型、RR（right）型、
LR型、RL型
这几种类型是根据引起不平衡的结点的位置来分的，下面将引起不平衡的这个结点叫做unbalanceNode
旋转方式
判断右旋还是左旋，可以这样理解
向哪个方向旋转就是让哪边树更高。比如左旋，就是右子树高于左子树，要想平衡就要让左子树更高一点
LL型
unbalanceNode在根结点左孩子的左子树 – 根结点右旋
如图，插入结点5后导致二叉树失衡，插入的结点5在根结点左孩子14的左子树上，所以就是 LL 型
LL型二叉树的平衡因子满足：
根结点：2
根结点的左孩子：1（左孩子的左子树高度>右子树）
方法就是将根结点右旋，意思就是将根结点向右旋转到其左孩子的右孩子的位置
在根结点向右旋转的过程中，因为根结点的左孩子14原本有右孩子20，所以根结点就会和20发生冲突，这时需要将14的右孩子20变成根结点的左孩子
根结点25旋转完成后就是
再和14相连，最终结果：
如果出现了多个结点都失衡的情况，如下图
46、35、24都失衡了，那这时候就不是将根结点右旋了，而是将 与导致失衡的结点（15）最近的失衡结点右旋，在这个例子中也就是将24右旋
再与35相连，最终结果：
RR型
unbalanceNode在根结点右孩子的右子树 – 根结点左旋
RR 型与 LL 型方法一致，只是换汤不换药
如图，插入结点67后导致二叉树失衡，插入的结点67在根结点右孩子45的右子树上，所以就是 RR 型
RR型二叉树的平衡因子满足：
根结点：-2
根结点的左孩子：-1（左孩子的右子树高度>左子树）
方法就是将根结点左旋，意思就是将根结点向左旋转到其右孩子的左孩子的位置
在根结点向左旋转的过程中，因为根结点的右孩子45原本有左孩子34，所以根结点就会和34发生冲突，这时需要将45的左孩子34变成根结点的右孩子
根结点26旋转完成后就是
再和45相连，最终结果：
如果同时出现了多个失衡结点，和 LL 型一样，也是找到与导致失衡结点距离最近的失衡的结点，对该结点进行左旋操作
LR型
unbalanceNode在根结点左孩子的右子树 – 先左旋再右旋（根结点的左孩子左旋，根结点右旋）
如图，插入结点40后导致二叉树失衡，插入的结点40在根结点左孩子25的右子树上，所以就是 LR 型
LR型的平衡因子满足：
根结点：2
根结点的左孩子：-1（左孩子的右子树高度>左子树）
方法就是
- 先将根结点的左孩子左旋
- 再将根结点右旋
对于这个二叉树，调整过程：
- 将根结点的左孩子左旋
- 将根结点右旋后
RL型
unbalanceNode在根结点右孩子的左子树 – 先右旋再左旋（根结点的右孩子右旋，根结点左旋）
如图，插入结点29后导致二叉树失衡，插入的结点29在根结点右孩子48的左子树上，所以就是 RL 型
LR型的平衡因子满足：
根结点：-2
根结点的右孩子：1（右孩子的左子树高度>右子树）
方法就是
- 先将根结点的右孩子右旋
- 再将根结点左旋
对于这个二叉树，调整过程：
将根结点的右孩子右旋
将根结点左旋
实现
结构
结构体中一定包含的是数据data 和左右孩子指针
又因为需要计算平衡因子，所以需要知道左右子树的高度，直接将高度height 包含在结构体中
// 定义树结构
type BTNode struct {
data int //数据
left *BTNode
right *BTNode
height int //树的高度
}
获取结点高度
首先判断结点 t 为不为 nil， 为 nil 直接返回0
// 获取结点高度
func (t *BTNode) GetHeight() int {
if t == nil {
return 0
}
return t.height
}
平衡因子
平衡因子 = 左子树高度 - 右子树高度
若结点 t 为 nil ，直接返回0
// 计算结点的平衡因子 -- 左子树高度-右子树高度
func (t *BTNode) GetBalanceFactor() int {
if t == nil {
return 0
}
return t.left.GetHeight() - t.right.GetHeight()
}
更新高度
在插入或删除数据后，根结点和其他结点的高度都有可能发生变化，所以在插入或删除结点后，需要更新节点的高度，否则在计算平衡因子会出错
// 更新高度
func (t *BTNode) UpdateHeight() {
leftHeight := t.left.GetHeight()
rightHeight := t.right.GetHeight()
if leftHeight > rightHeight {
t.height = leftHeight + 1
} else {
t.height = rightHeight + 1
}
}
左旋
对 node 进行左旋 --> node连接在node.right 的左孩子，如果node.right 原本有左孩子leftChild，那让leftChild 连接到node 的右孩子
// 左旋
func (t *BTNode) LeftRotate() *BTNode {
//新的根结点变为t的右孩子
newT := t.right
//判断newT有没有左孩子
if newT.left == nil{ //newT原本没有左孩子，t为newt.T左孩子
newT.left = t
}else { //newT原本有左孩子，原本的左孩子变为t的右孩子，t为newT左孩子
t.right = newT.left
newT.left = t
}
//更新高度
t.UpdateHeight()
newT.UpdateHeight()
return newT
}
对上面的代码，还可以再简化
如果newT没有左孩子，即为nil，也可以直接赋值给t.right
// 左旋
func (t *BTNode) LeftRotate() *BTNode {
//新的根结点变为t的右孩子
newT := t.right
t.right = newT.left
newT.left = t
//更新高度
t.UpdateHeight()
newT.UpdateHeight()
return newT
}
右旋
对 node 进行右旋 --> node连接在node.left 的右孩子，如果node.left 原本有右孩子rightChild，那让rightChild 连接到node 的左孩子
// 右旋
func (t *BTNode) RightRotate() *BTNode {
newT := t.left
t.left = newT.right
newT.right = t
t.UpdateHeight()
newT.UpdateHeight()
return newT
}
插入结点
按照二叉搜索树插入数据的方式插入，再根据平衡因子判断是否需要调整和调整的方式
// 插入结点
func (t *BTNode) Insert(data int) *BTNode {
if t == nil {
return &BTNode{
data,
nil,
nil,
1,
}
}
//递归查找插入位置
if data < t.data {
t.left = t.left.Insert(data)
} else if data > t.data {
t.right = t.right.Insert(data)
} else {
return t //不支持重复数据
}
//更新当前结点的高度
t.UpdateHeight()
//检查是否需要旋转
balance := t.GetBalanceFactor()
//左子树高
if balance > 1 {
if t.left.GetHeight() == 1 { //左孩子的左子树高 -- ll型
//右旋
return t.RightRotate()
}
if t.left.GetHeight() == -1 { //左孩子的右子树高 -- lr型
//先对左孩子左旋，再对结点右旋
t.left.LeftRotate()
return t.RightRotate()
}
}
//右子树高
if balance < -1 {
if t.right.GetHeight() == 1 { //右孩子的右子树高 -- rr型
return t.LeftRotate()
}
if t.right.GetHeight() == -1 { //右孩子的左子树高 -- rl型
先对右孩子右旋，再对结点左旋
t.right.RightRotate()
return t.LeftRotate()
}
}
return t
}
中序遍历
// 中序遍历
func (t *BTNode) InOrder() {
if t == nil {
return
}
t.left.InOrder()
fmt.Printf("%d ", t.data)
t.right.InOrder()
}