二叉平衡排序树的查找算法

① 数据结构 简单算法实现在二叉排序树上查找关键值k

如果用C语言，应该要写成这样:
typedef
struct
node{int
key;
struct
node
*lchild;
struct
node
*rchild;}bitree;
bitree
*bstsearch(bitree
*t,
int
k)
{
if
(t==NULL
)
//这里t是一个指针，是不能跟0判等的，要和空指针判等
{
return(NULL);//如果t是空指针，表示数是空数，不存在关键值key
}
else
{
while
(t!=NULL)//要循环遍历整个树，寻找关键值key
{
if
(t->key==k)
//如果找到了关键值key，则返回节点指针t
return(t);
else
if
(t->key>k)
//因为是排序树，则有对于任意节点，左孩子小于根小于右孩子
t=t->lchild;
//所以如果当前节点的key大于输入值，则搜索左子树，否则右子树
else
t=t->rchild_;
}
return
NULL;//这里要加这个，如果搜索不到的话要返回空指针
}
}

② 题目3． 平衡二叉树算法查找树中某节点的时间复杂度是多少

平均查找的时间复杂度为O(log n)。

平衡树的查找过程和排序树的相同。在查找过程中和给定值进行比较关键字个数不超过树的深度。

如果二叉树的元素个数为n，那么不管是对树进行插入节点、查找、删除节点都是log(n)次循环调用就可以了。它的时间复杂度相对于其他数据结构如数组等是最优的。

是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。常用算法有红黑树、AVL、Treap、伸展树等。

(2)二叉平衡排序树的查找算法扩展阅读：

二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树算法有五种基本形态：

(1)空二叉树——(a)

(2)只有一个根结点的二叉树——(b);

(3)右子树为空的二叉树——(c);

(4)左子树为空的二叉树——(d);

(5)完全二叉树——(e)

注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。

③ 计算机考研：数据结构常用算法解析(8)

第九章 查找
查找分成静态查找和动态查找，静态查找只是找，返回查找位置。而动态查找则不同，若查找成功，返回位置，若查找不成功，则要返回新记录的插入位置。也就是说，静态查找不改变查找表，而动态查找则会有插入操作，会改变查找表的。
不同的查找所采用的存储结构也不同，静态查找采用顺序表，而动码迟态查找由于经常变动，所以用二叉排序树，二叉平衡树、B-和B+。
静态查找有，顺序查找，折半查找，分块查找(索引顺序查找)
顺序查找(Sequential Search)是最简单的一种查找方法。
算法思路
设给定值为k，在表(R1 R2……Rn)中，从Rn即最后一个元素开始，查找key=k的记录。若存在一个记录Ri(l≤i≤n)的key为k，则查找成功，返回记录序号i;否则，查找失败，返回0。
算法描述
int sqsearch(sqlist r,keytype k) //对表r顺序查找的算法//
{ int i;
r.data[0].key=k; //k存入监视哨//
i=r.len; //取表长//
while(r.data[i].key!=k)
i--; //顺序查找//
return(i);
}
算法用了一点技巧：先将k存入监视哨，若对某个i(≠0)有r.data[i].key=k，则查找成功，返回i;若i从n递减到1都无记录的key为k，i再减1为0时，必有r.data[0].key=k，说明查找失败，返回i=0。
平均查找成功长度ASL= ，而查找失败时，查找次数等于n+l。
折半查找算法及分析
当记录的key按关系≤或≥有序时，不管是递增的还是递减的，只要有序且采用顺序存储。
算法描述
int Binsearch(sqlist r,keytype k) //对有序表r折半查找的算法//
{ int low,high,mid;
low=1;high=r.len; //上下界初值//
while(low<=high) //表空间存在时//
{ mid=(low+high)/2; //求当前mid//
if (k==r.data[mid].key)
return(mid); //查找成功，返回mid//
if (k
high=mid-1; //调整上界，向左部查找//
else
low=mid+1; //调整下界，向右部查找//
}
return(0); //low>high，查找失败//
}
判定树：用来描述二分查找过程的二叉树。n个结点的判定树的深度和n个结点的完全二叉树深度相同= 。但判断树不一定是完全二叉树，但他的叶子结点所在层次之差不超过1。所以，折半查找在查找成功时和给定值进行比笑困较的关键字个数至多为
ASL=
分块查找算法及分析
分块查找(Blocking Search)，又称索引顺序查找(Indexed Sequential Search)，是顺序查找方法的一种改进，目的也是为了提高查找效率。
1.分块
设记录表长为n，将表的n个记录分成b= 个块，每块s个记录(最后一块记录数可以少于s个)，即：
且表分块有序，即第i(1≤i≤b-1)块所有记录的key小于第i+1块中记录的key，但块内记录可以无序。
2.建立索引
每块对应一索引项：
KeymaxLink
其中Keymax为该块内记录的最大key;link为该块第一记录的序号(或指针)。
3.算法思路 分块索碰模念引查找分两步进行：
(1)由索引表确定待查找记录所在的块;(可以折半查找也可顺序因为索引表有序)
(2)在块内顺序查找。(只能用顺序查找，块内是无序的)

考研有疑问、不知道如何总结考研考点内容、不清楚考研报名当地政策，点击底部咨询官网，免费领取复习资料：https://www.87dh.com/xl/