博客
关于我
数据结构·第八章查找·平均查找长度
阅读量: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型:先顺后逆(先右后左

你可能感兴趣的文章
Mysql 提示:Communication link failure
查看>>
mysql 插入是否成功_PDO mysql:如何知道插入是否成功
查看>>
Mysql 数据库InnoDB存储引擎中主要组件的刷新清理条件:脏页、RedoLog重做日志、Insert Buffer或ChangeBuffer、Undo Log
查看>>
mysql 数据库中 count(*),count(1),count(列名)区别和效率问题
查看>>
mysql 数据库备份及ibdata1的瘦身
查看>>
MySQL 数据库备份种类以及常用备份工具汇总
查看>>
mysql 数据库存储引擎怎么选择?快来看看性能测试吧
查看>>
MySQL 数据库操作指南:学习如何使用 Python 进行增删改查操作
查看>>
MySQL 数据库的高可用性分析
查看>>
MySQL 数据库设计总结
查看>>
Mysql 数据库重置ID排序
查看>>
Mysql 数据类型一日期
查看>>
MySQL 数据类型和属性
查看>>
mysql 敲错命令 想取消怎么办?
查看>>
Mysql 整形列的字节与存储范围
查看>>
mysql 断电数据损坏,无法启动
查看>>
MySQL 日期时间类型的选择
查看>>
Mysql 时间操作(当天,昨天,7天,30天,半年,全年,季度)
查看>>
MySQL 是如何加锁的?
查看>>
MySQL 是怎样运行的 - InnoDB数据页结构
查看>>