[算法笔记]树表的查找：BST与AVL_bst旋转

树表得从线性表说起：

线性表查找方法有三种，折半查找是其中效率最高的。但是其数据之间的有序性意味着无法进行频繁的插入删除，这适合静态查找表。

对于动态查找表进行高效查找，可以用树表。

二叉排序树

二叉排序树(BST, Binary Search Tree)又称为二叉搜索树

其实跟普通的二叉树差不多，但是

1. 若根节点的左子树非空，则左子树上所有结点关键字均小于根节点关键字
2. 若根节点的右子树非空，则右子树上所有结点关键字均大于根节点关键字
3. 根节点的左、右子树本身又各是一棵二叉排序树

显然较之于普通的二叉树有了值上的约束.

对于关键字重复的情况可以将上述规则1改为小于等于或者规则2改为大于等于。

存储结构也是常规二叉树的数据域＋左右指针域

typedef struct node{
    int key;
    struct node *lchild, *rchild;
}BSTNode, *BSTree;
1
2
3
4

中序遍历得到的结果是有序的

二叉排序树的操作

创建

创建操作是对插入操作的反复调用

插入

整个过程是递归的。

不难发现二叉搜索树的创建就是对插入函数的反复调用。

亦不难发现对于一组关键字，序列不同其树形态也可能不同。

在诸多不同的二叉树序列中，高度越小查找效率越高。如何构建合理的二叉树是要详细学习的

查找

删除

如果是整棵树的删除是和传统二叉树一样的。但是如果是单个节点的删除，应当注意：删除某个结点后所得的二叉树应当仍满足二叉搜索树的性质。

1. 被删除节点要确定是否在树中
2. 删除这个节点不意味着其子树都删去（因此需要考虑子树怎么接到剩下的二叉搜索树上）
3. 被删除节点是叶子结点则不那么费劲（直接删去就行）

删除策略依然是遵守BST的性质的，因此

若删除的节点是叶子结点：直接删

若删除的节点只有左子树或右子树：直接让这个子树接替被删除节点的位置即可

若删除的节点两个子树均存在：从左子树中挑选最大的或从右子树中挑选最小的结点替代被删除的结点。换句话说就是使用中序遍历中被删结点的前驱或者后继替代它。

---

但是在删除的节点两个子树均存在的情况下，使用中序遍历前驱或者后继的节点代替时，该节点的子树该如何处理？

看上图左右两种情况，也就是前驱结点是否有左子树（肯定没有右子树啊，这是性质）。

如果有左子树（图左）：前驱替换到待删节点，前驱的父节点指向前驱的左子树。

如果没有左子树（图右，待删前驱是叶子结点）：前驱替换到待删节点就完事了。

---

总结一下

这是使用待删前驱替代待删节点的方法，也可以使用待删后继代替待删节点。思路是类似的，但是常用的是前者。

因此上表可以细化为

代码

代码及测试用例（主函数）如下

#include <iostream>
#include <stdlib.h>
using namespace std;
#define KeyType int

typedef struct node{//二叉排序树的存储结构
    KeyType key;//关键字的值
    struct node *lchild, *rchild;
}BSTNode;

bool InsertBST(BSTNode *&bt, KeyType k){
	// 二叉树的插入 
	if(bt == NULL){
		// 若树空则创建节点
		bt = (BSTNode *)malloc(sizeof(BSTNode));
		bt->key = k;
		bt->lchild = bt->rchild = NULL;
		return true;
	}
	else if(k == bt->key){
		// 若有相同的则不处理且返回假 
		return false;
	}
	else if(k < bt->key){
		InsertBST(bt->lchild, k);
	}
	else if(k > bt->key){
		InsertBST(bt->rchild, k);
	}
} 

BSTNode * CreateBST(KeyType a[], int n){
	// 二叉树的创建，a[]是数据源，n是数据个数
	 BSTNode* bt = NULL;
	 int i = 0;
	 while(i < n){
	 	InsertBST(bt, a[i]);
	 	i++;
	 } 
	 return bt;
}
BSTNode* SearchBST(BSTNode* bt, KeyType k){
	// 查找成功返回指向该节点的指针 
	if(bt == NULL || bt->key == k){
		return bt;
	}
	else if(k < bt->key){
		SearchBST(bt->lchild, k);
	}
	else{
		SearchBST(bt->rchild, k);
	}
}

void InOrederOutput(BSTNode* bt){
	if(bt == NULL){
		return;
	}
	InOrederOutput(bt->lchild);
	cout<<bt->key<<" ";
	InOrederOutput(bt->rchild);
}

bool DeleteBST(BSTNode*& bt, KeyType k){
	/*
	总体思路是两个指针找到目标节点target及其父节点temp
	而且任何删除节点的操作都需要父节点将孩子设为NULL 
	if判断情况进行对应的操作处理。 
	*/
	BSTNode* temp, *target = bt;
	while(target != NULL){
		if(target->key == k){
			break;
		}
		temp = target;
		if(target->key < k){
			target = target->rchild;
		}
		else{
			target = target->lchild;
		}
	}
	if(target == NULL){
		//没找到或者传入的是空树 
		return false;
	}
	if(target->rchild == NULL){
		//左子树为空
		if(temp == NULL){
			//待删节点为根
			bt = target->rchild; 
		} 
		else if(temp->lchild == target){
			//待删节点是父节点的左孩子
			temp->lchild = target->rchild; 
		}
		else{
			temp->rchild = target->lchild;
		}
		free(target);
	}
	else{
		//左子树不为空
		BSTNode* maxInLeft, *parentBeforeMax = target; 
		maxInLeft = target->lchild;
		while(maxInLeft->rchild != NULL){
			//找到中序遍历下待删节点的前驱
			//即左子树最右下的那个 
			parentBeforeMax = maxInLeft;
			maxInLeft = maxInLeft->rchild;
		}
		if(target == parentBeforeMax){
			//待删节点左孩子没有右子树，本身就是最大的情况
			 parentBeforeMax->lchild = maxInLeft->lchild;
		}
		else{
			parentBeforeMax->rchild = maxInLeft->lchild;
		}
		parentBeforeMax->key = maxInLeft->key;
		free(maxInLeft);
	}
	return true;
}

int main()
{
	int a[10] = {2,4,1,6,3,5,9,7,8,10};
	BSTNode * st = CreateBST(a,10);
	InOrederOutput(st);
	InsertBST(st, 17);
	InsertBST(st, -2);
	cout<<endl;
	InOrederOutput(st);
	cout<<endl;
	BSTNode* temp = SearchBST(st, 7);
	if(temp != NULL){
		cout<<temp->key<<endl;
	}
	else{
		cout<<"Search Error"<<endl;
	}
	temp = SearchBST(st, 11);
	if(temp != NULL){
		cout<<temp->key<<endl;
	}
	else{
		cout<<"Search Error"<<endl;
	}
	DeleteBST(st, 5);
	InOrederOutput(st);
	cout<<endl;
	DeleteBST(st, -1);
	InOrederOutput(st);
    return 0;
}
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

平衡二叉树

平衡的二叉排序树有很多种，较为著名的是AVL树

AVL树具有的特点：

• 所有二叉排序树的特点
• 平衡二叉树的特点

平衡二叉树：每个节点左右子树高度最多相差1

（一个节点的）平衡因子（缩写BF）：该节点一个子树减去另一个子树的高度（一般是左减右）

节点的平衡因子取值为1、0、-1时该节点是平衡的，否则是不平衡的。当且仅当所有结点都是平衡的，整棵树是平衡二叉树。

上面说过，对于一组关键字，序列不同其树形态也可能不同。在诸多不同的二叉树序列中，高度越小查找效率越高。平衡二叉树就是解决这个问题的。

插入过程

空树也符合平衡二叉树的性质，这意味着跟二叉搜索树一样，完成了插入操作，就相当于基本上完成了创建操作。或者说创建操作就是对于空树的插入操作。

插入操作的操作对象是一个平衡二叉树，插入新节点（总是作为叶子结点插入）后会破坏平衡性。因此整个插入过程是：插入->失衡->再调整至平衡

调整策略涉及到一个概念叫失衡的最小子树

失衡的最小子树：离插入节点最近且平衡因子绝对值大于1的节点作为根的子树

由于插入是一般是叶子结点，因此要向根方向上溯寻找平衡因子绝对值大于1的节点，这个节点出现的位置只有四种情况，也就是LL，RR，LR和RL四种。

L是英文left首字母，R是right。那LL就是离插入节点最近且平衡因子绝对值大于1的节点左子树的左子树下插入数据的情况。

类似地LR就是离插入节点最近且平衡因子绝对值大于1的节点左子树的右左子树下插入数据的情况

局部平衡是整体平衡的前提

再理解四种情况的名字后就可以看处理操作了。处理操作的根本逻辑是把失衡的最小子树通过旋转等操作调整为平衡的。

而这四种操作，均由左旋和右旋两种基本操作组成

---

上图是两种基础旋转操作（图自邓俊辉数据结构）

不论怎样的过程，最后根节点的平衡因子都是0

单向右旋平衡处理LL

LL型的调整策略是以B为轴，对A做一次顺时针旋转

长方框表示子树

单向左旋平衡处理RR

RR型是以B为轴，对A做一次逆时针旋转

双向旋转（先左后右）平衡处理LR

双向旋转（先右后左）平衡处理RL

RL型是对B做一次顺时针旋转，对A做一次逆时针旋转

四种方法的总结

假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a（即a是离插入点最近，且平衡因子绝对值超过1的祖先结点），则失去平衡后进行进行的规律可归纳为下列四种情况：

• 单向右旋平衡处理LL：由于在*a的左子树根结点的左子树上插入结点，a的平衡因子由1增至2，致使以a为根的子树失去平衡，则需进行一次右旋转操作；
• 单向左旋平衡处理RR：由于在*a的右子树根结点的右子树上插入结点，a的平衡因子由-1变为-2，致使以a为根的子树失去平衡，则需进行一次左旋转操作；
• 双向旋转（先左后右）平衡处理LR：由于在*a的左子树根结点的右子树上插入结点，a的平衡因子由1增至2，致使以a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。
• 双向旋转（先右后左）平衡处理RL：由于在*a的右子树根结点的左子树上插入结点，a的平衡因子由-1变为-2，致使以a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。

---

旋转过程耗费恒定的时间，平衡总是于插入节点处开始自底向上向根节点折回，将插入期间成为不平衡的所有节点上进行旋转。这一路上最多有$O(logn)$个节点，故时间复杂度属于常量*logn依旧是$O(logn)$。

删除过程

从AVL树中删除可以通过把要删除的节点向下旋转成一个叶子节点，接着直接剪除这个叶子节点来完成。

也可以直接像BST一样删去，然后再调整。

查找过程

与二叉树无异

最坏情况下二叉树查找情况是$O(n)$，但是AVL是$O(logn)$，这是因为对于n个数据的AVL树最多只有$O(logn)$层

参考

百度百科
邓俊辉《数据结构》
李春葆《数据结构教程》