数据结构之二叉排序树

小咪咪 2022-05-30 06:18 218阅读 0赞

上一节我们介绍了二分（折半）查找，也了解了它的优缺点。

二分查找的特点:二分查找能够提高有序表中数据元素的查找速度；二分查找的时间复杂度为**O(log2n)；**二分查找是一种静态查找

二分查找的不足：当查找表经常变化时，二分查找的整体性能急剧下降。

二分查找的硬伤：二分查找基于有序表。

![70][]

当需要插入或者删除数据元素时，为了能够继续进行二分查找，需要大规模挪动有序表中的数据元素，使得插入或者删除后的线性表保持有序。二分查找的过程是一棵二叉树！如下图：

![70 1][]  
这颗二叉树的特性如下：  
1.任意一个结点的值都大于其左子树的所有结点值；

2.任意一个结点的值都小于其右子树的所有结点值。

如何改进二分查找使其适应动态查找？这里就有了一个新的想法，直接组织一棵具有二分查找特性的二叉树。二分查找过程即变换为对树结点的查找过程；由二分查找的特性可知树结点查找的时间复杂度为O(log2n)；只在叶结点处插入新结点即可保持特性不变；删除树结点时也可以容易的保持特性不变。这是一棵特殊的二叉树，怎么给它命名呢？它就是**二叉排序树**。

**二叉排序树的定义**：二叉排序树是一棵空树，或者，若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左右子树也分别是二叉排序树。

二叉排序树是特殊的二叉树，因此具有与二叉树相同的操作。只不过是插入与删除时与普通的二叉树有所不同而已，下面介绍一下二叉排序树的插入与删除操作：

二叉排序树的插入和删除操作

1.插入：其插入操作总是在叶结点处进行；

2.删除；

2.1.叶结点：直接删除；

2.2.非叶结点：查找合适的替代者后删除。

二叉排序树的所有操作都必须保证其二叉排序性不变。

那么，如何为删除操作查找合适的替代者：

1.有一个孩子的结点：用孩子结点代替原结点；

2. 有两个孩子的结点：用中序遍历下的直接前驱替换原结点。

下面介绍一下二叉排序树的插入与删除实现代码：

1.插入

根据上面的描述，我们知道二叉排序树的插入需要递归来实现，所以首先看一下二叉排序树插入的递归函数

// 二叉排序树插入递归函数
    static int recursive_insert(BSTreeNode* root, BSTreeNode* node, BSTree_Compare* compare)
    {
        int ret = 1;
        int r = compare(node->key, root->key);
        // 二叉排序树中含有相同值，非法
        if( r == 0 )
        {
            ret = 0;
        }
        // 插入元素大于根结点
        // 在左子树位置插入
        else if( r < 0 )
        {
        	// 左子树不为空、调用二叉排序树插入递归函数，直至插入至左子树
            if( root->left != NULL )
            {
                ret = recursive_insert(root->left, node, compare);
            }
            // 左子树为空，直接插入
            else
            {
                root->left = node;
            }
        }
        // 插入元素小于根结点
        //  在右子树位置插入
        else if( r > 0 )
        {
        	  // 右子树不为空、调用二叉排序树插入递归函数，直至插入至右子树
            if( root->right != NULL )
            {
                ret = recursive_insert(root->right, node, compare);
            }
            // 右子树为空，直接插入
            else
            {
                root->right = node;
            }
        }
    }

插入代码如下：

// 根据参数插入结点至二叉排序树
    int BSTree_Insert(BSTree* tree, BSTreeNode* node, BSTree_Compare* compare) 
    {
        // 定义二叉排序树结构体变量并强制转换参数
        TBSTree* btree = (TBSTree*)tree;
        // 入口参数合法性检查
        int ret = (btree != NULL) && (node != NULL) && (compare != NULL);    
        // 入口参数合法性ok
        if( ret )
        {
            node->left = NULL;
            node->right = NULL;
            // 插入位置为根结点
            if( btree->root == NULL )
            {
                btree->root = node;
            }
            // 调用二叉排序树递归函数，寻找插入位置
            else
            {
                ret = recursive_insert(btree->root, node, compare);
            }
            // 二叉排序树结点个数加1
            if( ret )
            {
                btree->count++;
            }
        }
        
        return ret;
    }

插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或者右孩子结点。同插入一样，二叉排序树的删除也要通过递归来实现，递归函数如下：

static BSTreeNode* delete_node(BSTreeNode** pRoot)
    {
        BSTreeNode* ret = *pRoot;
        // 有一个孩子的结点,用孩子结点代替原结点
        // 右孩子为空，有一个左孩子的结点,用左孩子结点代替原结点
        if( (*pRoot)->right == NULL )
        {
            *pRoot = (*pRoot)->left;
        }
        // 左孩子为空，有一个右孩子的结点,用右孩子结点代替原结点
        else if( (*pRoot)->left == NULL )
        {
            *pRoot = (*pRoot)->right;
        }
        // 有两个孩子的结点
        else
        {
            BSTreeNode* g = *pRoot;             // 保存要删除结点的地址
            BSTreeNode* c = (*pRoot)->left;     // 保存要删除结点的左孩子结点地址
            // 循环移动要删除结点的左孩子的右孩子，直至到叶结点为止，转左，然后向右到尽头
            // 相当于用中序遍历下的直接前驱
            while( c->right != NULL )
            {
                g = c;
                c = c->right;        // 一直查找右孩子
            }
            // 要删除结点的左孩子有右孩子，用最后右叶子结点
            if( g != *pRoot )
            {
                g->right = c->left;
            }
            // 要删除结点的左孩子没有右孩子，直接用左孩子代替要删除结点
            else
            {
                g->left = c->left;
            }
    				// 将要删除结点的双亲结点的左右孩子结点指向该结点的左右孩子结点
            c->left = (*pRoot)->left;
            c->right = (*pRoot)->right;
       
            *pRoot = c;
        }
        
        return ret;
    }
    
    // 删除二叉排序树结点递归函数
    static BSTreeNode* recursive_delete(BSTreeNode** pRoot, BSKey* key, BSTree_Compare* compare)
    {
        BSTreeNode* ret = NULL;    
        // 参数合法，树存在
        if( (pRoot != NULL) && (*pRoot != NULL) )
        {
        	// 返回关键字与根结点比较结果
            int r = compare(key, (*pRoot)->key);        
            // 找到关键字，调用删除结点函数删除结点
            if( r == 0 )
            {
                ret = delete_node(pRoot);
            }
        	// 获取元素大于根结点
        	// 调用删除二叉排序树结点递归函数，从左子树中开始
            else if( r < 0 )
            {
                ret = recursive_delete(&((*pRoot)->left), key, compare);
            }
        	// 获取元素小于根结点
        	// 调用删除二叉排序树结点递归函数，从右子树中开始
            else if( r > 0 )
            {
                ret = recursive_delete(&((*pRoot)->right), key, compare);
            }
        }
        
        return ret;
    }

删除结点函数如下：

// 删除二叉排序树指定结点
    BSTreeNode* BSTree_Delete(BSTree* tree, BSKey* key, BSTree_Compare* compare)
    {
        // 定义二叉排序树结构体变量并强制转换参数
        TBSTree* btree = (TBSTree*)tree;
        BSTreeNode* ret = NULL;     
        // 入口参数合法性检查ok
        if( (btree != NULL) && (key != NULL) && (compare != NULL) )
        {
        	// 调用删除二叉排序树结点递归函数
            ret = recursive_delete(&btree->root, key, compare);
            // 二叉排序树结点个数减1
            if( ret != NULL )
            {
                btree->count--;
            }
        }
        
        return ret;
    }

由于二叉排序树的其他操作和普通二叉树相同，这里不再赘述，详请参考[二叉树的创建][Link 1]

二叉排序树整体代码：[二叉排序树的C代码实现][C]

[70]: /images/20220530/4a9a7b3a1d874bd687393d0ac71644f9.png
[70 1]: /images/20220530/ffe65219fd6943dca72b2bd6206bcb26.png
[Link 1]: http://blog.csdn.net/u014754841/article/details/79361772
[C]: http://download.csdn.net/download/u014754841/10270638