博客
关于我
数据结构·第八章查找·平均查找长度
阅读量: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
查看>>
MTK Android 如何获取系统权限
查看>>
MySQL - 4种基本索引、聚簇索引和非聚索引、索引失效情况、SQL 优化
查看>>
MySQL - ERROR 1406
查看>>
mysql - 视图
查看>>
MySQL - 解读MySQL事务与锁机制
查看>>
MTTR、MTBF、MTTF的大白话理解
查看>>
mt_rand
查看>>
mysql /*! 50100 ... */ 条件编译
查看>>
mudbox卸载/完美解决安装失败/如何彻底卸载清除干净mudbox各种残留注册表和文件的方法...
查看>>
mysql 1264_关于mysql 出现 1264 Out of range value for column 错误的解决办法
查看>>
mysql 1593_Linux高可用(HA)之MySQL主从复制中出现1593错误码的低级错误
查看>>
mysql 5.6 修改端口_mysql5.6.24怎么修改端口号
查看>>
MySQL 8.0 恢复孤立文件每表ibd文件
查看>>
MySQL 8.0开始Group by不再排序
查看>>
mysql ansi nulls_SET ANSI_NULLS ON SET QUOTED_IDENTIFIER ON 什么意思
查看>>
multi swiper bug solution
查看>>
MySQL Binlog 日志监听与 Spring 集成实战
查看>>
MySQL binlog三种模式
查看>>
multi-angle cosine and sines
查看>>