二叉排序树（BST）
概念常用操作
查找
查找步骤：查找代码：例如： 插入
插入步骤：插入代码：例如： 删除
删除步骤：删除代码：例如： 构造
构造步骤：构造代码：例如： 查找效率分析优化 二叉排序树（BST） 概念
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树；一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。左 子 树 节 点 值 < 根 节 点 值 < 右 子 树 节 点 值 左子树节点值lt根节点值lt右子树节点值 左子树节点值<根节点值<右子树节点值
进行中序遍历可以得到一个递增的有序序列。
二叉排序树节点定义：
//二叉排序树节点typedef struct BSTNode{ int key; struct BSTNode *leftChild,*rightChild;}BSTNode,*BSTree;
常用操作 查找 查找步骤： 如果树非空，目标值与根节点值比较；如果相等，则查找成功；如果小于根节点值，则在左子树上查找；如果大于根节点值，则在右子树上查找；查找成功返回节点指针，查找失败返回null。 查找代码：非递归方法：最坏空间复杂度为O(1)
//在二叉排序树中查找值为key的节点（非递归实现）BSTNode *search(BSTree tree,int key){ while(tree != NULL && key != tree->key){ //如果树为空或key等于根节点值，结束循环 if(key < tree->key){ //小于，在左子树上查找 tree = tree->leftChild; }else{ //大于，在右子树上查找 tree = tree->rightChild; } } return tree;}
递归方法：最坏空间复杂度为O(h)
//在二叉排序树中查找值为key的节点（递归实现）BSTNode *searchOfRecursion(BSTree tree,int key){ if(tree == NULL){ return NULL; //查找失败 } if(key == tree->key){ return tree; //查找成功 }else if(key < tree->key){ //小于，在左子树上查找 return searchOfRecursion(tree->leftChild,key); }else{ //大于，在右子树上查找 return searchOfRecursion(tree->rightChild,key); }}
例如：查找68
插入 插入步骤： 如果二叉排序树为空，则直接插入节点；如果二叉排序树非空，若插入值小于根节点值，则插入到左子树上；如果二叉排序树非空，若插入值大于根节点值，则插入到右子树上；如果二叉排序树非空，若插入值等于根节点值，则插入值已存在，插入失败。 插入代码：最坏空间复杂度为O(h)。
//在二叉排序树中插入值为key的节点（递归实现）int insert(BSTree *tree, int key) { if (*tree == NULL) { //如果为空，插入新节点 *tree = (BSTree) malloc(sizeof(BSTNode)); (*tree)->key = key; (*tree)->leftChild = (*tree)->rightChild = NULL; return 1; } if ((*tree)->key == key) { //已存在，插入失败 return 0; } else if (key < (*tree)->key) { //插入到左子树中 return insert(&((*tree)->leftChild), key); } else { //插入到右子树中 return insert(&((*tree)->rightChild), key); }}
例如：给定一棵树：
插入26：
删除 删除步骤： 先查找到目标节点；如果节点是叶子节点，直接删除，不影响原树；如果节点只有一棵左子树或右子树，删除节点，将它的左子树或右子树整个移动到删除节点的位置；如果节点既有左子树又有右子树，找到要删除的节点p的直接前驱或者直接后继节点s，用节点s的值替换节点p的值，然后在删除节点s。 删除代码：//删除当前子树的根节点int deleteNode(BSTree *tree) { BSTree q, s; if (!((*tree)->leftChild) && !((*tree)->rightChild)) { //如果左右子树都为空，直接删除 free(*tree); * tree = NULL; } else if (!((*tree)->leftChild)) { //如果左子树都为空 q = *tree; *tree = (*tree)->rightChild; free(q); } else if (!((*tree)->rightChild)) { //如果右子树都为空 q = *tree; *tree = (*tree)->leftChild; free(q); } else { //如果左右子树都为空 q = *tree; //查找节点tree直接前驱 s = (*tree)->leftChild; while (s->rightChild) { q = s; s = s->rightChild; } (*tree)->key = s->key; //替换节点的值 //删除节点s if (q != *tree) { q->rightChild = s->leftChild;//若有，则在删除直接前驱结点的同时，令前驱的左孩子结点改为 q 指向结点的孩子结点 } else { q->leftChild = s->leftChild;//否则，直接将左子树上移即可 } free(s); } return true;}//在二叉排序树中删除值为key的节点（递归实现）int delete(BSTree *tree, int key) { if (!(*tree)) {//数为空时返回失败 return false; } else { //查找要删除的节点 if (key == (*tree)->key) { //对要删除的节点进行删除 deleteNode(tree); return true; } else if (key < (*tree)->key) { //在左子树上查找 return delete(&((*tree)->leftChild), key); } else { //在右子树上查找 return delete(&((*tree)->rightChild), key); } }}
例如：给定一棵树：
删除叶子节点26：
删除只有右子树的节点5：
删除既有左子树又有右子树的节点61（案例使用的是替换直接后继节点68）：
构造 构造步骤： 循环二叉搜索树的插入操作即可。数组元素排列序列不同可导致构建的二叉排序树不同（也可能相同）。
构造代码：//根据数组构造二叉排序树void create(BSTree *tree, int str[], int n) { *tree = NULL; //初始时tree为空 for (int i = 0; i < n; ++i) { //依次插入 insert(tree, str[i]); }}
例如：根据序列[50,66,60,26,21,30,70,68]构造BST:
根据序列[50,26,21,30,66,60,70,68]构造BST:
根据序列[26,21,30,50,60,66,68,70]构造BST:
查找效率分析查找长度：在查找运算中，需要对比节点值的次数称为查找长度，反映了查找操作的时间复杂度。
如果树高为h，找到最下层的叶子节点需要对比h次；
最好情况，n个节点的二叉树最小高度为(log2n)+1,平均查找长度ASL为O(log2n);
最坏情况，每个节点只有一个分支，树高h等于节点数n，平均查找长度ASL为O(n);
平均查找长度ASL(Average Search Length)计算：
下图树的平均查找长度ASL：
A S L = ( 1 × 1 + 2 × 2 + 3 × 4 + 4 × 1 ) ÷ 8 = 2.625 begin{aligned} ASL&=(1times1+2times2+3times4+4times1)div8 \ &=2.625 end{aligned} ASL=(1×1+2×2+3×4+4×1)÷8=2.625
下图树的平均查找长度ASL：
A S L = ( 1 × 1 + 2 × 2 + 3 × 1 + 4 × 1 + 5 × 1 + 6 × 1 + 7 × 1 ) ÷ 8 = 3.75 begin{aligned} ASL&=(1times1+2times2+3times1+4times1+5times1+6times1+7times1)div8 \ &=3.75 end{aligned} ASL=(1×1+2×2+3×1+4×1+5×1+6×1+7×1)÷8=3.75
优化AVL树红黑树
可以使查找树的高度为O(log(n))。