- BST简介
- 查询BST
- 插入和删除
#1. BST简介
BST(Binary Search Tree)，二叉搜索树是一棵满足如下特点的二叉树：
- 每一个结点的左子树小于结点本身
- 每一个节点的右子树大于结点本身
- 左右子树同时也是二叉搜索树
BST的性质允许我们通过一个简单的递归算法来按序输出二叉树中的所有关键字，这种算法称为中序遍历（inorder tree walk）算法。中序遍历的特点是，子树根的关键字值位于其左子树的关键字值和右子树的关键字值之间。先序遍历（preorder tree walk）中根关键字值位于左右子树关键字值之前，后序遍历(postorder tree walk)输出的根关键字位于左右子树的关键字值之后。
图下为BST:
#2. 查询BST
我们经常需要查找一个存储在BST中的关键字。除了Search操作之外，BST还能支持诸如MINIMUN、MAXIMUM、SUCCESSOR和PREDECESSOR的查询操作。
查找
BST查找过程大致如下：从树根开始查找，并沿着这棵树的一条简单路径向下进行。对于遇到的每个结点x，比较关键字k与x.key。如果两个关键字相等，查找终止。如果k小于x.key，继续查找x的左子树，对称地，如果k大于x.key，继续查找x的右子树。查找的时间复杂度为O(h)，h为树高。
BST查找过程：
BST过程伪代码：
TREE_SEARCH(x,k) {
if(x == NIL or k == x.key)
return x;
if(x < x.key)
return TREE_SEARCH(x.left,k);
return TREE_SEARCH(x.right,k);
}
最大关键字和最小关键字元素
通过从树根开始沿着left孩子指针直到遇到一个NIL，我们总能在BST中找到一个元素。下面的过程返回一个指向在以给定结点x为根的子树中最小元素的指针：
TREE_MINIMUM(x) {
while(x.left != NIL) {
x = x.left;
}
return x;
}
二叉搜索性质保证了TREE_MINIMUM是正确的。
TREE_MAXIMUM的伪代码是对称的，如下：
TREE_MAXIMUM(x) {
while(x.right != NIL) {
x = x.right;
}
return x;
}
后继和前驱
给定一个二叉搜索树中的一个结点，有时候需要按中序遍历的次序查找它的后继。如果所有的关键字互不相同，则一个结点x的后继是大于x.key的最小关键字的结点。
TREE_SUCCESSOR(x) {
if(x.right != NIL)
return TREE_MINIMUM(x.right)
y = x.p
while y != NIL and x == y.right
x = y
y = y.p
return y
}
过程TREE_PREDECESSOR与TREE_SUCCESSOR是对称的。
#3. 插入和删除
插入和删除操作会引起BST表示的动态集合的变化。一定要修改数据结构来反应这个变化，但修改要保持BST性质的成立。
插入
插入的大致过程如下：从树根开始，指针x记录一条向下的简单路径，并查找要替换的输入项Z的NIL。伪代码如下：
TREE_INSERT(T,z) {
y = NIL
x = T.root
while(x != NIL)
y = x
if(z.key < x.key)
x = x.left
else x = x.right
z.p = y
if(y == NIL)
T.root = z
elseif(z.key < y.key)
y.left = z
else y.right = z
}
BST插入图解：
删除
从BST中删除一个结点z的整个策略分为三种基本情况：
- 如果z没有孩子结点，那么只简单地将它删除，并修改它的父结点，用NIL作为孩子来替换z。
- 如果z只有一个孩子，那么将这个孩子提升到树中z的位置上，并修改z的父结点，用z的孩子来替换z。
- 如果z有两个孩子，那么找z的后继y（一定在z的右子树中），并让y占据树中z的位置。z的原来右子树部分成为y的新右子树，并且z的左子树成为y的新左子树。
BST删除图解：
BST C实现：
bstree.h
#pragma once
#ifndef _BSTREE_H_
#define _BSTREE_H_
typedef struct node {
int key;
struct node* left;
struct node* right;
}NODE;
NODE* insert(NODE*, int);
NODE* delete_node(NODE*, int);
NODE* search(NODE*, int);
void inorder_tree_walk(NODE*);
void release(NODE*);
#endif // !_BSTREE_H_
bstree.c
#include "bstree.h"
#include <stdio.h>
#include <stdlib.h>
NODE* new_one(int key) {
NODE* n = (NODE*)malloc(sizeof(NODE));
n->key = key;
n->left = n->right = NULL;
return n;
}
NODE* min_value(NODE* root) {
if (!root) {
return root;
}
NODE* current = root;
while (current && current->left) {
current = current->left;
}
return current;
}
NODE* max_value(NODE* root) {
if (!root) {
return root;
}
NODE* current = root;
while (current && current->right) {
current = current->right;
}
return current;
}
NODE* insert(NODE* root, int key) {
if (!root) {
return new_one(key);
}
if (key < root->key) {
root->left = insert(root->left, key);
}
else {
root->right = insert(root->right, key);
}
return root;
}
NODE* delete_node(NODE* root, int key) {
if (!root) {
return root;
}
if (key < root->key) {
root->left = delete_node(root->left, key);
}
else if (key > root->key) {
root->right = delete_node(root->right, key);
}
else {
// Find target.
// If node has only one child or none.
if (!root->left) {
NODE* tmp = root->right;
free(root);
return tmp;
}
else if (!root->right) {
NODE* tmp = root->left;
free(root);
return tmp;
}
else {
// Target node got two children
NODE* tmp = min_value(root->right);
root->key = tmp->key;
root->right = delete_node(root->right, tmp->key);
}
}
return root;
}
NODE* search(NODE* root, int key) {
if (!root || root->key == key) {
return root;
}
if (key < root->key) {
return search(root->left, key);
}
else {
return search(root->right, key);
}
}
void inorder_tree_walk(NODE* root) {
if (root) {
inorder_tree_walk(root->left);
printf("%d ", root->key);
inorder_tree_walk(root->right);
}
}
void release(NODE* root) {
if (root) {
release(root->left);
release(root->right);
printf("free:%d ", root->key);
free(root);
}
}
参考资料：算法导论
参考资料：https://www.geeksforgeeks.org/binary-search-tree-data-structure/
