二叉排序树，平衡二叉树，B树

二叉排序树

二叉排序树性质：
1.若左子树不空，左子树元素比其根节点小
2. 若右子树不空，右子树元素比其根节点大
3. 它的左右子树也是二叉排序树
二叉排序树操作
1 查找：
在二叉排序树上查找关键字类似于折半查找
2 插入：
插入操作以查找操作为基础，先进行查找当树中不存在结点时才插入，新插入的节点一定是一个叶子结点，若本身树中有这个元素那么插入失败
3 创建：
从空开始逐个经过查找为基础插入
4 删除：
删除节点会比较复杂，有三种情况：
1 被删除的是叶子结点，那么直接删除
2 被删除的不是叶子结点：
(1)若只有左子树或者只有右子树的结点:
将待删除结点删除然后其子结点连接至被删除结点的父节点
(2)若待删除结点同时有左右子树：
将待删除结点左子树的最右结点或者右子树的最左结点值覆盖被删除结点然后将这个结点删除

平衡二叉树

本质也是一个二叉排序树
平衡二叉树性质：
左右子树高度之差的绝对值不超过1，即平衡因子只能是1，0，-1
平衡调整的步骤：
(1)找|平衡因子|=2的结点
(2)找插入新结点后失去平衡的最小子树
最小子树： 距离插入结点最近的3个结点而且这3个结点以|平衡因子|=2为根的子树
(3)进行平衡调整：
平衡调整的4个情况：
1.LL型：R旋
2.RR型：L旋
3.LR型：先下面两个结点整体L旋变成LL型然后再R旋
4.RL型：先下面两个结点整体R旋变成RR型然后再L旋

平衡二叉树的建立：
因为平衡二叉树是二叉排序树，建立方法类似，就是先查找应在什么地方，然后插入，每次插入后再进行平衡调整

平衡二叉树的删除：
在二叉排序树基础上增加平衡调整
1 先删除：
1 被删除的是叶子结点，那么直接删除
2 被删除的不是叶子结点：
(1)若只有左子树或者只有右子树的结点:
将待删除结点删除然后其子结点连接至被删除结点的父节点
(2)若待删除结点同时有左右子树：
将待删除结点左子树的最右结点或者右子树的最左结点值覆盖被删除结点然后将这个结点删除
2 再调整

B树

B树性质：
(1)n阶B树每一个结点(除首结点)的关键字(数值元素)最多n-1个，最少┌m/2 ┐-1 ,
分支(指针)个数最多n个
如5阶B树：分支最多5个，除了首结点其余结点的关键字最少2两个，最多4个，当 出现5个就溢出需要调整
(n阶B树指分支为n)
(2)每个结点内部的关键字都是从小到大有序的

B树的插入
基于一个原则：多就上升，且取中然后切分两段

分析：插入4 先放入形成345不满住3阶B树性质，满了就往上升，按中间为分界点切分成3 4 5三个结点 然后将中间结点4放入父结点形成246仍然不满住3阶B树继续切分往上升形成49合理

B树的删除
类似于二叉排序树删除
1.删除叶子结点：
(1)若删除了被删除处仍满足原来的结点个数要求就直接删除
(2)若删除了被删除处不满足原来结点个数要求
a.若兄弟结点关键字数目大于┌m/2 ┐-1即兄弟删除一个也仍然合理,
此时直接用父结点覆盖删除处，然后用兄弟结点覆盖父结点
(理解为：先借父，父再借兄弟)
b.若兄弟结点关键字数目等于┌m/2 ┐-1即兄弟删除一个就不合理了，
此时删除这个结点然后把父结点拉下来然后这个整体再和兄弟结点连接一块
(理解为：自己不合理，兄弟也穷，那么全家一块穷)
2.删除非叶子结点：
(1)若左子树最右结点或者右子树最左结点至少有一个被删除后仍合理则直接用这个叶子结点覆盖待删除结点然后将将其删除
(2)若左子树最右结点或者右子树最左结点没有一个满足被删除后仍合理，则直接将此结点和其兄弟结点合并