参考文献

注册

 

发新话题 回复该主题

Beyond是用于创建和交易合成金融产品 [复制链接]

1#
二叉排序树(BinarySearchTree)

普通的二叉树在执行查找操作时候,我们只能按照遍历的顺序逐个地比较每个元素的值,如此方法查找元素的时间复杂度为O(n),思考是否可以通过合理的存储来降低二叉树查询操作的时间复杂度,由此我们引入二叉排序树BST,树中各个元素的规律如下。

左子树上所有节点关键字小于根节点关键字;

右子树上所有节点关键字大于根节点关键字;

左子树,右子树又是一个二叉排序树。

我们重新做一次查询操作,假设查找的元素为9,若按照中序遍历的顺序查询二叉树中的元素我们比较的次数为9次,若我们结合二叉排序树的性质进行查询,则只需要比较3次,就可以找到目标元素,再来看看其他元素,发现其比较的次数也不超过3。可见二叉排序树在在元素查找上有很好的时间特性。

二叉排序树的查找过程,新建查找节点指针,指向根节点,将待查找元素与根节点值进行比较,若相等,直接返回查找结果;若小于根节点值,则将指针移动到左孩子,继续比较;若大于根节点值,则将指针移动到右孩子,继续比较。对于分布均匀的二叉查找树,可以得到其查找的时间复杂度为O(logn),和上面的O(n)比较查找效率提升了很多。

BST基本操作BST查找操作(示例代码)

BSTNode*BST_Search(BiTreeT,ElemTypedata){while(T!=NULLT-data!=data){if(T-datadata){T=T-lchild;//小于根节点,左子树查找}if(T-datadata){T=T-rchild;//大于根节点,右子树查找}}returnT;}BST插入操作(示例代码)

//递归实现boolBST_Insert_Recursion(BiTree*T,ElemTypedata){if(NULL==T){*T=(BiTree)malloc(sizeof(BSTNode));T-data=data;T-lchild=T-rchild=NULL;returntrue;}if(T-data==data){printf("data%dexists\n",data);returnfalse;}elseif(T-datadata){returnBST_Insert((T-lchild),data);}else{returnBST_Insert((T-rchild),data);}}//非递归实现boolBST_Insert_Loop(BiTree*T,ElemTypedata){if(NULL==T){returnInsert(T,data);}BiTreet=T,pre=NULL;while(t!=NULL){pre=t;if(t-datadata){t=t-lchild;}elseif(t-datadata){t=t-rchild;}else{printf("data%dexists\n",data);returnfalse;}}if(pre-datadata){returnInsert((pre-lchild),data);}else{returnInsert((pre-rchild),data);}}//插入新节点boolInsert(BiTree*T,ElemTypedata){*T=(BiTree)malloc(sizeof(BSTNode));T-data=data;T-lchild=T-rchild=NULL;returntrue;}BST删除操作

分析

二叉排序树删除节点的时候,不仅要考虑将节点从原有的二叉排序树中摘下来,且删除节点后的二叉树依然是二叉排序树,按照以下三种情况分析:

若待删除节点为叶子节点,则直接删除即可;若待删除节点只有左子树或右子树,则将左子节点/右子节点的位置置于待删除节点位置;若待删除节点既有左子树又有右子树,则将左子树最大值/右子树最小值节点置于待删除节点位置;

示例代码

BSTNode*FindMax(BiTreeT){if(T){while(T-rchild){T=T-rchild;}}returnT;}BSTNode*FindMin(BiTreeT){if(T){while(T-lchild){T=T-lchild;}}returnT;}//递归算法实现BiTreeBST_Delete(BiTreeT,ElemTypedata){BSTNode*tmp=NULL;if(NULL==T){printf("datanode%dnotexists\n",data);}else{if(dataT-data){T-rchild=BST_Delete(T-rchild,data);}elseif(dataT-data){T-lchild=BST_Delete(T-lchild,data)}else{if(T-lchildT-rchild){tmp=FindMax(T-lchild);T-data=tmp-data;//删除左子树中最大的元素T-lchild=BST_Delete(T-lchild,T-data);}else{tmp=T;//被删除节点最多只有一个子节点情况if(T-lchild){T=T-lchild;}else{T=T-rchild;}free(tmp);}}}returnT;}BST存在的问题

给定两个序列,序列1,,序列2,。按照序列的顺序逐个插入二叉排序树中,得到如下图所示的二叉排序树。尽管两个序列包含的元素相同,由于元素的顺序不一致得到的BST差异比较大,序列2所有的节点都在右子树上面,已经退化成了线性链表,其查找的平均时间复杂度也退化成了O(n)。因此要保证二叉树查找的平均时间复杂度为O(logn),我们必须保证在创建二叉排序树的时候其左右子树的高度不能相差太多。为此引入了平衡二叉树的概念,我们下期见。

参考文献

[1]数据结构:C语言版.严蔚敏等.北京:清华大学出版社,

[2]数据结构考研复习指导:王道论坛.电子工业出版社

[3]数据结构:第二版.陈越.北京:高等教育出版社

获取更多知识请
分享 转发
TOP
发新话题 回复该主题