概述
BST（二叉搜索樹）可以提高查找效率，理想的情況下BST的每個(gè)子樹的高度差相等（BST平衡）躁锁，搜索的時(shí)間復(fù)雜度為O(lgn)。如果數(shù)據(jù)有序或接近會(huì)導(dǎo)致生成BTS中出現(xiàn)線性結(jié)構(gòu)（BST失衡）超全，搜索的時(shí)間復(fù)雜度會(huì)變?yōu)镺(n)恬涧。
AVL（平衡二叉樹）是BST的一個(gè)進(jìn)化體， 得名于其發(fā)明者的名字（ Adelson-Velskii 以及 Landis）舶沿。對(duì)于AVL樹的每一個(gè)節(jié)點(diǎn)墙杯，它的左右子樹的高度之差不能超過1，如果插入或者刪除操作使得高度之差大于1括荡，就要進(jìn)行節(jié)點(diǎn)之間的旋轉(zhuǎn)高镐，將二叉樹重新維持在一個(gè)平衡狀態(tài)。
avl樹特點(diǎn)
AVL樹是一棵二叉搜索樹畸冲。
AVL樹的左右子節(jié)點(diǎn)也是AVL樹嫉髓。
每個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)的高度之差（簡稱平衡因子）的絕對(duì)值不超過1（故一個(gè)結(jié)點(diǎn)的平衡因子可以是-1/0/1）。
具體實(shí)現(xiàn)
AVL樹插入或刪除一個(gè)節(jié)點(diǎn)可能會(huì)導(dǎo)致AVL樹平衡因子的絕對(duì)值大于1邑闲，此時(shí)需要進(jìn)行旋轉(zhuǎn)操作以實(shí)現(xiàn)重新平衡算行。
旋轉(zhuǎn)
旋轉(zhuǎn)兩種情況，分別是左旋和右旋苫耸。以右旋操作為例州邢， 節(jié)點(diǎn)B上升同時(shí)節(jié)點(diǎn)A下降為節(jié)點(diǎn)B的右子節(jié)點(diǎn)，原節(jié)點(diǎn)B的右子節(jié)點(diǎn)D變?yōu)楣?jié)點(diǎn)A的左子節(jié)點(diǎn)褪子。左旋操作同理量淌。
失衡
實(shí)際情況下無外乎如下圖所示4種失衡狀態(tài)骗村。
重平衡
這四種失衡狀態(tài)都可以通過一次或兩次旋轉(zhuǎn)達(dá)到重平衡狀態(tài)。其中 case1和case2通過一次旋轉(zhuǎn)即可重新平衡呀枢，case3和case4需要做兩次旋轉(zhuǎn)達(dá)到平衡叙身。
- case3 先對(duì)y節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)， 再對(duì)z節(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)
- case4 先對(duì)z節(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)硫狞，再對(duì)x節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)信轿。
代碼實(shí)現(xiàn)
結(jié)構(gòu)定義
為了計(jì)算平衡因子，需要在節(jié)點(diǎn)增加一個(gè)高度屬性残吩， 用于存儲(chǔ)左右子樹高度的最大值财忽。
type Node struct {
Left *Node
Right *Node
Height int
Key int
Val interface{}
}
平衡因子計(jì)算
節(jié)點(diǎn)的平衡因子為左右子樹的高度差
//獲取節(jié)點(diǎn)高度
func (n *Node) GetHeight() int {
if n == nil {
return 0
}
return n.Height
}
//節(jié)點(diǎn)高度差
func (n *Node) GetBalanceFactor() int {
if n == nil {
return -1
}
return n.Left.GetHeight() - n.Right.GetHeight()
}
節(jié)點(diǎn)旋轉(zhuǎn)
//左旋轉(zhuǎn)
func (n *Node) LeftRotation() *Node {
root, newRoot := n, n.Right
//旋轉(zhuǎn)
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
}
//右旋轉(zhuǎn)
func (n *Node) RightRotation() *Node {
root, newRoot := n, n.Left
//旋轉(zhuǎn)
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
}
節(jié)點(diǎn)插入
當(dāng)需要插入一個(gè)新結(jié)點(diǎn)時(shí)，從根節(jié)點(diǎn)開始遞歸查找泣侮，直到找到或nil即彪， 執(zhí)行更新或插入操作。節(jié)點(diǎn)插入完成后活尊，依次檢查所有父節(jié)點(diǎn)是否失衡隶校。
代碼中 balance 為 n.left.height - n.right.height, 如果balance的絕對(duì)值大于1，則當(dāng)前節(jié)點(diǎn)失衡蛹锰。當(dāng)balance > 1時(shí)深胳，則說明插入節(jié)點(diǎn)在左側(cè)，反之在右側(cè)铜犬。如果插入key小于節(jié)點(diǎn)key舞终， 則說明插入節(jié)點(diǎn)在左側(cè)，反之在右側(cè)癣猾。由此可以判斷出是否存在四種失衡情況敛劝。
//插入
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
}
節(jié)點(diǎn)刪除
節(jié)點(diǎn)刪除步驟：
遞歸查找要?jiǎng)h除的節(jié)點(diǎn)， 如未找到則不處理纷宇。
-
刪除節(jié)點(diǎn)是否存在子節(jié)點(diǎn)夸盟。
若不存在子節(jié)點(diǎn)直接刪除。
若存在一個(gè)子節(jié)點(diǎn)像捶， 刪除節(jié)點(diǎn)后子節(jié)點(diǎn)接上
若存在兩個(gè)子節(jié)點(diǎn)上陕， 查找右子樹中最小子節(jié)點(diǎn)替換掉待刪除節(jié)點(diǎn)，刪除右子樹中最小子節(jié)點(diǎn)作岖。
判斷時(shí)候失衡唆垃，失衡則重平衡。
//刪除
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個(gè)或1個(gè)子節(jié)點(diǎn)
if root.Left == nil || root.Right == nil {
//沒做子節(jié)點(diǎn)
if root.Left == nil && root.Right == nil {
return nil
}
if root.Left != nil {
root = root.Left
} else {
root = root.Right
}
} else {
//查找最小子節(jié)點(diǎn)
minNode := root.Right.SearchMinNode()
//替換當(dāng)前節(jié)點(diǎn)
root.Key = minNode.Key
root.Val = minNode.Val
//刪除替換節(jié)點(diǎn)
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
}
//查找最小節(jié)點(diǎn)
func (n *Node) SearchMinNode() *Node {
cur := n
for cur.Left != nil {
cur = cur.Left
}
return cur
}
