博客
关于我
数据结构·第八章查找·平均查找长度
阅读量:548 次
发布时间:2019-03-09

本文共 682 字,大约阅读时间需要 2 分钟。

版权声明!此乃原创!转载请附上原文出处链接!

静态查找表

(本章存储结构只讲顺序存储,不讲链式存储)

1、顺序查找

优点:算法简单、适应面广,对表结构(顺序表or链表、有序or无序)

缺点:平均查找长度较大 O(n)

2、折半查找

优点:平均查找长度小、查找速度快O(log2n)

缺点:只限于顺序有序表,不适于线性链表
但维护表有序性效率为 O(n)

3、索引顺序表

动态查找表

(存储结构用二叉链表)

1、二叉排序树

在这里插入图片描述

在这里插入图片描述
注:图中左下方的1 2 2 3 3 3指查找成功(如1 指当key=45时的查找长度、2 2指当key=24or53时的查找长度),而平均查找长度为log2n。
右下方的1 2 3 4 5 6指查找成功,而平均查找长度为6,即n。
pi是概率。

在这里插入图片描述

因此常需要重新修改指针
一般是将中序后继结点的数据复制到 p 结点中,相当于删去了 p 结点
在这里插入图片描述
分析:
(1)就平均时间性能而言,二叉排序树上和折半查找一样。
(2)就维护表有序性而言,二叉排序树更香。
无须移动结点,只需修改指针即可完成插入,且其平均执行时间均为 O(log2n)。而折半查找是 O(n)。

2、平衡二叉树(AVL)

(一颗形态均匀的二叉排序树)较高的检索速度

1、结点的平衡因子:该结点的左子树深度与右子树深度之差(最多相差1)
2、最小不平衡子树:在平衡二叉树的构造过程中,以距离插入结点最近的、且平衡因子的绝对值大于 1 的结点为根的子树。
3、插入 平衡二叉树的调整:
LL型:顺时针旋转(右
RR型:逆时针旋转(左
LR型:先逆后顺(先左后右
RL型:先顺后逆(先右后左

你可能感兴趣的文章
MSSQL日期格式转换函数(使用CONVERT)
查看>>
MSTP多生成树协议(第二课)
查看>>
MSTP是什么?有哪些专有名词?
查看>>
Mstsc 远程桌面链接 And 网络映射
查看>>
Myeclipse常用快捷键
查看>>
MyEclipse更改项目名web发布名字不改问题
查看>>
MyEclipse用(JDBC)连接SQL出现的问题~
查看>>
mt-datetime-picker type="date" 时间格式 bug
查看>>
myeclipse的新建severlet不见解决方法
查看>>
MyEclipse设置当前行背景颜色、选中单词前景色、背景色
查看>>
Mtab书签导航程序 LinkStore/getIcon SQL注入漏洞复现
查看>>
myeclipse配置springmvc教程
查看>>
MyEclipse配置SVN
查看>>
MTCNN 人脸检测
查看>>
MyEcplise中SpringBoot怎样定制启动banner?
查看>>
MyPython
查看>>
MTD技术介绍
查看>>
MySQL
查看>>
MySQL
查看>>
mysql
查看>>