Yan`s Notepad

--- My Notepad......Articles, tools and etc.
二叉搜索树
二叉排序树(Binary Sort Tree,BST),或者叫做二叉搜索树(Binary Search Tree,BST),是一种比较有用的数据结构——可以使用它完成排序、搜索任务,并且查找的速度可以做到极快。作为二叉树的一种,它也可以有几种表示法,但是为了方便,我依然采用左右孩子的链式表示:
typedef int    BSTData;
typedef struct _BitSchTree
{
    BSTData         data;
    int             key;
    _BitSchTree    *left;
    _BitSchTree    *right;
}BSTNode, *BST;
// 分配节点
BSTNode *mallocNode()
{
    BSTNode   *r;
    r = (BSTNode*)malloc(sizeof(BSTNode));
    r->left = NULL;
    r->right = NULL;
    return r;
}
在存在子树的情况下,它满足以下的定义:
1. 任意节点的子树也是一颗二叉查找树,且左子树的每个节点均小于该节点,右子树的每个节点均大于该节点。
2. 任意节点的左孩子小于该节点的键值(key),右孩子大于该节点键值。
或许定义比较繁琐,可以自己绘制一些出来:
···图片正在加载···
images/BitTree_BST/tree.png
二叉搜索树
首先,来考虑插入节点的问题。
从上图也看到了,左子节点的键值(如果没有特殊强调,键值和数据是被分开的,并且查找的时候按照键值查找。下面说的节点的值也指的是键值)总是会比它的父节点小,而右子节点的值总是比它的父节点大。并且,整个二叉搜索树没有出现重复的键值——并没有硬性规定它不可以出现重复键值,但是对于查找而言,我们应当自行定义,不允许出现重复的值,不然会可能带来麻烦。下面,我们在下面的BST中插入新的数据:
···图片正在加载···
images/BitTree_BST/insert_1.png
准备插入的树
显然,我们需要从根节点开始,一步步地找到插入的位置。第一步,根节点的值是15,10这个值比15要小,因此应该出现在当前节点的左边:
···图片正在加载···
images/BitTree_BST/insert_2.png
第一步
所以,节点现在被推到左边的蓝色的位置,然后第二步,当前节点的值是8,10这个值比8要大,因而10应该出现在节点8的左边。但是发现这个右节点为空,因此找到插入的位置——当前为空的右节点,进行插入:
···图片正在加载···
images/BitTree_BST/insert_3.png
插入完成
这样,插入就完成了。可以发现,插入过程中会一直寻找到为空的子节点位置,然后把这个空节点替换成插入的值。而找到这个位置的过程,就是一个一直递推的过程:当遇到一个节点时,判断它的键值和需要插入的键值的大小关系,如果新插入的键值大于节点键值,那么就需要前往该节点的右边,反之则是小于的情况应该前往该节点的左边。由于我们定义了作为搜索的树不允许出现相同值的节点,但是作为排序的树则有可能会遇到相同值的节点——因此修改一下,当新插入的键值大于等于节点键值,那么就需要前往该节点的右边,反之,小于的情况应该前往该节点的左边。这个等于符号可以加在左子树的那边也可以加在右子树的那边,并且对二叉搜索树没有影响。这样一来,我们写的插入程序就可以应对排序情景和搜索情景了:
void BSTInsertData(BST *tree, int key, BSTData data)
{
    BST  i, s;
    i = *tree;
    s = *tree;
    while (i != NULL)                                   // 查找插入的位置
    {
        s = i;
        if (i->key < key)                               // 当前的"根节点"的key小于需要插入的key, 那么说明需要插入到这个节点的右边
            i = i->right;
#if _BST_SORT_                                          // 对于排序用的树, 可以出现相同键值的节点, 对于搜索用的则不然
        else if (i->key >= key)
            i = i->left;
#else
        else if (i->key > key)
            i = i->left;
        else
            return;                                     // 不允许出现键值一样的节点
#endif
    }
    i = mallocNode();                                   // 分配新节点, 并载入数据
    i->key = key;
    i->data = data;
    i->left = NULL;
    i->right = NULL;
    if (s == NULL)                                      // 空的,放在根节点
        *tree = i;
    else if (s->key < key)                              // 当前key大于节点的key, 在它的右孩子的位置插入
        s->right = i;
    else
        s->left = i;
}
然后,再来考虑在一个二叉搜索树中进行查找某一个节点。
按照类似的思路,查找节点也有类似的流程。比如在下面的树中查找节点“10”,依然从根节点开始:
···图片正在加载···
images/BitTree_BST/search_1.png
需要查找的树
类似地,由于查找的值是10,小于当前的节点的值15,因此需要往左边走:
···图片正在加载···
images/BitTree_BST/search_2.png
第二步
然后,当前节点的值是9,需要查找的是10,大于9,因此往右边走:
···图片正在加载···
images/BitTree_BST/search_3.png
查找完成
这样一来,就寻找完成了。总结一下规律:如果当前节点的值不等于需要查找的值,那么就进行比较:查找值大于当前值,就往右走;查找值小于当前值,就往左走。这样,就可以实现查找算法:
void BSTSearchData(BST bst, int key, BSTData **data)
{
    BST  i;
    i = bst;
    while (i != NULL)
    {
        if (key == i->key)                              // 查找到了, 返回
        {
            *data = &(i->data);                         // 输出当前数据位置的地址
            return;
        }
        if (key > i->key)                               // 大于根节点的键值, 在这个节点的右边去找
            i = i->right;
        else                                            // 不然去左边寻找
            i = i->left;
    }
    *data = NULL;                                       // 没有找到
}
再接着,已经完成了插入、查找两个内容,那么自然地,我们还需要考虑删除操作。在之前的基础上,我们可以找到任意一个键值的节点位置。接下来所需要做的就是删掉该节点。对于简单的在末端的、或者在某一个单一的分支上的节点,可以直接删去
···图片正在加载···
images/BitTree_BST/delete_1.png
可以直接删掉的节点
但针对于中间的节点,则没有那么简单。因为BST的每一个节点的值是有关系的,如果直接删掉这个节点,就会破坏掉这个关系,况且删除之后会变成三颗树,如何合并也是一个难事。比如下面的情况:
···图片正在加载···
images/BitTree_BST/delete_2.png
需要复杂操作的
针对于这种情况,需要了解对一个二叉搜索树进行中序遍历,可以得到一串已经排序好了的值。那么换句话说,为了保证删除前后的中序遍历的结果不变——即保证该BST的正确,可以直接在这个中序遍历结果中进行操作:7 15 16 20 23 25 37 40 49,删去20,得到:7 15 16 23 25 37 40 49。这样一来,就完成了删除操作。
但是,每一次都去生成这个序列,然后再按照删除完毕后的序列来构建新的BST,无疑是很耗时间的。如果我们能知道某一个节点在中序遍历后的位置,并且知道该结果的下一个值对应的节点,就好办了。现在,引入后继节点:树进行中序遍历后,得到的结果中,某个节点A的对应的元素的下一个元素所对应的节点,被叫做节点A的后继节点。比如,在上面的树中,16的后继节点是20;25的后继节点是37等。后继节点存在两种情况,一种是当前的子树存在右子树,那么当前节点的后继节点一定在它的右子树上,即为右子树的最左边。比如图上的节点25,存在右子树:根节点为40。对于根节点为40的这个子树,它的最左边就是节点37。而第二种情况,也就是不存在右子树,那就依次往上找直到这个节点的父节点是某个节点的左孩子,那么这个父节点就是当前节点的后继节点。在BST中,不难发现没有左或者右子树的节点可以直接被删掉,并且不会造成影响。这样说来,我们只需要考虑第一种情况。那么,就可以得到如下的程序了:
void BSTDeleteData(BST *bst, int key)
{
    BST  i, root, father;
    i = *bst;
    root = i;
    father = NULL;
    while (i != NULL)
    {
        if (key == i->key)                              // 查找到了, 进行删除
        {
            if (i->left == NULL && i->right == NULL)
            {                                           // 叶子节点, 直接删除
                if (father != NULL)
                    if (i == father->left)
                        father->left = NULL;
                    else
                        father->right = NULL;
                if (i == root)                          // 删掉的是根节点
                    *bst = NULL;
                free(i);
            }
            else if (i->left == NULL)                   // 右子树不为空, 也可以直接删除
            {
                if (father != NULL)
                    if (i == father->left)              // 把i下面的子树连接上
                        father->left = i->right;
                    else
                        father->right = i->right;
                if (i == root)
                    *bst = i->right;                    // 把根节点设置为右子节点, 因为根节点被删掉, 并且只有右孩子
                free(i);
            }
            else if (i->right == NULL)                  // 左子树不为空, 也可以直接删除
            {
                if (father != NULL)
                    if (i == father->left)              // 把i下面的子树连接上
                        father->left = i->left;
                    else
                        father->right = i->left;
                if (i == root)                          // 把根节点设置为左子节点, 因为根节点被删掉, 并且只有左孩子
                    *bst = i->left;
                free(i);
            }
            else {                                      // 拥有左右子树的节点
                BST   t, s;
                t = i;
                s = i->right;
                while (s->left != NULL)                 // 查找后继节点
                {
                    t = s;
                    s = s->left;
                }
                i->key = s->key;                        // 直接替换节点的值
                i->data = s->data;
                if (t == i)                             // 当前的后继节点的父节点就是需要删除的, 直接把子树接上
                    i->right = s->right;                // 根节点也可能是此情况, 因此无需处理root
                else
                    t->left = s->right;                 // 不然把后继节点的右子树接到它的父节点的左边去
                free(s);
            }
            return;
        }
        father = i;                                     // 记录父节点
        if (key > i->key)                               // 大于根节点的键值, 在这个节点的右边去找
            i = i->right;
        else                                            // 不然去左边寻找
            i = i->left;
    }                                                   // 没有找到, 那么就不管了(TODO: 错误处理)
}
最后,是二叉排序树的使用。在之前提到的二叉搜索树中,我们更改为允许插入相同的键值。那么这样就可以进行排序——对该二叉树进行中序遍历,即可得到排序后的键值。代码实现如下:
void sortOutput(BST tree)
{
    if (!tree)
        return;
    sortOutput(tree->left);
    printf("%d ", tree->key);
    sortOutput(tree->right);
}
关于BST最基本的插入和查找操作就这样完成了。不过,目前所提到的二叉查找树其实是一个略有不稳定的东西。尝试输入一个从小到大的键值来构造一个BST,结果是会变成链表那样——它的优点也就全部消失了。为了解决这个问题,出现了平衡二叉树、红黑树,它们可以保证BST几乎处于最佳的状态,从而提高效率。事实上,文中涉及到的图片都是平衡二叉树,不然怎么会看起那么的巧合呢?