概述
BST（二叉搜索树）可以提高查找效率，理想的情况下BST的每个子树的高度差相等（BST平衡），搜索的时间复杂度为O(lgn)。如果数据有序或接近会导致生成BTS中出现线性结构（BST失衡），搜索的时间复杂度会变为O(n)。
AVL（平衡二叉树）是BST的一个进化体， 得名于其发明者的名字（ Adelson-Velskii 以及 Landis）。对于AVL树的每一个节点，它的左右子树的高度之差不能超过1，如果插入或者删除操作使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。
avl树特点
-
AVL树是一棵二叉搜索树。
-
AVL树的左右子节点也是AVL树。
-
每个节点的左右子节点的高度之差（简称平衡因子）的绝对值不超过1（故一个结点的平衡因子可以是-1/0/1）。
具体实现
AVL树插入或删除一个节点可能会导致AVL树平衡因子的绝对值大于1，此时需要进行旋转操作以实现重新平衡。
旋转
旋转两种情况，分别是左旋和右旋。以右旋操作为例， 节点B上升同时节点A下降为节点B的右子节点，原节点B的右子节点D变为节点A的左子节点。左旋操作同理。
image-20200214222026784.png
失衡
实际情况下无外乎如下图所示4种失衡状态。
WeChat9cea3c866502213c05506d647591a5ee.png
重平衡
这四种失衡状态都可以通过一次或两次旋转达到重平衡状态。其中 case1和case2通过一次旋转即可重新平衡，case3和case4需要做两次旋转达到平衡。
- case3 先对y节点进行左旋转， 再对z节点进行右旋转
- case4 先对z节点进行右旋转，再对x节点进行左旋转。
image-20200214220940353.png
代码实现
结构定义
为了计算平衡因子，需要在节点增加一个高度属性， 用于存储左右子树高度的最大值。
type Node struct {
Left *Node
Right *Node
Height int
Key int
Val interface{}
}
平衡因子计算
节点的平衡因子为左右子树的高度差
//获取节点高度
func (n *Node) GetHeight() int {
if n == nil {
return 0
}
return n.Height
}
//节点高度差
func (n *Node) GetBalanceFactor() int {
if n == nil {
return -1
}
return n.Left.GetHeight() - n.Right.GetHeight()
}
节点旋转
//左旋转
func (n *Node) LeftRotation() *Node {
root, newRoot := n, n.Right
//旋转
root.Right = newRoot.Left
newRoot.Left = root
//更新高度
root.Height = Max(root.Left.GetHeight(), root.Right.GetHeight()) + 1
newRoot.Height = Max(newRoot.Left.GetHeight(), newRoot.Right.GetHeight()) + 1
return newRoot
}
//右旋转
func (n *Node) RightRotation() *Node {
root, newRoot := n, n.Left
//旋转
root.Left = newRoot.Right
newRoot.Right = root
//更新高度
root.Height = Max(root.Left.GetHeight(), root.Right.GetHeight()) + 1
newRoot.Height = Max(newRoot.Left.GetHeight(), newRoot.Right.GetHeight()) + 1
return newRoot
}
节点插入
当需要插入一个新结点时，从根节点开始递归查找，直到找到或nil， 执行更新或插入操作。节点插入完成后，依次检查所有父节点是否失衡。
代码中 balance 为 n.left.height - n.right.height, 如果balance的绝对值大于1，则当前节点失衡。当balance > 1时，则说明插入节点在左侧，反之在右侧。如果插入key小于节点key， 则说明插入节点在左侧，反之在右侧。由此可以判断出是否存在四种失衡情况。
//插入
func (n *Node) Insert(key int, val interface{}) *Node {
if n == nil {
return &Node{
Height: 1,
Key: key,
Val: val,
}
}
if key < n.Key {
n.Left = n.Left.Insert(key, val)
} else if key > n.Key {
n.Right = n.Right.Insert(key, val)
} else {
n.Val = val
return n
}
//更新高度
n.Height = Max(n.Left.GetHeight(), n.Right.GetHeight()) + 1
balance := n.GetBalanceFactor()
//case1
if balance > 1 && key < n.Left.Key {
return n.RightRotation()
}
//case2
if balance < -1 && key > n.Right.Key {
return n.LeftRotation()
}
//case3
if balance > 1 && key > n.Left.Key {
n.Left = n.Left.LeftRotation()
return n.RightRotation()
}
//case4
if balance < -1 && key < n.Right.Key {
n.Right = n.Right.RightRotation()
return n.LeftRotation()
}
return n
}
节点删除
节点删除步骤：
-
递归查找要删除的节点， 如未找到则不处理。
-
删除节点是否存在子节点。
-
若不存在子节点直接删除。
-
若存在一个子节点， 删除节点后子节点接上
-
若存在两个子节点， 查找右子树中最小子节点替换掉待删除节点，删除右子树中最小子节点。
-
-
判断时候失衡，失衡则重平衡。
//删除
func (n *Node) Delete(key int) *Node {
root := n
if root == nil {
return nil
}
if key < root.Key {
root.Left = root.Left.Delete(key)
} else if key > root.Key {
root.Right = root.Right.Delete(key)
} else {
//存在 0个或1个子节点
if root.Left == nil || root.Right == nil {
//没做子节点
if root.Left == nil && root.Right == nil {
return nil
}
if root.Left != nil {
root = root.Left
} else {
root = root.Right
}
} else {
//查找最小子节点
minNode := root.Right.SearchMinNode()
//替换当前节点
root.Key = minNode.Key
root.Val = minNode.Val
//删除替换节点
root.Right = root.Right.Delete(minNode.Key)
}
}
root.Height = Max(root.Left.GetHeight(), root.Right.GetHeight()) + 1
balance := root.GetBalanceFactor()
if balance > 1 {
leftBalance := root.Left.GetBalanceFactor()
if leftBalance >= 0 {
return root.RightRotation()
} else {
root.Left = root.Left.LeftRotation()
return root.RightRotation()
}
} else if balance < -1 {
rightBalance := root.Right.GetBalanceFactor()
if rightBalance <= 0 {
return root.LeftRotation()
} else {
root.Right = root.Right.RightRotation()
return root.LeftRotation()
}
}
return root
}
//查找最小节点
func (n *Node) SearchMinNode() *Node {
cur := n
for cur.Left != nil {
cur = cur.Left
}
return cur
}
网友评论