共计 1962 个字符，预计需要花费 5 分钟才能阅读完成。
开篇介绍
大家好，我是 Java 最全面试题库 的提裤姐，明天这篇是数据结构与算法的第八篇，次要介绍查找中的树的查找；在后续，会沿着第一篇开篇的常识线路始终总结上来，做到日更！如果我能做到百日百更，心愿你也能够跟着百日百刷，一百天养成一个好习惯。
树的查找
当用线性表作为表的组织模式时，能够有三种查找法，其中 二分查找 效率最高。但因为二分查找要求表中结点按关键字有序，且不能用链表作存储构造，因而，当表的插入或删除操作频繁时，为保护表的有序性，势必要挪动表中很多结点，这种由挪动结点引起的额定工夫开销，就会对消二分查找的长处。即二分查找只实用于动态查找表。若要对动静查找表进行高效率的查找，则能够采纳几种非凡的二叉树或树作为表的组织模式。
二叉排序树的查找
1. 二叉排序树
二叉排序树 (Binary Sort Tree 称二叉查找(搜寻) Binary Search Tree，
定义：二叉排序树或者是空树，或者是满足如下性质的二叉树：
①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
③左、右子树自身又各是一棵二叉排序树。
上述性质简称二叉排序树性质 (BST 性质)，故二叉排序树实际上是满足 BST 性质的二叉树。BST 性质通知咱们，二叉排序树中任一结点 x，其左(右) 子树中任一结点 y(若存在)的关键字必小 (大) 于 x 的关键字。如此定义的二叉排序树中各结点关键字是惟一的。但理论利用中，咱们不能保障被查找的数据集中各元素的关键字互不雷同，所以可将二叉排序树定义中 BST 性质 (1) 里的“小于”改为“大于等于”，或将 BST 质 (2) 里的“大于”改为“小于等于”，甚至可同时批改这两个性质。
从 BST 性质可推出二叉排序树的另一个重要性质：按中序遍历该树所失去的中序序列是一个递增有序序列
代码实现：
public class Search {
public class BiTreeNode {
int m_nValue;
BiTreeNode m_pLeft;
BiTreeNode m_pRight;
}
// 二叉排序树，二叉查找树，二查搜寻树，是一颗具备如下特点的树，树的右边都比它小，树的左边都比它大。public BiTreeNode BinaryBiSearch(BiTreeNode pHead,int b){if(pHead==null)
return null;
if(pHead.m_nValue==b)
return pHead;
if(pHead.m_pLeft!=null)
return BinaryBiSearch(pHead.m_pLeft,b);
if(pHead.m_pRight!=null)
return BinaryBiSearch(pHead.m_pRight,b);
return null;
}
}B 树：
在 B - 树中查找给定关键字的办法是，首先把根结点取来，在根结点所蕴含的关键字 K1,…,Kn 查找给定的关键字（可用程序查找或二分查找法），若找到等于给定值的关键字，则查找胜利；否则，肯定能够确定要查找的关键字在 Ki 与 Ki+ 1 之间，Pi 为指向子树根节点的指针，此时取指针 Pi 所指的结点持续查找，直至找到，或指针 Pi 为空时查找失败。
以上图为例：若查问的数值为5：
第一次磁盘IO：在内存中定位（与 17、35 比拟），比 17 小，左子树；
第二次磁盘IO：在内存中定位（与8、12 比拟），比8小，左子树；
第三次磁盘IO：在内存中定位（与 3、5 比拟），找到 5，终止。
因为 B 树绝对于二叉树来说矮胖了许多，所以它所波及的 IO 操作也绝对少了许多。不过依据咱们下面的剖析，其在查找数据的时候并没有缩小比拟次数。然而咱们晓得，咱们在比拟数据的时候是在内存中进行的，所以相对来说工夫上会更加迅速，简直能够疏忽。
插入流程：
在上面的 B 树中插入 key：
第一步：检索 key 插入的节点地位如上图所示，在 3,5 之间
第二步：判断节点中的关键码个数节点 3，5 曾经是两元素节点，无奈再减少（曾经 = 3-1）。父亲节点 2，6 也是两元素节点，也无奈再减少。根节点 9 是单元素节点，能够降级为两元素节点。
第三步：结点决裂拆分节点 3，5 与节点 2，6，让根节点 9 降级为两元素节点 4，9。节点 6 独立为根节点的第二个孩子。
删除流程：
第一步：判断该元素是否在叶子结点上。该元素在叶子节点上，能够间接删去，然而删除之后，两头节点 12 只有一个孩子，不合乎 B 树的定义：每个两头节点都蕴含 k 个孩子，（其中 ceil（m/2）<= k <= m）所以须要调整；
第二步：判断其左右兄弟结点中有“多余”的关键字，即：原关键字个数 n >=ceil(m/2) – 1；显然结点 11 的右兄弟节点中有多余的关键字。那么可将右兄弟结点中最小关键字上移至双亲结点。而将双亲结点中小于该上移关键字的关键字下移至被删关键字所在结点中即可