408
数据结构 7 查找
查找的基本概念
查找表 用于查找的数据集合，静态为不删减，动态增加删除
平均查找长度ASL 需要比较的平均次数
顺序查找
顺序表，链表都适用，正常查找 o(n)
优化 有序，减少失败ASL；将概率大的数据放前面
折半查找
二分查找 o(log2 n)
失败条件 L指针大于H
判定树 平衡树，向上向下取整决定左右子树的大小关系
折半查找次数不超过树高，适合有序顺序存储
分块查找
块内无序，块间有序
ASL=索引ASL+块内ASL
最小ASL，块数平方为字数
二叉排序树BST
左<中<右，中序遍历为顺序数列，可以是空，最差o(n)，最好o(log2 n)，适合动态查找
插入 插入访问失败最后节点的孩子，不可相同
删除 叶节点直接删除；只有一颗子树直接添加；两颗子树找前驱或后继
！平衡二叉树AVL
左右高度差不超过1，查找o(log2 n)
AVL插入
根据插入点后最小不平衡树
LL 右旋转
RR 左旋转
LR 左右
RL 右左
根据情况将子树迁移
构造时按照插入处理
AVL删除
删除操作先按照BST处理，再按照插入处理，再继续检查是否传递不平衡
红黑树RBT
左中右，根叶黒，无二红，黑数同，查找o(log2 n)
引入了NULL作为叶子，黒
L最大不超过L最小的二倍
RBT插入
只需要关注插入节点的叔节点
叔节点黒 根据AVL插入处理，一次的父爷变换，两次的爷孙变换
叔节点红 爷父叔变换，爷作为新节点检查
RBT删除
查找o(log2 n)，先按照BST处理，再进行变换