查看原文
其他

什么是二叉查找树?

守望先生 编程珠玑 2019-04-24

树简介

对于树的基本认识,我们很容易通过我们平常所见到的树来理解:一棵树,有一个根,根往上又会分叉出大树枝,大树枝又会分叉出小树枝,以此往复,直到最后是叶子。而作为数据结构的树也是类似的,只不过我们通常将它倒着画。树的应用也相当广泛,例如在文件系统,数据库索引中的应用等。本文会对树的基本概念做介绍,但重点介绍二叉查找树。

现实中的树

树的定义

树是一种无向图,其中任意两个节点间存在唯一一条路径。树常常用一种递归的方式来定义,它是一种数据结构,要么为空,要么具有一个值并且有零个或多个孩子,而每个孩子又是树。

例如下图一棵树,任意两个节点间只有一条路径可到达:


图一:树


但下图并非树:

非树

图二:非树


因为从节点root到节点b并非只有一条路径。

树的种类

我们可能已经听过很多树的名词,例如,红黑树,霍夫曼树,B树,B+树,平衡二叉树等等,而本文将要介绍二叉查找树,很多其他树都是它的变种,不像链表的线性访问,二叉查找树的大部分操作时间复杂度都为O(logN)。

常见名词解释

在学习二叉查找树之前,必须要先了解一些名词,我们借助下面的图来了解,如果已经清楚了可以跳过此节。

介绍树的基本名词:

  • 根节点:root节点没有父节点,我们把它称为根节点

  • 父节点:如b节点的父节点为root节点

  • 子节点:在图三中,root有三个孩子,分别是b,c,d,它们都是root的子节点

  • 兄弟节点:b有两个兄弟节点,c,d,因为它们有相同的父节点root

  • 叶子节点:e f等节点,它们没有子节点,因此是叶子节点。

  • 树的深度:树的深度等于它的最深的树叶的深度,而树叶的深度为从根到本叶子节点的路径长(边数)。根节点的深度为0,例如,图三树的深度root->b->e(也可选其他树叶的深度)为2。

  • 树的层:树的深度+1,根节点的层为1。

  • 二叉树:如图四,每个节点最多两个子节点


图三:树


二叉树

图四:二叉树


二叉查找树

二叉树是一种树的特殊形式,它的每个节点最多两个孩子节点,分别为左孩子和右孩子。而二叉查找树在此基础上,还有一个特点,就是每个节点比它左子树的节点值都要大,而比右子树的节点值都要小

二叉查找树操作

二叉查找树常见操作有插入,查找,删除以及遍历。而实际上二叉查找树既可以使用数组来实现,也可以使用链表,本文采用链表来实现。另外本文也排除了两个节点存在相同值的情况。

节点定义

我们使用一个结构体来定义它:

typedef struct Tree_Node
{

    ElementType value;   //节点值
    struct Tree_Node *left; //左节点
    struct Tree_Node *right; //右节点
}TreeNode;

二叉查找树的插入

我们以数据 10,5,19,4,8,13,24为例,来看看二叉查找树的插入流程是怎样的。

  • 插入节点值10,由于原先无节点,因此10作为根节点

  • 插入节点值5,与根节点比较,比根节点小,因此将插入到左子树,而19比根节点大,将插入右子树。

    二叉查找树插入


    图五:二叉查找树插入1


  • 节点值4,与根节点10比较,比根节点小,因此将插入到左子树,继续与5比较,比5小,将插入左子树;节点8,与根节点10比较,比根节点小,因此插入到左子树,与5比较,比5大,因此插入到右子树。

    二叉查找树插入


    图六:二叉查找树插入2


  • 节点值13,与根节点比较,比根节点大,因此将插入到右子树,继续与19比较,比19小,因此插入到左子树;节点值24,与根节点比较,比根节点大,因此将插入到右子树,与19比较,比19大,因此插入到右子树。

      

    二叉查找树插入


    图七:二叉查找树插入3


最终完成了所有元素的插入。而观察插入后的二叉树可以发现,每个节点都要比左子树的值大,而比右子树的值小。另外,我们在插入的时候不断地与节点值比较,比它大,则将插入右子树,而比它小,则将插入左子树,因此这个过程非常容易用递归来实现。

/*将value插入到树中*/
TreeNode *insertTree(ElementType value,TreeNode *tree)
{
    if(NULL == tree)
    {
        /*创建一个节点*/
        tree = malloc(sizeof(TreeNode));
        if(NULL == tree)
        {
            printf("malloc failed\n"); 
            return NULL;
        }
        else
        {
            /*将节点信息存储在此叶子节点中*/
            printf("insert %d to tree\n",value);
            tree->value = value;
            tree->left = NULL;
            tree->right = NULL;

        }
    }
    /*比当前节点小,则插入到左子树*/
    else if(value < tree->value)
    {
        tree->left = insertTree(value,tree->left);
    }
    /*比当前节点大,则插入到右子树*/
    else if(value > tree->value)
    {   
        tree->right = insertTree(value,tree->right);
    }
    return tree;
}

二叉查找树的查找

实际上,我们在做插入操作的时候,已经在做查找动作了,因为为了将一个元素插入到正确的位置,我们需要从根节点开始,不断比较其值和要插入(查找)的值的大小,如果比该节点值小,则说明该值需要插入到左子树,否则插入到右子树,并且递归调用,最终找到插入的位置。

查找的思路有点像二分查找,我们知道根节点左子树的值都比根节点值小,而右子树的值都比根节点的值要大,以此递归调用,可以很容易找到:

/*查找值为value的节点*/
TreeNode *findTree(ElementType value,TreeNode *tree)
{
    if(NULL == tree)
    {
        /*最后一层还没有找到*/
        return NULL;
    }
    /*从左子树查找*/
    if(value < tree->value)
    {
        return findTree(value,tree->left);
    }
    /*从右边子树查找*/
    else if(value > tree->value)
    {
        return findTree(value,tree->right);
    }
        /*找到*/
    else
        return tree;

}

二叉查找树的删除

相对来说,删除要比插入和查找复杂很多。因为它需要考虑很多情况:

  • 删除的节点为叶子节点,直接删除

  • 删除的节点有一个子节点,可以将该子节点作为其父节点的子节点

  • 删除的节点有两个子节点,我们可以采取这样的策略:用右子树最小值代替该节点,并递归删除那个节点值。需要递归删除是因为这个最小值的节点可能还有右子树,因此需要做同样的删除操作(它不会有左子树,因为它自己的值最小)。

第一种情况很容易理解,我们来看第二种和第三种情况。

先看第三种情况,假如我们要从前面的二叉树中删除节点值为10的节点。首先我们可以找到节点值为10的节点的右子树的最小值,为13,因此,将13代替节点值为10的节点值,而幸运的是,节点值为13的节点没有右子树,因此释放根节点的内存,完成删除操作。删除前后如图所示:

二叉查找树删除


图八:二叉查找树删除1


再看第二种情况,假如此时要删除值为19的节点,从图中可知,它有一个右儿子,因此删除该节点后,需要将其父节点指向它的右儿子,删除后如下图:

 

二叉查找树删除2


图九:二叉查找树删除2


总体来说,删除操作并不是一次简单的查找就可以完成,甚至删除会使得整个二叉树变得非常不平衡,所以如果删除次数不多,完全可以采用懒惰删除,即当节点被删除时,仅做一个标记,表明它被删除了,而不是真的从树中移除,这样虽然表面上浪费了一点空间,但是如果后面又要插入该元素值,则为新元素分配内存的开销就免了。

根据上面的分析,代码如下:

TreeNode *deleteTree(ElementType value,TreeNode *tree)
{
    TreeNode *tempNode = NULL;;
    if(NULL == tree)
    {
        printf("not fount \n");
        return NULL;
    }
    /*比当前节点值小,从左子树查找并删除*/
    else if(value < tree->value)
    {
        tree->left = deleteTree(value,tree->left);
    }
    /*比当前节点值大,从右子树查找并删除*/
    else if(value > tree->value)
    {
        tree->right = deleteTree(value,tree->right);
    }
    /*等于当前节点值,并且当前节点有左右子树*/
    else if(NULL != tree->left  && NULL != tree->right)
    {
        /*用右子树的最小值代替该节点,并且递归删除该最小值节点*/
        tempNode = findMin(tree->right);
        tree->value = tempNode->value;
        tree->right = deleteTree(tree->value,tree->right);
    }
    /*要删除的节点只有一个子节点或没有子节点*/
    else
    {
        tempNode = tree; 
        /*要删除节点有右孩子*/
        if(NULL == tree->left)
            tree=tree->right;
        /*要删除节点有左孩子*/
        else if(NULL == tree->right)
            tree = tree->left;
        free(tempNode);
        tempNode = NULL;
    }
    return tree;
}

完整代码及运行结果

完整代码可阅读原文或访问
https://www.yanbinghu.com/2019/04/07/55964.html查看
编译运行结果:

$ gcc -o binarySearchTree binarySearchTree.c
$ ./binarySearchTree
insert 10 to tree
insert 5 to tree
insert 19 to tree
insert 4 to tree
insert 8 to tree
insert 13 to tree
insert 24 to tree
find 13 

总结

本文简单介绍了二叉查找树的插入,查找,删除操作,其中删除操作较为复杂,需要特别注意。

思考

如果待插入数据是已经排好序的,会发生什么情况?


关注公众号【编程珠玑】,获取更多Linux/C/C++/Python/Go/算法/工具等原创技术文章。后台免费获取经典电子书和视频资源

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存