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 + " ") } }
|