Question

查找——动态查找

Answer 1

等概率下动态查找的方式。

定义：二叉排序树或者是一棵空树，或者是具有下列性质的[二叉树]
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；

二叉排序树的查找、插入和删除过程
查找过程：
1、若根结点的关键字值等于查找的关键字，[成功]
2、若小于根结点的关键字值，递归查左子树。
3、若大于根结点的关键字值，递归查右子树。
4、若子树为空，查找不成功。

插入和删除过程：
先看图，构造一个序列为{45,24,53,45,12,24,90}的二叉排序树。

因为树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

跟插入不同的是，删除结点的过程要分几种情况。
分为三种情况：（删除结点为p ，其父结点为f）
（1）要删除的p结点是叶子结点，只需要修改它的双亲结点的指针为空
（2）若p只有左子树或者只有右子树，直接让左子树/右子树代替p
（3）若p既有左子树，又有右子树，用p左子树中最大的那个值（即最右端S）代替P，删除s，重接其左子树

性能分析：
查找性能：
含有n个结点的二叉排序树的平均查找长度和树的形态有关，
（最坏情况）当先后插入的关键字有序时，构成的二叉排序树蜕变为单枝树。查找性能为O(n)
（最好情况）二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log2(n)成正比

插入、删除性能：
插入、删除操作间复杂度都O(log(n))级的，
即经过O(log(n))时间搜索到了需插入删除节点位置和删除节点的位置， 经O(1)级的时间直接插入和删除
*与顺序表相比，比顺序表插入删除O(n)(查找时间O(log(n))移动节点时间O(n))要快
*与无序顺序表插入时间O(1)，删除时间O(n)相比，因为是有序的，所查找速度要快很多

左右两个子树的高度差的绝对值不超过 1。

那么我们来看以序列（13,24,37,90,53）生成平衡树的过程。

1、LL型平衡旋转
由于在A的左子树的左子树上插入结点，使平衡因子由1变为2而失去平衡，需进行一次顺时针旋转操作。
2、RR型平衡旋转
由于在A的右子树的右子树上插入结点，使平衡因子由-1变为-2而失去平衡，需进行一次逆时针旋转操作。
3、LR型平衡旋转
由于在A的左子树的右子树上插入结点，使平衡因子由1变为2而失去平衡，需进行两次旋转操作（先逆时针，后顺时针）。
4、RL型平衡旋转
由于在A的右子树的左子树上插入结点，使平衡因子由-1变为-2而失去平衡，需进行两次旋转操作（先顺时针，后逆时针）。

平衡树查找的分析
因为这个是比较平衡的，所以相对于二叉排序树，它没有最坏的情况，复杂度为O(logN)；
插入的分析，因为每次插入都要计算平衡因子，所以某些结点是需要旋转的，但也只最多旋转一次。因此，总体上插入操作的代价仍然在O(logN)级别上(插入结点需要首先查找插入的位置)。
删除的分析，因为删除某个结点之后，其后的所有结点都需要重新计算平衡因子，每一次删除操作最多需要O(logN)次旋转。因此，删除操作的时间复杂度为O(logN)+O(logN)=O(2logN)

B-树及其查找、查找分析
http://www.sohu.com/a/154640931_478315
B+ 树及其查找、分析
http://www.sohu.com/a/156886901_479559
键树（数字查找树）
https://blog.csdn.net/mevicky/article/details/46041493