二叉排序树

二叉排序树(Binary Sort Tree，BST)又称二叉查找，是一种特殊的二叉树，二叉排序树或者是空树，或者是满足如下性质的二叉树：
①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
③左、右子树本身又各是一棵二叉排序树。

二叉排序树的重要性质

中根遍历一棵二叉排序树所得的结点访问序列是按键值的递增序列。

数据结构定义

typedef struct node
{
    KeyType key; //关键字
    DataType other; //其他数据域
    struct node *lchild, *rchild; //左右子树指针
} BsTNode; //结点类型
typedef BsTNode *BsTree; //二叉排序树类型

插入操作

算法思想

① 若二叉排序树T为空，则为待插入的关键字key申请一个新结点，并令其为根；
② 若二叉排序树T不为空，则将key和根的关键字比较：
若二者相等，则说明树中已有此关键字key，无须插入。
若key<T→key，则将key插入根的左子树中。
若key>T→key，则将它插入根的右子树中。
子树中的插入过程与上述的树中插入过程相同。如此进行下去，直到将key作为一个新的结点的关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。

算法实现

BSTree InsertBST(BSTree T, BSTNode *S)
{
    BSTNode *f, *p = T;
    while (p) { //找插入位置
        f = p; // f记录p的双亲,为将来插入结点
        if (S->key < p->key) p = p->lchild;
        else p = p->rchild;
    }
    if (T == NULL) T = S; //T为空树,新结点作为根结点
    else if (S->key < f->key)
        f->lchild = S; //作为双亲的左孩子插入
    else f->rchild = S; //作为双亲的右孩子插入
    return T;
}

二叉排序树生成

从空的二叉树开始，每输入一个结点数据，生成一个新结点，就调用一次插入算法将它插入到当前生成的二又排序树中

实现

BSTree CreateBST(void)
{
    //从空树开始,建立一棵二叉排序树
    BSTree T = NULL; //初始化T为空树
    KeyType key;
    BSTNode *S;
    scanf("％d", &key); //输入第一个关键字
    while (key) { //假设key=0是输入结束
        S = (BSTNode *)malloc(Sizeof(BSTNode));
        S->key = key; //生成新结点
        S->lchild = S->rchiId = NULL;//成为叶结点
        T = InsertBST(T, S); //将新结点*S插入二叉排序树T
        scanf("％d", &key); //输入下一个关键字
    }
    return T; //返回建立的二叉排序树
}

二叉排序树查找

基本思想

若二叉排序树为空，则表明查找失败，应返回空指针。否则，若给定值key等于根结点的关键字，则表明查找成功，返回当前根结点指针；若给定值key小于根结点的关键字，则继续在根结点的左子树中查找，若给定值key大于根结点的关键字，则继续在根结点的右子树中查找。显然，这是一个递归的查找过程，

算法实现

BSTNode *SearchBST(BSTree T, KeyType x)
{
    //在二叉排序树上查找关键字值为x的结点
    if (T == NULL || T->key == x)
        return T;
    if (x < T->key)
        return SearchBST(T->lchild, x);
    else
        return SearchBST(T->rchild, x);
}

算法分析

若二叉排序树是一棵理想的平衡树（是指树中任一结点的左右子树的高度差不能大于1），则进行查找的时间复杂度为O(log2n)；

二叉树删除

从BST树上删除一个结点，仍然要保证删除后满足BST的性质。
在这里插入图片描述

（1）若p是叶子结点：直接删除p，如b图
（2）若p只有一棵子树（左子树或右子树），直接用p的左子树（或右子树）取代p的位置而成为f的一棵子树。即原来p是f的左子树，则p的子树成为f的左子树；原来p是f的右子树，则p的子树成为f的右子树，如图（c）所示。
（3）若p既有左子树又有右子树，处理方法有以下两种，可以任选其中一种。

①用p的直接前驱结点（中序遍历）代替p，即从p的左子树中选择值最大的结点s放在p的位置（用结点s的内容替换结点p内容），然后删除结点s。s是p的左子树中最右边的结点且没有右子树，如图（d）所示。
②用p的直接后继结点（中序遍历）代替p，即从p的右子树中选择值最小的结点s放在p的位置（用结点s的内容替换结点p的内容），然后删除结点s。s是p的右子树中的最左边的结点且没有左子树。例如，对图（a）所示的二叉排序树，删除结点8后所得的结果如图（e）所示。

b树

二叉树不适于大量文件存储的情形。所以出来一个b树

一棵m（m≥3）阶的B树，或为空树，或为满足下列性质的m叉树：
如下图所示：在这里插入图片描述

①每个结点至少包含下列信息域：
（n，p0，k1，p1，k2，…，kn，pn）
其中，n为关键字的个数；
ki（1≤i≤n）为关键字，且ki < ki+1（1≤i≤n-1）；
pi（0≤i≤n）为指向子树根结点的指针，且pi所指向子树中所有结点的关键字均小于ki+1，pn所指子树中所有结点关键字均大于kn。
②树中每个结点至多有m棵子树。
③若树为非空，则根结点至少有1个关键字，至多有m-1个关键字。因此，若根结点不是叶子，则它至少有两棵子树。
④所有的叶结点都在同一层上，并且不带信息
⑤每个非根结点中所包含的关键字个数满足： m/2上取整 -1≤n≤m-1。因为每个内部结点的度数正好是关键字总数加1，所以，除根结点之外的所有非终端结点（非叶子结点的最下层的结点称为终端结点）至少有 m/2上取整棵子树，至多有m棵子树。

数据结构定义

#define m 10 //m为B树的阶,结点中关键字最多可有m-1个

typedef struct node {
    int keynum; //结点中关键字个数,即结点的大小
    KeyType key[m]; //关键字向量,key[0]不用
    struct *parent; //指向双亲结点
    struct node *ptr[m]; //子树指针向量
} BTNode;
typedef BTNode *BTree;

b树插入

先在最低层的某个非终端结点中添加一个关键字。若该结点中关键字的个数不超过m-1，则插入完成，否则要产生结点"分裂"。"分裂"结点时把结点分成两个，将中间的一个关键字拿出来插入到该结点的双亲结点上，如果双亲结点中已有m-1个关键字，则插入后将引起双亲结点的分裂，这一过程可能波及B树的根结点，引起根结点的分裂，从而使B树长高一层。

实例

将关键字序列：24，45，53，90，3，50，30，6l，12，70，100依次插入一棵初始为空的4阶B树中的过程。
如下图所示：
在这里插入图片描述

b树删除

（1）若需删除关键字所在结点中的关键字数目不小于，则只需要该结点中关键字和相应的指针删除。
（2）若需删除关键字所在结点中的关键字数目等于－1，即关键字数目已是最小值，直接删除该关键字会破坏B树的性质。删除这样关键字分两种情况处理：
① 若所删结点的左(或右)邻兄弟结点中的关键字数目不小于，则将其兄弟结点中的最大(或最小)的关键字上移至双亲结点中，而将双亲结点中相应的关键字移至删除关键字所在结点中。
② 若需删除关键字所在结点及其相邻的左、右兄弟(或只有一个兄弟)结点中关键字数目均等于 m/2上取整－1，则按上述情况①的移动操作就不能实现。此时，就需要将被删结点与其左兄弟或右兄弟结点进行"合并"。

b树查找

若B树为非空，则首先取出树根结点，将给定值K依次与关键字向量中从高下标端（key[keynum]）开始的每个关键字进行比较，直到K≥Ki（0≤i≤n=keynum，用key[0]作为中止标志，存放给定的查找值K）为止，此时，若K= Ki且i>0，则表明查找成功，返回具有该关键字的结点的存储位置及K在key[1…keynum]中的位置；否则，其值为K的关键字只可能落在当前结点的pi所指向的子树上，接着只要在该子树上继续进行查找即可。这样，每取出一个结点比较后就下移一层，直到查找成功，或被查找的子树为空(即查找失败)为止。

算法实现

BTNode *SearchBTree(BTree T, KeyType K, int *pos)
{
    //从树根指针为T的B树上查找关键字为K的对应结点的存储地址及K在其中的
//位置*pos,查找失败返回NULL,*pos无定义
    int i;
    BTNode *p = T;
    while (p != NULL) { //从根结点开始起依次向下一层查找
        i = p->keynum; //把结点中关键字个数赋给i
        p->key[0] = K; //设置哨兵,顺序查找key[0…keynum]
        while (K < p-> key[i]) //从后向前查找第1个小于等于K的关键字
            i--;
        if (K == key[i] && i > 0) {
            *pos = i;
            return p;
        } else
            p = p->ptr[i];
    }
    return NULL;
}

B+树

B+树是一种常用于文件组织的B树的变形树。一棵m阶的B+树和m阶的B树的差异在于：
（1）有k个孩子的结点必含有k个关键字。
（2）所有的叶结点中包含了关键字的信息及指向相应结点的指针，且叶子结点本身依照关键字的大小从小到大顺序链接。
（3）所有非终端结点可看成是索引部分，结点中仅含有其子树（根结点）中的最大关键字（或最小）关键字。
对B+树进行两种查找运算：一种是从最小关键字起进行顺序查找，另一种是从根结点开始进行随机查找。