AVL二叉查找树
AVL二叉查找树是一种特殊的二叉查找树，其规定
每个节点的左子树和右子树的高度差最多是1
AVL调整算法
AVL树插入一个新的节点到某个节点下破坏AVL树的要求时，对于破坏条件的第一个节点a（最靠近底部/深度最深的节点），具有四种情况：
- 插入a的左儿子节点的左子树
- 插入a的左儿子节点的右子树
- 插入a的右儿子节点的左子树
- 插入a的右儿子节点的右子树
其中，第一种和第四种可以看成一种情况的镜像，均是插入外侧；第二种和第三种可以看成另一种情况的镜像，均是插入内侧。这两种情况分别对应两种不同调整方法——单旋转和双旋转。其核心思想都相同，都是尽量将违规子树的父节点的位置尽量向上提。
单旋转调整
考虑入下左图所示的情况，假设X与Z的深度相同且，整棵树符合AVL条件：
单旋转
若插入一个小于b的值，则X的深度将+1，从a节点来看，左子树的深度就比右子树大2，不符合条件。调整的方法如右图所示，以下是调整的合理性：
- 查找树条件：X子树存储的数据小于b，Z子树存储的数据大于a，Y子树存储的数据范围时(b,a)，且a>b，由此看出转换后的数依然是一颗查找树。
- AVL条件：X深度比Z深1，但Z的位置要比X低1，因此a节点开始的树满足AVL条件。a树原来的深度为max{X+2,Y+2,Z+1}，现在a树的深度是max{X+1,Y+2,Z+2}。由于原树满足AVL条件，则Y的深度不会比原来X的深度深，所以深度分别为X1+2，X2+1，其中X2=X1+1，所以a节点深度不变，不影响上层AVL结构。
由此，只要将b提为树根，a放到b的右子树，再将Y挂到a的左子树就可以完成调整
| 待调整指针 | 调整前 | 调整后 |
|---|---|---|
| 树根指针 | a | b |
| b左儿子（不变） | X | X |
| b右儿子 | Y | a |
| a左儿子 | b | Y |
| a右儿子（不变） | Z | Z |
双旋转
考虑下左图情况
双旋转
设左图为一颗AVL树，X,Y的深度比W,Z浅1（X,Y深度相等，W,Z深度相等），假若在X或Y中插入一个节点，在a节点的AVL条件将不同，需要使用双旋转调整，调整成右图的样子，合理性如下：
- 查找树条件：对于W中的w，有w<b；对于X中的x，有b<x<c；对于Y中的y，有c<y<a；对于Z中的z，有z>a。且有b<c<a。在右侧数中以上均成立
- AVL条件：c的子树深度为1+max{W,X}，右侧深度为1+max{Y,Z}，W,X,Y,Z中有三个相同，另一个比其他都要浅1，则a的AVL条件成立。双旋转处理后c树深度不变，因此不影响上层的AVL条件
调整情况如下
| 待调整指针 | 调整前 | 调整后 |
|---|---|---|
| 树根节点 | a | c |
| a左儿子 | b | Y |
| a右儿子（不变） | Z | Z |
| b左儿子（不变） | W | W |
| b右儿子 | c | X |
| c左儿子 | X | b |
| c右儿子 | Y | a |
同时，双旋转可以看成b-c和c-a之间的两次单旋转：
双旋转转单旋转
代码实现
结构体
type tree_data struct {
data int
}
type tree_node struct {
num int
height int
data tree_data
parent *tree_node
left *tree_node
right *tree_node
}
构造函数
func New_tree_node(num int, data tree_data, parent *tree_node) *tree_node {
node := tree_node{}
node.num = num
node.data = data
node.height = 0
node.left = nil
node.right = nil
node.parent = parent
return &node
}
插入方法
func (t *tree_node) Insert(num int, data tree_data) {
if num > t.num {
if t.right != nil {
t.right.Insert(num, data)
//调整算法，向右子树插入，只能是右侧深度破坏条件
if t.GetLenght(t.right) > t.GetLenght(t.left)+1 {
if num > t.right.num {
//当待插入的数大于右侧标签，为插入右节点的右子树，单旋转
t.RightSimpleRotate()
} else {
//当待插入的数小于右侧标签，为插入右节点的左子树，双旋转
t.RightDoubleRotate()
}
}
} else {
//新建节点不会导致条件破坏
t.right = New_tree_node(num, data, t)
}
} else if num < t.num {
if t.left != nil {
t.left.Insert(num, data)
//调整算法，向左子树插入，只能是左侧深度破坏条件
if t.GetLenght(t.left) > t.GetLenght(t.right)+1 {
if num < t.left.num {
//当待插入的数小于左侧标签，为插入左节点的左子树，单旋转
t.LeftSimpleRotate()
} else {
//当待插入的数大于左侧标签，为插入左节点的右子树，双旋转
t.LeftDoubleRotate()
}
}
} else {
//新建节点不会导致条件破坏
t.left = New_tree_node(num, data, t)
}
} else {
t.data = data
}
t.compute_height()
}
单旋转方法
func (t *tree_node) LeftSimpleRotate() {
if t.parent.left == t {
t.parent.left = t.left
} else {
t.parent.right = t.left
}
temp := t.left.right
t.left.right = t
t.left.parent = t.parent
t.parent = t.left
t.left = temp
}
func (t *tree_node) RightSimpleRotate() {
if t.parent.left == t {
t.parent.left = t.right
} else {
t.parent.right = t.right
}
temp := t.right.left
t.right.left = t
t.right.parent = t.parent
t.parent = t.right
t.right = temp
}
双旋转
func (t *tree_node) LeftDoubleRotate() {
t.left.RightSimpleRotate()
t.LeftSimpleRotate()
}
func (t *tree_node) RightDoubleRotate() {
t.right.LeftSimpleRotate()
t.RightSimpleRotate()
}
其他方法
计算深度
func (t *tree_node) compute_height() {
t.height = int(math.Max(float64(t.GetLenght(t.left)), float64(t.GetLenght(t.right)))) + 1
}
获得深度
func (t *tree_node) GetLenght(node *tree_node) int {
if node == nil {
return -1
} else {
return node.height
}[图片上传中...(simple.png-2406ad-1514205437481-0)]
}
遍历
func (t *tree_node) Visit(indent string) {
fmt.Println(indent, t.num, t.GetLenght(t.left), t.GetLenght(t.right))
if t.left != nil {
t.left.Visit(indent + " ")
}
if t.right != nil {
t.right.Visit(indent + " ")
}
}
