二叉排序树
有序线性表，并且是顺序存储，查找可以用折半、插值、斐波那契查找算法实现。但是因为有序，在插入和删除操作上，就需要耗费大量的时间。
有没有一种可以使得插入和删除效率不错，又可以比较高效率地实现查找的算法呢？
查找时插入或删除的查找表称为动态查找表。什么样的结构可以实现动态查找表的高效率。
如上图所示58的插入，在线性表顺序结构会影响到62和88；但是在二叉树结构中，58只是成为了它的左子树，58的插入并没有影响到62和88的关系。
也就是说，如果我们对集合{62,88,58,47,35,73,51,99,37,93}做查找，我们打算创建此集合时就考虑用二叉树结构，而且是排好序的二叉树来创建。
创建上图的二叉树，并且我们对它进行中序遍历时，就可以得到一个有序的序列{35,37,47,51,58,62,73,88,93,99}，所以我们通常称它为二叉排序树。
二叉排序树（Binary Sort Tree），又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
- 它的左、右子树也分别为二叉排序树
二叉排序树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度。在一个有序数据集上查找，速度总是要快于无序的数据集，而二叉排序树这种非线性的结构，也有利于插入和删除的实现。
二叉排序树查找操作
二叉排序树初始化、查找、插入
二叉排序树删除
删除结点后，整棵树还要满足二叉排序树的特性，所以需要考虑多种情况，比较复杂
- 删除叶子结点，比较容易，其他结点的结构未受到影响
- 删除的结点只有左子树或只有右子树，结点删除后，将它的左子树或右子树整个移动到删除结点位置，可以理解为独子继承父业
- 删除的结点既有左子树，又有右子树怎么办？
如上图所示，47结点要删掉，它的两个儿子以及子孙该怎么办？
想法1：可以将47结点的左子树操作与只有左子树的操作一样，让35以及它之下的结点成为58的左子树；然后对47的右子树的所有结点进行插入
问题：47的右子树子孙共有5个结点，插入效率低，二叉排序树结构也会发生变化，有可能增加树的高度（增加高度有问题）
想法2：47的两个子树中能否找出一个结点可以代替47呢？果然有，37或48都可以代替，此时删除47后，整个二叉排序树并没有发生本质的改变。
37和48刚好是二叉排序树中最接近47的两个数，如果对二叉排序树进行中序遍历，他们刚好是47的前驱或直接后继。
所以比较好的办法：找到p的直接前驱（或者直接后继）s，用s来替换结点p，然后在删除s，如下图所示：
删除结点的三种情况：
- 叶子结点
- 仅有左子树或者右子树的结点
- 左右子树都有结点
二叉排序树总结
二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点。找到合适的插入和删除位置，修改链接指针即可。
二叉排序树查找，比较次数等于给定值的结点在二叉排序树的层数。最多不超过树的深度。
二叉排序树的查找性能取决于二叉排序树的形状。
{62,88,58,47,35,73,51,99,37,93}可以构建左图二叉排序树，如果数组为{35,37,47,51,58,62,73,88,93,99}，则二叉排序树就变成极端的右斜树，它依然是一棵二叉排序树；如下图所示，同样是查找结点99，左图只需要比较两次，而右图就需要10次。
所以我们希望二叉排序树是比较平衡的，**即其深度与完全二叉树相同，均为(㏒₂n) + 1，那么查找时间复杂度为O(㏒n)，近似于折半查找。事实上，上左图，也不够平衡，明显左重右轻。
不平衡的最坏情况如上右图所示，查找时间复杂度为O(n)，等同于顺序查找。
我们希望一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树，如何让二叉排序树平衡？
概念
平衡二叉树（Self-Balancing Binary Search Tree or Height-Balanced Binary Search Tree），是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。
英文名称可以体会，它是一种高度平衡的二叉排序树。
二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF（Balance Factor）。平衡二叉树上所有结点的平衡因子只能是-1，0，1。只要二叉树上有一个结点的平衡因子的绝对值大于1，该二叉树就是不平衡的。
- 图2：59比58大，确实58的左子树，不符合二叉排序树的定义，所以不是平衡二叉树
- 图3：58左子树高度2（左子树高度应该是3吧？），右子树高度0，二者差大于绝对值1，因此不平衡
距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。
插入结点37，最近平衡因子超过1的结点为58，所以从58开始以下的子树为最小不平衡子树。
平衡二叉树实现原理
思想：构想过程，每插入一个结点，先检查是否因插入而破坏了树的平衡性，若是，找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。
假设一个数组a[10]={3,2,1,4,5,6,7,10,9,8}构建二叉排序树。
图1高度为8的二叉树查找非常不利，希望构建成图2的二叉树，查询效率高，如何构想出图2？
- 插入1不平衡，3结点的bf = 2，为正值，然后对最小平衡树进行 顺时针右旋
- 插入5不平衡，最小平衡树为3，4，5，结点3的bf = -2 < 0 所以逆时针左旋
- 插入结点6和结点7
- 插入10，7的bf = -2，直接左旋二叉树就不是二叉排序树，原因是根结点7的bf = -2，子节点10的bf = 1，符号不统一。所以首先要统一符号，先对结点9和10右旋，9的bf = -1 符号统一，然后将以结点7为最小不平衡树左旋。
- 插入8，同上
平衡二叉树实现代码（后续掌握）
我们需要查找的集合本身没有顺序，在频繁查找的同时也要经常的插入和删除操作，所以我们需要构造一棵二叉排序树。
不平衡的二叉排序树，查找效率非常低，因此构建过程中，需要平衡二叉树。此时查找时间复杂度为O(㏒n)，而插入和删除也为O(㏒n)。
这是比较理想的动态查找表算法。
红黑树也是二叉排序树的平衡算法。
多路查找树（muitl-way search tree），其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。
2-3树
2-3树是这样的一棵多路查找树：其中的每一个结点都具有两个孩子（我们称它为2结点）或三个孩子（我们称它为3结点）
- 一个2结点包含一个元素和两个孩子（或没有孩子，不能只有一个孩子），且与二叉排序树类似
- 一个3结点包含一小一大两个元素和三个孩子（或没有孩子）
- 2-3树中所有的叶子都在同一层次上
2-3树插入
插入操作一定发生在叶子结点上，与二叉排序树不同的是，2-3树插入一个元素可能会对该树的其余结点产生连锁反应
通过这个插入可以发现，2-3树插入的传播效应导致了根结点的拆分，树的高度就会增加。
2-3树删除
删除叶子是2结点的情况：
-
双亲是2结点，且拥有一个3结点的右孩子
-
双亲是2结点，右孩子也是2结点
-
双亲是3结点
-
满二叉树
删除非叶子结点：
将树进行中序遍历，获得其前驱或者后继，来填补空位
2-3-4树（对2-3树的扩展）
B树
B树（B-tree）是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶（order），因此2-3树是3阶的B树，2-3-4树是4阶的B树。
B+树
存储位置 = f(关键字)
通过查找关键字不需要比较就可获得需要记录的存储位置，这就是散列技术。
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。
f称为散列函数，又称为哈希（Hash）函数。
采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。
关键字对应的记录存储位置称为散列地址。
散列表查找步骤
整个散列过程其实就是两步
- 散列函数计算记录的散列地址，并按此散列地址存储该记录。
- 查找时，通过同样的散列函数计算记录的散列地址，按该地址访问该记录。
散列技术既是一种存储方法，也是一种查找方法。
散列只与关键字有关，因此，散列主要是面向查找的存储结构。
散列技术最适合求解问题是查找与给定值相等的记录。简化了比较过程，效率大大提高。
散列技术不适用：
- 一个关键字对应多条记录
- 范围查找
两个关键字key1 <> key2 ，但是有f(key1) = f(key2)，这种现象称为冲突（collision），并把key1和key2称为这个散列函数的同义词（synonym）
散列函数的构造方法
如何设计好的散列函数？
- 计算简单：保证所有关键字都不冲突，算法会很复杂，耗费很多时间，对于需要频繁查找来说，大大降低了查找效率。因此散列函数的计算时间不应该超过其他查找技术与关键字比较的时间。
- 散列地址分布均匀：散列地址均匀分布在存储空间，保证存储空间有效利用，减少为处理冲突而耗费的时间。
直接定址法
取关键字的某个线性函数值为散列地址，即：
f(key) = a*key+b (a、b为常数)
简单、均匀、无冲突，但事先要知道关键字的分布情况，适合查找表较小且连续的情况。现实应用不常用。
数字分析法（手机号码后四位）
适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，可以考虑用此方法。
平方取中法
关键字平方后取中间三位
适合不知道关键字的分布，而位数又不是很大的情况。
折叠法
折叠法是将关键字从左到右分割成位数相等的几部分（最后一部分可以短一些），然后将几部分折叠求和，按照散列表表长，取最后几位作为散列地址。
除留余数法
此方法为最常用的构造散列函数方法，对于散列表长为m的散列函数公式为：
f(key) = key mod p (p<=m)
mod是取模（求余数），不仅可以对关键字直接取模，也可以在折叠、平方取中后再取模。
关键在于p的选择，p选的不好，会出现很多同义词。
经验：散列表表长为m，通常p为小于或等于表长（最好接近m）的最小质数或不包含小于20质因子的合数。
随机数法
取关键字的随机函数值为它的散列地址
f(key) = random(key)
适用于关键字长度不等
关键字是字符串如何处理？英文、中文和各种各样的符号都可以转化为数字来对待。
散列函数选择
- 计算散列地址所需时间
- 关键字的长度
- 散列表的大小
- 关键字的分布情况
- 记录查找的频率
处理散列冲突
开放定址法（开放寻址法）
一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
f₁(key) = (f(key)+d₁) MOD m (d₁=1,2,3,4…m-1)
这种解决冲突的开放定址（寻址）法称为线性探测法。
本来不是同义词却需要争夺一个地址的情况，称为堆积。
增加平方运算的目的是为了不让关键字都聚集在某一块区域。我们称这种方法为二次探测。
f₁(key) = (f(key)+d₁) MOD m (d₁=1²,-1²,2²,-2²,q²,-q²…q<=m/2)
在冲突时，位移量d采用随机函数（伪随机数，同样的随机种子，每次得到的数列也是相同的）计算得到，我们称之为随机探测法。
再散列函数法
会增加计算时间
链地址法
会带来查找时遍历单链表的性能损耗
公共溢出区法
冲突的重新找内存存储
冲突数据很少的情况下，公共溢出区结构对查找性能来说还是非常高的
点击拨打：