linuxsir首页 LinuxSir.Org | Linux、BSD、Solaris、Unix | 开源传万世,因有我参与欢迎您!
网站首页 | 设为首页 | 加入收藏
您所在的位置:主页 > Linux基础建设 >

二叉搜索树介绍及其接口说明

时间:2018-03-17  来源:未知  作者:admin666

二叉搜索树介绍

二叉搜索树是由二叉树组成专用于查找和搜索目的的一种数据结构。

在二叉搜索树中查询一个结点,从根结点开始,一层一层往下查找,直到找到目标结点为止。以要查找的目标结点为参照,当遇到的结点值比要查找的结点值大时,就顺着该结点的左子树继续查找;当遇到的结点值比要查找的结点值小时,则顺着该结点的右子树继续查找。如果在到达树的分支尽头前都没有找到目标结点,则该结点并不存在于树中。

如下图1所示,要找出树中值为15的结点,从根结点开始,因为15比20小,往20的左结点移动。移动到结点值为9的左子结点上,因为15又比9大,所以往9的右结点移动,此时的结点值恰好是15,于是就找到了所需要的目标结点。

当然,搜索一个二叉树的过程依赖于其结点都是按照类似的方式插入的。因此,要插入一个结点,也是从根结点开始,一层层往下,适当地移动到左或右子结点上,当到达分支的尽头时,执行插入操作。不允许插入重复的结点值

如下图1所示,将值65的结点插入到树中,从根结点开始,因为65比20大,所以向20的右子结点移动。移动到53,又因为65比53大,所以还是向右移动。移动到79,因为65比79小,所以向79的左子结点移动,此时79已经是树的分支尽头了,因此将待插入的结点插入到79对应的左子结点上。插入结束。

二叉搜索树是一种用于查找操作的高效数据结构,因为在最坏的情况下,只需要查找一个分支上的数据就可以了,而不用检索每一个数据。因此,查找的复杂度是O(lg n), 这里的n代表树中的结点的个数。这里树必须是保持平衡的(对于给定数据的结点,要使树的高度尽可能的短)。保持二叉搜索树处于平衡状态是非常重要的,因为这代表着我们查找的分支都不会特别长。

二叉搜索树的接口说明

 二叉搜索树的接口包括初始化、销毁、插入、移除、查找和树的大小等操作。

bistree_init


 void bistree_init(BisTree *tree, void (*compare)(const void *key1,const void *key2),void (*destroy)(void *data));

返回值:无

描述初始化由参数tree所指定的二叉搜索树

该函数必须在其他操作执行前调用。函数指针compare指定一个由用户定义的比较函数。这个比较函数在key1大于key2时返回1,key1小于key2时返回-1,当key1等于key2时返回0。当调用bistree_destroy时,由destroy所指定的析构函数提供了一种释放动态分配的空间的方法。它的工作方式同前面描述过的bitree_destroy类似。如果二叉搜索树包含的数据不需要释放,则destroy应该设置为NULL。

复杂度:O(1)

bistree_destroy


void bistree_init(BisTree *tree);

返回值:无

描述销毁由参数tree所指定的二叉搜索树

调用该函数后其他任何操作都不允许再执行,除非重新调用bistree_init。bistree_destroy将二叉搜索树中所有的结点都移除。如果传给bistree_init的参数destroy不为NULL的话,则每次移除结点时都需要调用由destroy所指定的析构函数。

复杂度:O(n),这里n代表二叉搜索树中的结点个数。

bistree_insert


int bistree_insert(BisTree *tree, const void *data);

返回值:如果插入操作成功,返回0;如果待插入结点已经在树中存在,返回1;否则返回-1。

描述将结点插入由参数tree所指定的二叉搜索树中

新结点包含一个指向参数data的指针,因此只要该结点还在树中,data所引用的内存空间就必须保持有效。由调用者负责管理data所关联的内存空间。

复杂度:O(lg n),这里n代表二叉搜索树中的结点个数。

bistree_remove


int bistree_remove(BisTree *tree, const void *data);

返回值:如果移除操作成功返回0;否则返回-1。

描述在由参数tree所指定的二叉搜索树中,移除数据同参数data相吻合的结点

实际上该操作仅仅只执行一种惰性移除,即该结点只是简单的标识为隐藏。

因此,并不会返回指向结点数据的指针。更进一步的是,树中的数据就算被移除了也必须保持有效。其结果就是,二叉搜索树的大小,即bistree_size的返回值,并不会在移除一个结点后递减。

复杂度:O(lg n),这里n代表二叉搜索树中的结点的个数。

bistree_lookup


int bistree_lookup(const BisTree *tree, void **data);

返回值:如果成功查找到结点,返回0;否则返回-1。

描述判断由参数tree所指定的二叉搜索树中是否存在数据同参数data相吻合的结点

如果查找操作成功,则函数返回后参数data指向查找到结点的数据。

复杂度:O(lg n),这里n代表二叉搜索树中的结点的个数。

bistree_size


int bistree_lookup(const BisTree *tree);

返回值:二叉树中的结点的个数。

描述这是一个宏,用来计算由参数tree所指定的二叉搜索树中的结点的个数。

复杂度:O(1)

友情链接