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\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之间的两次单旋转：

代码实现

结构体

1
2
3
4
5
6
7
8
9
10
11
12
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
}

构造函数

1
2
3
4
5
6
7
8
9
10
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
}

插入方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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()
}

单旋转方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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
}

双旋转

1
2
3
4
5
6
7
8
9
func (t *tree_node) LeftDoubleRotate() {
	t.left.RightSimpleRotate()
	t.LeftSimpleRotate()
}

func (t *tree_node) RightDoubleRotate() {
	t.right.LeftSimpleRotate()
	t.RightSimpleRotate()
}

其他方法

计算深度

1
2
3
func (t *tree_node) compute_height() {
	t.height = int(math.Max(float64(t.GetLenght(t.left)), float64(t.GetLenght(t.right)))) + 1
}

获得深度

1
2
3
4
5
6
7
func (t *tree_node) GetLenght(node *tree_node) int {
	if node == nil {
		return -1
	} else {
		return node.height
	}
}

遍历

1
2
3
4
5
6
7
8
9
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 + "  ")
	}
}