在二叉判定树以及二分搜索的基础上，基于二叉树的搜索树产生，该数据结构可以随时进行调整，可以保证高效的搜索效率。
内容：
1.二叉搜索树
2.二叉平衡树
3.B-树
一、二叉搜索树
1、定义：（1）所有节点的值都不一样；（2）根节点的值大于左子树所有节点的值；（3）根节点的值小与右子树所有节点的值；（4）左右子树也都是二叉搜索树。
2、基本算法：查找、插入和删除
查找：类似于二分查找，将带查找的值与根节点的值比较，若小于根节点的值，则递归搜索根节点的左子树；否则递归搜索根节点的右子树；若等于根节点的值，则返回成功。
插入：若根节点的为空，则将待插入的值作为根节点；若待插入值小于根节点，则递归搜索根节点的左子树至搜索失败，新建节点并令新节点的值等于待插入的值；若待插入的值大于根节点的值，按类似的方法搜索右子树。当待插入的值等于树中某一节点值时，返回。
删除：当进行删除操作时，如果被删除的节点为叶子节点，则直接将叶子节点删除掉；如果被删除节点只有一个孩子，则将它的孩子代替被删除节点的位置；如果被删除的节点有两个孩子，则令其左子树中最大的元素代替被删除节点的位置，或者令被删除节点右子树中最小的节点代替被删除节点。
二、二叉平衡树
虽然二叉搜索树具有很强的搜索效率，但是假如插入的数据为一有序序列时，二叉树就变为了一个有序链表，搜索效率变低。为了解决这个问题，二叉平衡树出现了。
1、定义：二叉平衡树是一颗二叉搜索树，但是其每个节点左右子树的高度差小于1。
2、基本算法：插入、删除
插入：平衡树的插入与搜索树的插入相同，但是要保证其平衡性。当出现了不平衡现象时，要进行调整：
（1）假设p指向AVL树的树根，若p==NULL,则插入元素的值为即为跟节点的值，树的高度+1。
（2）若根节点不为空，调用Search(p,key)判断待插入元素在树内是否存在。若存在，则返回；若不存在，记录待插入位置A，并转入步骤（3）。
（3）考虑离A最近的节点，若执行插入运算后改节点的平衡因子的绝对值大于一，则把该祖先节点的位置标记为B，左孩子为Bl,右孩子为Br。转入步骤（6）。
（4）若从根节点到A位置的平衡因子都为0，则修改其平衡因子。当插入位置在某个节点的左子树上，改节点的平衡因子+1，插入位置若在某右节点的子树上时，改节点的平衡因子-1。树的高度+1。
（5）若B的平衡因子为１，且新节点插入到B的右子树上时，则B的平衡因子该为０，树的高度不变。
（６）此时B的平衡因子为２，下面细分LL型和LR型：
LL：如果Bl的平衡因子为1，新插入的节点插在Bl的左子树上，则向右旋转调节B为根的子树，树的高度不变；
LR型： 若Bl的平衡因子为-1，且新插入的节点在Bl的右子树上，则参考三原则，最以B为根的节点进行调整。树的高度不变。（一般是先左旋转后右旋转）
（7）当B的平衡因子为-2时，对应的情况时RR和RL，与（6）类似。
网友评论