二叉排序树又称二叉查找树。它要么是一颗空树，要么是具有下列性质的二叉树：
- 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 它的左子树和右子树也分别为二叉排序树。
查找
1
2
3
4
5
6
7
8
9
10
11
12
13
| struct node* search(struct node* root, int key)
{
// 如果root为空或者root的值和待查找的key相同，则返回root
if (root == NULL || root->key == key)
return root;
// 当待查找的关键字大于根结点的值，则递归查找根结点的右子树
if (root->key < key)
return search(root->right, key);
// 当待查找的关键字小于根结点的值，则递归查找根结点的左子树
return search(root->left, key);
}
|
插入元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| struct node* insert(struct node* node, int key)
{
/*如果树为空，则返回一个新的结点，相当于上面例子中10的左子树为空，则将9插入到10的左子树 */
if (node == NULL) return newNode(key);
/*当插入的值key小于当前结点的key，则递归判断左子树*/
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key) /*当插入的值key大于当前结点的key，则递归判断右子树子树*/
node->right = insert(node->right, key);
/* 返回结点指针*/
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| struct node* deleteNode(struct node* root, int key)
{
// 如为空，直接返回
if (root == NULL) return root;
// 如果删除的值小于 root 的值，则递归的遍历rootde左子树
// 即删除结点位于左子树
if (key < root->key)
root->left = deleteNode(root->left, key);
// 如果删除的值大于 root 的值，则递归的遍历root的右子树
// 即删除结点位于右子树
else if (key > root->key)
root->right = deleteNode(root->right, key);
// 如果值相等，则删除结点
else
{
/*第一种情况可以包含在第二种当中，所以不做处理
这里处理第二种情况*/
//删除结点的左孩子为空
if (root->left == NULL)
{
struct node *temp = root->right;
if(root->key == 30){
printf("%dn",temp->key);
}
free(root);
return temp;
}
else if (root->right == NULL)//删除结点的右孩子为空
{
struct node *temp = root->left;
free(root);
return temp;
}
// 左右孩子均不为空，获取删除结点中序遍历的直接后继结点
struct node* temp = minValueNode(root->right);
// 将删除结点的值替换为直接后继结点的值
root->key = temp->key;
// 删除直接后继结点
root->right = deleteNode(root->right, temp->key);
/* 或者获取删除结点中序遍历的直接前驱结点。*/
//struct node* temp = maxValueNode(root->left);
// root->key = temp->key;
//root->left = deleteNode(root->left, temp->key);
}
return root;
}
|
总结
二叉排序树的插入、查找和删除操作的时间复杂度为O(h)，其中 h 是二叉排序树的高度。当原序列有序时，二叉树会退化成单链表，时间复杂度会变为O(n)。
二叉排序树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率最高。要让保持树的高度最小，就要使用到平衡二叉树了。
参考资料
https://mp.weixin.qq.com/s/9-M9V12JBl41PiygZUgJ_w