二叉排序树的查找 二叉排序树 二叉排序树-定义,二叉排序树-查找

二叉排序树(Binary Sort Tree)或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树;

二叉排序树_二叉排序树 -定义

二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:

(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;

(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;

(3)左、右子树也分别为二叉排序树;

(4)没有键值相等的节点。

二叉排序树_二叉排序树 -查找


二叉树

步骤:

若根结点的关键字值等于查找的关键字,成功。

二叉排序树的查找 二叉排序树 二叉排序树-定义,二叉排序树-查找

否则,若小于根结点的关键字值,递归查左子树。

若大于根结点的关键字值,递归查右子树。

若子树为空,查找不成功。

平均情况分析(在成功查找两种的情况下):

在一般情况下,设 P(n,i)为它的左子树的结点个数为 i 时的平均查找长度。如图的结点个数为 n = 6 且 i = 3; 则 P(n,i)= P(6, 3) = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6

注意:这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。 在一般情况,P(i)为具有 i 个结点二叉分类树的平均查找长度。

P(3) = (1+2+2)/ 3 = 5/3

P(2) = (1+2)/ 2 = 3/2∴ P(n,i)= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n


二叉排序树

∴ P(n)=

P(n,i)/ n

因为 2(1+I/n)lnn≈1.38logn 故P(n)=O(logn)

二叉排序树_二叉排序树 -步骤

若根结点的关键字值等于查找的关键字,成功。

否则,若小于根结点的关键字值,递归查左子树。

若大于根结点的关键字值,递归查右子树。

若子树为空,查找不成功。

插入算法:

首先执行查找算法,找出被插结点的父亲结点。

判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。

若二叉树为空。则首先单独生成根结点。

注意:新插入的结点总是叶子结点。

void InsertBST(t,key)

//在二叉排序树中插入查找关键字key

{

if(t==NULL){

t=new BiTree;

t->lchild=t->rchild=NULL;

t->data=key;

return; }

if(keydata ) InsertBST(t->lchild,key);

else InsertBST (t->rchild, key );

}

void CreateBiTree(tree,d【 】,n)

//n个数据在数组d中,tree为二叉排序树根

{tree=NULL;

for(i=0;i InsertBST(tree,d);}

二叉排序树_二叉排序树 -删除结点

在二叉排序树删去一个结点,分三种情况讨论:

若*p结点为叶子结点,即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构,则可以直接删除此子结点。

若*p结点只有左子树PL或右子树PR,此时只要令PL或PR直接成为其双亲结点*f的左子树(当*p是左子树)或右子树(当*p是右子树)即可,作此修改也不破坏二叉排序树的特性。

若*p结点的左子树和右子树均不空。在删去*p之后,为保持其它元素之间的相对位置不变,可按中序遍历保持有序进行调整,可以有两种做法:

C代码

二叉排序树_二叉排序树 -性能分析


二叉排序树

每个结点的C(i)为该结点的层次数。最坏情况下,当先后插入的关键字有序时,构成的二叉排序树蜕变为单支树,树的深度为其平均查找长度(n+1)/2(和顺序查找相同),最好的情况是二叉排序树的形态和折半查找的判定树相同,其平均查找长度和log 2 (n)成正比。

二叉排序树_二叉排序树 -优化

Size Balanced Tree(SBT)

AVL树

红黑树

Treap(Tree+Heap)

这些均可以使查找树的高度为O(log(n))

  

爱华网本文地址 » http://www.aihuau.com/a/8103480103/111456.html

更多阅读

爱爬树的鱼《君生我已老》 爱爬树的鱼

爱爬树的鱼《君生我已老》推荐指数:4.08文案:她二十七岁那年,他球衣还未换下,丢开篮球用能点亮一百瓦灯泡的眼神将她从头打量到脚,挣扎良久,最终还是嫌弃地对哭得眼泪鼻涕齐飞的她说——

平衡二叉树的生成理论 平衡二叉树

本文由作者收集整理所得,作者不保证内容的正确行,转载请标明出处。作者:关新全1、AVL的插入算法描述在平衡的二叉排序树T上插入一个关键码为kx的新元素,递归算法可描述如下:(一)若T为空树,则插入一个数据元素为kx的新结点作为T的根结

二叉树的基本性质 二叉树的基本性质3

(1)在二叉树的第k层上,最多有2k-1(k≥1)个结点;解释:最多的时候是满二叉树,它的第1层有21-1=1个结点;第2层有22-1=2个结点;第3层23-1=4个结点;第4层有24-1=8个结点;……(2)深度为m的二叉树最多有2m-1个结点,最少有m个结点;(3)对于任意一棵二叉树,度为

金钱树叶子为什么变黄? 金钱树的叶子发黄

家里的客厅里养了一株金铁树,都快半年了,一直长的很好,最近不知道是天气转凉下雨,空气湿气大,还是因为客厅朝北的没有阳光,有二枝刚长出来的新枝上的叶子变黄了,我平时也差不多半个月才浇一次水.不知道是不是水份太多的原因,就在网

声明:《二叉排序树的查找 二叉排序树 二叉排序树-定义,二叉排序树-查找》为网友不变的守候分享!如侵犯到您的合法权益请联系我们删除