1.1 定义
树是由n（n≥0）个节点组成的有限集合，当n=0时成为空树；否则，在任意非空树中：必有一个根节点；剩下的节点被分为m≥0个互不相交的有限集合T1，T2······，这些有限集合的每一个又都是树。树T1，T2······被称作根的子树。树中的每一个节点都是该树中某一棵子树的根。需要注意的是，子树互不相交，即每个节点只属于一棵树（或子树），只有一个双亲。下图(a)表示只有一个节点的树，(b)是有13个节点的树：
1.2 基本术语
树包含若干个结点以及若干指向其子树的分支。结点拥有的子树数称为节点的度（degree）。例如，上图(b)中A的度为3，C的度为1，F的度为0。度为0的节点称为叶子（leaf）节点或终端节点，度不为0的节点称为非终端节点或分支节点。除根节点外，分支节点又称为内部节点。树的度（阶）是树中各节点的最大值，比如上图(b)中树的度为3。节点的子树的根称为节点的孩子（child），相应的，该节点称为孩子的双亲（parent）。例如，上图(b)中，D为A的子树T3的根，则D是A的孩子，而A是D的双亲。同一个双亲的孩子之间互称兄弟（sibling）。例如，上图(b)中，H、I、J互为兄弟。进一步地，可以认为D是M的祖父。节点的祖先是从根到该节点所经分支上的所有节点。例如，上图(b)中，M的祖先为A、D、H。反之，以某节点为根的子树中的任一节点都称为该节点的子孙。如B的子孙为E、F、K、L。
节点的层次（level）从根开始定义起，根为第一层，根的孩子称为第二层。若某节点在第C层，则其子树的根就在C+1层。其双亲在同一层的节点互称为堂兄弟。例如，上图(b)中，节点G与E、F、H、I、J互为堂兄弟。树中节点的最大层次称为树的深度（depth）或高度。例如，上图(b)中树的深度为4。
如果将树中节点的各子树看成从左至右是有顺序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
森林（forest）是m（m≥0）棵互不相交的树的集合。对树中每个节点而言，其子树的集合即为森林。
1.3 基本操作
1、初始化操作：INITIATE（T）。置T为空树。
2、求根方法：ROOT（T）或ROOT（x）。求树T的根或求结点x所在的树的根节点。
3、求双亲：PARENT（T，x）。求树T中节点x的双亲节点。
4、求孩子节点方法：CHILD（T，x，i）：求树T中节点x的第i个孩子节点。
5、求右兄弟节点：RIGHT_SIBLING（T，x）。求树T中节点x右边的兄弟。
6、建树方法：CRT_TREE（x，F）。生成一棵以x节点为根，以森林F为子树森林的树。
7、插入子树：INS_CHILD（y，i，x）。置以节点x为根的树为结点y的第i棵子树。
8、删除子树：DEL_CHILD（x，y）。删除结点x的第i棵子树。
9、遍历：TRAVERSE（T）。按某个次序依次访问树中某个节点，并使每个节点只访问一次。
10、清除结构操作：CLEAR（T）。将树T置为空树。
二叉树是每个节点最多有两棵子树的树结构（不存在度大于2的结点）。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树可以有5种基本形态，如图所示：
二叉树的特点是：树中的每个节点最多只能有两棵子树，即树中任何结点的度不大于2。二叉树的子树有左右之分，而且，子树的左右顺序是重要的，即使在只有一棵子树的情况下，也要分清是左子树还是右子树。
2.1 满二叉树（完美二叉树）
满二叉树（有些地方也叫完美二叉树，参考http://www.cnblogs.com/idorax/p/6441043.html）是指除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。一棵深度为 k 的满二叉树，是由2^k - 1个结点组成的深度为k的二叉树。2^k - 1个结点是二叉树所具有的最大结点个数。例如，下图所示为深度为4的满二叉树：
为便于访问满二叉树的结点，对满二叉树的第一层的结点（即根）开始，自上而下，从左往右，按顺序给节点编号，即得到满二叉树的一个顺序表。
2.2 完全二叉树
一棵具有n个节点，深度为k的二叉树，当且仅当其所有节点对应于深度为k的满二叉树中编号由1到n的那些节点时，该二叉树便是完全二叉树。如下图所示，满二叉树和完全二叉树：
换句话说，完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。
满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。满二叉树一定是完满二叉树，但完满二叉树不一定是满二叉树。
2.3 完满二叉树
完满二叉树是所有非叶子节点的度都是2的树。换句话说，只要你有孩子，就必然有两个孩子。例如，下图所示的树就是一颗完满二叉树：
2.4 二叉树的性质
1、在二叉树的第i层，最多有2^(i-1)个结点（i≥1）。
2、深度为k的二叉树最多有（2^k - 1）个结点（k≥1）。
3、对任何一棵二叉树T，如果其叶子节点数为m，度为2的节点数为n，则m=n+1。
4、具有n个结点的完全二叉树的深度为⌊logn⌋ + 1，其中，⌊⌋符号表示向下取整，读作floor。⌈⌉符号表示向上取整，读作Ceiling。
2.5 二叉树的存储结构及其实现
2.5.1 顺序存储结构
用一组连续的存储单元存储二叉树的数据元素，将二叉树中编号为i的结点的数据元素存放在分量tree[i-1]中，如图所示：
对于上面的完全二叉树，可以用向量（一维数组）tree[0...11]作为它的相应存储结构。对于下图所示的一般二叉树，其顺序存储结构如图所示：
根据完全二叉树的特性，结点在一维数组中的相对位置蕴含着结点间的关系，如tree[i]的双亲为tree[(i+1)/2 - 1]，而其左右两个孩子分别为tree[2i]和tree[2i+1]。显然，这种顺序存储结构仅适用于完全二叉树，因为在顺序存储结构中，仅以结点在一维数组中的相对位置表示结点之间有关系。因此，一般的二叉树也必须按照完全二叉树的形式来存储，这将造成存储空间的浪费。比如上述的一般二叉树，其存储结构中0表示不存在此节点。在最坏的情况下，一个深度为k且只有k个节点的单支树（树中无度为2的节点）却需要2^k - 1个存储分量。
2.5.2 链式存储结构
由二叉树的定义可知，二叉树的结点由数据元素和分别指向左右子树的两个分支构成，也就是说，二叉树的链表中的节点至少包含3个域：数据域和左、右指针域，如图所示：
有时，为了便于找到节点的双亲，还可以增加一个指向其双亲节点的指针域。利用这两个节点结构所得的二叉树存储结构分别叫做二叉链表和三叉链表，如下图所示。链表的头指针指向二叉树的根节点。
2.5.3 Java实现二叉树及其遍历
结点类，用来存储结点的内部数据和维护对下一节点的引用：
public class TreeNode<T> { private T data = null; // 数据部分 private TreeNode<T> left; // 左结点的引用 private TreeNode<T> right; // 右结点的引用 public TreeNode() { } public TreeNode(T data, TreeNode<T> left, TreeNode<T> right) { this.data = data; this.left = left; this.right = right; } public T getData() { return data; } public void setData(T data) { this.data = data; } public TreeNode<T> getLeft() { return left; } public void setLeft(TreeNode<T> left) { this.left = left; } public TreeNode<T> getRight() { return right; } public void setRight(TreeNode<T> right) { this.right = right; } }二叉树：
public class BinaryTree<T> { private TreeNode<T> root; // 根结点 public BinaryTree() { } public BinaryTree(TreeNode<T> root) { this.root = root; } public TreeNode<T> getRoot() { return root; } public void setRoot(TreeNode<T> root) { this.root = root; } /** * 返回父结点 * * @param element * @return */ public TreeNode<T> getParent(TreeNode<T> element) { // 如果根结点为空或者根结点为当前结点，返回null return (root == null || root == element) ? null : parent(root, element); } private TreeNode<T> parent(TreeNode<T> subTree, TreeNode<T> element) { if (subTree == null) { return null; } if (subTree.getLeft() == element || subTree.getRight() == element) { // 返回父结点地址 return subTree; } TreeNode<T> p; // 在左子树中找，如果左子树没有找到，才到右子树中找 if ((p = parent(subTree.getLeft(), element)) != null) { // 递归在左子树中找 return p; } else { // 递归在右子树中找 return parent(subTree.getRight(), element); } } /** * 结点个数 * * @return */ public int getSize() { return getNum(root); } private int getNum(TreeNode<T> node) { if (node == null) { return 0; } else { int i = getNum(node.getLeft()); int j = getNum(node.getRight()); return j + i + 1; } } /** * 树的高度 * * @return */ public int getHeight() { return getHeight(root); } private int getHeight(TreeNode<T> node) { if (node == null) { return 0; } else { int i = getHeight(node.getLeft()); int j = getHeight(node.getRight()); return (i < j) ? (j + 1) : (i + 1); } } /** * 递归实现前序遍历 * * @param node */ public void preOrder(TreeNode<T> node) { if (node != null) { System.out.println(node.getData() + " "); preOrder(node.getLeft()); preOrder(node.getRight()); } } /** * 递归实现中序遍历 * * @param node */ public void inOrder(TreeNode<T> node) { if (node != null) { inOrder(node.getLeft()); System.out.println(node.getData() + " "); inOrder(node.getRight()); } } /** * 递归实现后序遍历 * * @param node */ public void postOrder(TreeNode<T> node) { if (node != null) { postOrder(node.getLeft()); postOrder(node.getRight()); System.out.println(node.getData() + " "); } } /** * 非递归实现前序遍历 * * @param node */ public void iterativePreOrder(TreeNode<T> node) { Stack<TreeNode<T>> stack = new Stack<>(); if (node != null) { stack.push(node); while (!stack.empty()) { node = stack.pop(); System.out.println(node.getData() + " "); if (node.getRight() != null) { stack.push(node.getRight()); } if (node.getLeft() != null) { stack.push(node.getLeft()); } } } } /** * 非递归实现中序遍历 * * @param node */ public void iterativeInOrder(TreeNode<T> node) { Stack<TreeNode<T>> stack = new Stack<>(); while (node != null) { while (node != null) { if (node.getRight() != null) { stack.push(node.getRight()); // 当前结点右子结点入栈 } stack.push(node); // 当前结点入栈 node = node.getLeft(); } node = stack.pop(); while (!stack.empty() && node.getRight() == null) { System.out.println(node.getData() + " "); node = stack.pop(); } System.out.println(node.getData() + " "); if (!stack.empty()) { node = stack.pop(); } else { node = null; } } } /** * 非递归实现后序遍历 * * @param node */ public void iterativePostOrder(TreeNode<T> node) { TreeNode<T> q = node; Stack<TreeNode<T>> stack = new Stack<>(); while (node != null) { // 左子树入栈 for (; node.getLeft() != null; node = node.getLeft()) { stack.push(node); } // 当前结点无右子结点或者右子结点已经输出 while (node != null && (node.getRight() == null || node.getRight() == q)) { System.out.println(node.getData() + " "); q = node; // 记录上一个已输出结点 if (stack.empty()) { return; } node = stack.pop(); } // 处理右子结点 stack.push(node); node = node.getRight(); } } public static void main(String[] args) { // 创建叶子节点 TreeNode<String> l12 = new TreeNode<>("left12", null, null); TreeNode<String> r12 = new TreeNode<>("right12", null, null); TreeNode<String> l22 = new TreeNode<>("left22", null, null); TreeNode<String> r22 = new TreeNode<>("right22", null, null); // 根结点左子树 TreeNode<String> l1 = new TreeNode<>("left1", l12, r12); // 根结点右子树 TreeNode<String> r1 = new TreeNode<>("right1", l22, r22); // 创建根结点 TreeNode<String> root = new TreeNode<>("root", l1, r1); BinaryTree<String> bt = new BinaryTree<>(root); System.out.println("深度：" + bt.getHeight()); System.out.println("结点数：" + bt.getSize()); System.out.println(); System.out.println("==============递归实现前序遍历=============="); bt.preOrder(bt.getRoot()); System.out.println(); System.out.println("==============递归实现中序遍历=============="); bt.inOrder(bt.getRoot()); System.out.println(); System.out.println("==============递归实现后序遍历=============="); bt.postOrder(bt.getRoot()); System.out.println(); System.out.println("==============非递归实现前序遍历=============="); bt.iterativePreOrder(bt.getRoot()); System.out.println(); System.out.println("==============非递归实现中序遍历=============="); bt.iterativeInOrder(bt.getRoot()); System.out.println(); System.out.println("==============非递归实现后序遍历=============="); bt.iterativePostOrder(bt.getRoot()); System.out.println(); } }下面是测试代码创建的二叉树：
遍历（taversal）是树的一种最基本的运算。所谓遍历二叉树就是按照一定规则和次序走遍二叉树的所有节点，使得每个节点都被访问一次，而且只能被访问一次。遍历二叉树的目的在于得到二叉树中各节点的一种线性序列，使非线性的二叉树线性化，从而简化有关的运算和处理。二叉树是非线性的，要得到二叉树中各节点的线性序列不那么容易，因为从二叉树的任意节点出发，既可以向左走，又可以向右走，存在两种可可能。所以，必须为遍历确定一个完整而有规则的走法，以便按同样的方法处理每个节点及其子树。
如果按L、D、R分别表示遍历左子树、访问根节点、遍历右子树，并遵循先左后右的规则，那么，遍历二叉树可以有三种不同的走法，即DLR、LDR和LRD，分别称为前序遍历、中序遍历和后序遍历（前、中、后可以理解为根节点是在前、中还是后）。定义如下：
前序遍历（DLR）
前序遍历又叫做先根遍历、先序遍历。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。若二叉树为空则返回空。
中序遍历（LDR）
中序遍历又叫中根遍历。中序遍历首先遍历左子树，再访问根节点，最后遍历右子树。巧记：左根右。
后序遍历（LRD）
后序遍历又叫后根遍历。后序遍历首先遍历左子树，再遍历右子树，最后访问根节点。
二叉查找树又叫做二叉排序树或二叉搜索树。二叉查找树或者是一棵空树，或者是具有下列性质的二叉树：
1、若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2、若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
3、左、右子树也分别为二叉查找树；
4、没有键值相等的节点。
二叉查找树的插入算法比较简单：空树，就首先生成根节点；不是空树就按照查找的算法，找到父节点，然后作为叶子节点插入，如果值已经存在就插入失败。
删除操作稍微复杂一点，有如下几种情况：
1、如果删除的是叶节点，可以直接删除；
2、如果被删除的元素有一个子节点，可以将子节点直接移到被删除元素的位置；
3、如果有两个子节点，这时候就采用中序遍历，找到待删除的节点的后继节点，将其与待删除的节点互换，此时待删除节点的位置已经是叶子节点，可以直接删除。如下图：
将待删除节点与后继节点互换，变成如下图所示：
将待删除元素删除，如下图所示：
另外，二叉查找树还有一个性质，即对二叉查找树进行中序遍历，即可得到有序的数列。
二叉查找树的查询复杂度，和二分查找一样，插入和查找的时间复杂度均为 O(logn) ，但是在最坏的情况下仍然会有 O(n) 的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡（如上不同形态的二叉树图中的b）。
本节内容来自：https://blog.csdn.net/qq_25940921/article/details/82183093。
平衡二叉树，又称AVL树，它是一种特殊的二叉查找树。AVL树或者是一棵空树，或者是具有以下性质的二叉树：
1、左子树和右子树都是平衡二叉树；
2、左子树和右子树的深度（高度）之差的绝对值不超过1。
由此可以看出平衡二叉树是一棵高度平衡的二叉查找树。所以，要构建跟维系一棵平衡二叉树就比普通的二叉树要复杂的多。在构建一棵平衡二叉树的过程中，当有新的节点要插入时，需要检查是否破坏了树的平衡，如果是，则需要做旋转去改变树的结构。
关于旋转，这东西不拿动态图将还真很难讲明白。所以我就借一下最容易懂得红黑树这篇文章中左旋右旋的图来讲。
左旋：
右旋：
左旋就是将节点的右支往左拉，右子节点变成父节点，并把晋升之后多余的左子节点出让给降级节点的右子节点；
而右旋就是反过来，将节点的左支往右拉，左子节点变成了父节点，并把晋升之后多余的右子节点出让给降级节点的左子节点。
即左旋就是往左变换，右旋就是往右变换。不管是左旋还是右旋，旋转的目的都是将节点多的一支出让节点给另一个节点少的一支。
举个例子，像上图是否平衡二叉树的图里面，左图在没插入前”19“节点前，该树还是平衡二叉树，但是在插入”19“后，导致了”15“的左右子树失去了”平衡“，所以此时可以将”15“节点进行左旋，让”15“自身把节点出让给”17“作为”17“的左树，使得”17“节点左右子树平衡，而”15“节点没有子树，左右也平衡了。如下图：
由于在构建平衡二叉树的时候，当有新节点插入时，都会判断插入后是否平衡，这说明了插入新节点前，都是平衡的，也即高度差绝对值不会超过1。当新节点插入后，有可能会有导致树不平衡，这时候就需要进行调整，而可能出现的情况就有4种，分别称作左左，左右，右左，右右。
左左：
左左即为在原来平衡的二叉树上，在节点的左子树的左子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”10“节点的左子树”7“，的左子树”4“，插入了节点”5“或”3“导致失衡。
左左调整其实比较简单，只需要对节点进行右旋即可，如下图，对节点”10“进行右旋：
注意：如果对左右旋变换还不是很懂或不是很熟练的，可以对照着前面的那两个动图去想象，自己动手变换几次，就明白了。
左右：
左右即为在原来平衡的二叉树上，在节点的左子树的右子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”11“节点的左子树”7“，的右子树”9“，插入了节点”10“或”8“导致失衡。
左右的调整就不能像左左一样，进行一次旋转就完成调整。我们不妨先试着让左右像左左一样对”11“节点进行右旋，结果图如下，右图的二叉树依然不平衡，而右图就是接下来要讲的右左，即左右跟右左互为镜像，左左跟右右也互为镜像。
右右跟左左一样，只需要旋转一次就能把树调整平衡，而左右跟右左也一样，都要进行旋转两次才能把树调整平衡，所以，首先上图的这种调整是错误的，正确的调整方式是，将左右进行第一次旋转，将左右先调整成左左，然后再对左左进行调整，从而使得二叉树平衡。
即先对上图的节点”7“进行左旋，使得二叉树变成了左左，之后再对”11“节点进行右旋，此时二叉树就调整完成，如下图：
右左：
右左即为在原来平衡的二叉树上，在节点的右子树的左子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”11“节点的右子树”15“，的左子树”13“，插入了节点”12“或”14“导致失衡。
前面也说了，右左跟左右其实互为镜像，所以调整过程就反过来，先对节点”15“进行右旋，使得二叉树变成右右，之后再对”11“节点进行左旋，此时二叉树就调整完成，如下图：
右右：
右右即为在原来平衡的二叉树上，在节点的右子树的右子树下，有新节点插入，导致节点的左右子树的高度差为2，如上即为”11“节点的右子树”13“，的左子树”15“，插入了节点”14“或”19“导致失衡。
右右只需对节点进行一次左旋即可调整平衡，如下图，对”11“节点进行左旋：
平衡二叉树构建的过程，就是节点插入的过程，插入失衡情况就上面4种，算简单了，下面讲下平衡二叉树节点的删除，删除的情况会复杂一点，复杂的原因主要在于删除了节点之后要维系二叉树的平衡，但是删除二叉树节点总结起来就两个判断：①删除的是什么类型的节点？②删除了节点之后是否导致失衡？
节点的类型有三种：叶子节点、只有左子树或只有右子树、既有左子树又有右子树。
针对这三种节点类型，再引入判断②，所以处理思路分别是：
1、当删除的节点是叶子节点，则将节点删除，然后从父节点开始，判断是否失衡，如果没有失衡，则再判断父节点的父节点是否失衡，直到根节点，此时到根节点还发现没有失衡，则说此时树是平衡的；如果中间过程发现失衡，则判断属于哪种类型的失衡（左左，左右，右左，右右），然后进行调整。
2、删除的节点只有左子树或只有右子树，这种情况其实就比删除叶子节点的步骤多一步，就是将节点删除，然后把仅有一支的左子树或右子树替代原有结点的位置，后面的步骤就一样了，从父节点开始，判断是否失衡，如果没有失衡，则再判断父节点的父节点是否失衡，直到根节点，如果中间过程发现失衡，则根据失衡的类型进行调整。
3、删除的节点既有左子树又有右子树，这种情况又比上面这种多一步，就是中序遍历，找到待删除节点的前驱或者后驱都行，然后与待删除节点互换位置，然后把待删除的节点删掉，后面的步骤也是一样，判断是否失衡，然后根据失衡类型进行调整。
最后总结一下，平衡二叉树是一棵高度平衡的二叉查找树，所以查询的时间复杂度是 O(log N) 。插入的话上面也说，失衡的情况有4种，左左，左右，右左，右右，即一旦插入新节点导致失衡需要调整，最多也只要旋转2次，所以，插入复杂度是 O(1) ，但是平衡二叉树也不是完美的，也有缺点，从上面删除处理思路中也可以看到，就是删除节点时有可能因为失衡，导致需要从删除节点的父节点开始，不断的回溯到根节点，如果这棵平衡二叉树很高的话，那中间就要判断很多个节点。所以后来也出现了综合性能比其更好的树——红黑树。
本节内容来自https://blog.csdn.net/qq_25940921/article/details/82183093。
红黑树是为平衡二叉树的一种，它具有如下特性：
1、结点是红色或者黑色；
2、根结点是黑色；
3、每个叶子结点都是黑色的空结点（NULL）；
4、每个红色结点的两个子结点都是黑色的；
5、从任意结点到其每个叶子的所有路径都包含相同的黑色结点。
下图就是一棵红黑树：
关于红黑树的更多知识可见https://blog.csdn.net/q3244676719/article/details/81540830、http://www.360doc.com/content/18/0904/19/25944647_783893127.shtml、https://www.jianshu.com/p/e136ec79235c。
红黑树和平衡二叉树的区别如下：
红黑树放弃了追求完全平衡而追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。所以红黑树适用于搜索、插入，删除操作较多的情况。
平衡二叉树追求绝对平衡（所有节点的左右子树高度差不超过1），条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。所以平衡二叉树（AVL树）适合用于插入与删除次数比较少，但查找多的情况。
内存一般是由硅制的存储芯片组成，这种技术在每一个存储单位的代价都要比磁存储技术昂贵两个数量级，因此基于磁盘技术的外存，容量比基于内存的容量至少大两个数量级，这也是目前PC通常内存也就几个G，而硬盘却可以做成上千G的原因。
前面讨论过的数据结构，处理数据都是在内存中，因此考虑的都是内存中的运算时间复杂度。但假如要操作的数据量非常大，大到内存已经没法处理了怎么办呢？如数据库中的上千万条数据的数据表、硬盘中的上万个文件等。在这种情况下，对数据的处理需要不断从硬盘等存储设备中调入或调出内存页面。一旦涉及到这样的外部存储设备，关于时间复杂度的计算就会发生变化，访问该集合元素的时间已经不仅仅是寻找该元素所需比较次数的函数，我们必须考虑对硬盘等外部设备的访问时间以及将会对该设备做出多少次单独访问。
试想一下，为了要在一个拥有几十万个文件的磁盘中找到一个文本文件，你设计的算法需要读取磁盘上万次还是几十次，这是有本质差异的。此时，为了降低对外存设备的访问次数，就需要新的数据结构来处理这样的问题。
前面提到的树，一个结点可以有多个孩子，但是它们自身只存储一个元素。二叉树的限制更多，结点最多只能有两个孩子。每个结点只能存储一个元素，在元素非常多的时候，就使得要么树的度非常大，要么树的高度非常大，甚至两者都必须足够大才行。这就使得内存存取外存次数非常多，这显然成了时间效率上的瓶颈。
多路查找树，每个结点的孩子树可以多余两个，且每一个节点可以存储多个元素。由于它是查找树，所以元素之间存在某种特定的排序关系。
在这里，每一个结点可以存储多少个元素，以及它的孩子数的多少是非常关键的。为此，我们讲解它的四种特殊形式：2-3树、2-3-4树、B树和B+树。
6.1 2-3 树
2-3 树是这样一棵多路查找树：其中的每一个结点都具有两个孩子（2结点）或三个孩子（3结点）。
一个2结点包含一个元素和两个孩子（或没有孩子），且与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素。与二叉排序树不同的是，这个2结点要么没有孩子，要么就有两个，不能只有一个孩子。
一个3结点包含一小一大两个元素和三个孩子（或没有孩子），一个3结点要么没有孩子，要么具有三个孩子。如果某个3节点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。
并且2-3树中所有的叶子结点都在同一层，下图所示就是一棵2-3树：
6.1.1 2-3树的插入
2-3树的插入与二叉排序树相同，插入操作一定是发生在叶子结点上。与二叉排序树不同的是，2-3树插入一个元素的过程有可能会对该树的其余结点产生连锁反应。
2-3树的插入分为三种情况：
1、对于空树，插入一个2结点即可；
2、插入结点到一个2结点的叶子上。由于其本身只有一个元素，所以只需将其升级为3结点即可。如下图所示，我们希望从左图的2-3树中插入元素3，根据遍历可知，3比8小，比4小，于是就只能考虑插入到叶子结点1的位置，因此自然的想法就是将此节点变成一个3结点，即右图这样完成插入操作。当然，要视插入的元素与当前叶子结点元素比较大小后，决定谁在左谁在右。例如，若插入的是0，则此节点就是0在左1在右了。
3、要往3结点插入一个元素。因为3结点本身已经是2-3树的结点最大容量（已经有两个元素），因此就需要将其拆分，且将树中两元素和待插入元素这三者中选择其一向上移动一层。复杂就在此。
第一种情况如下图所示，需要向左图中插入元素5。经过遍历可知元素5比8小比4大，因此它应该是需要插入在拥有6、7元素的3结点位置。问题在于，6/7结点已经是3结点，不能再加。此时发现它的双亲结点4是个2结点，因此考虑让它升级为3结点，这样它就得有3个孩子，于是就想到，将6、7结点拆分，让6与4结成3结点，将5称为它的中间孩子，7成为它的右孩子。
另一种情况是，需要向左图中插入元素11，经过遍历可知11比12、14小，比9、10大，因此它应该是需要插入在拥有9、10元素的3结点位置。同样的道理，9、10结点不能再增加结点，此时发现它的双亲结点12、14也是一个3结点，也不能再插入元素了。再往上看，12、14结点的双亲，结点8是个2结点。于是就想到，将9、10拆分，12、14也拆分，让根结点8升级为3结点，最终形成如下右图的样子。
再看下面的例子，需要在左图中插入元素2，经过遍历可知元素2比4小、6比1大，因此它应该是需要插入拥有1、3元素的3结点位置。而1、3结点、4、6结点都是3结点，都不能插入元素了，再往上看，8、12结点还是一个3结点，这就意味着，当前我们的树结构是三层已经不能满足当前增加结点的需要了。于是将1、3拆分，4、6拆分，根结点8、12也拆分，最终形成如下右图的形式：
6.1.2 2-3树的删除
2-3树的删除也有三种情况。
1、要删除的结点位于一个3结点的叶子结点上，只需在该结点处删除元素即可。如下所示：
2、要删除的结点位于一个2结点上，即要删除的结点是只有一个元素的结点。按照以前树的理解，删除即可， 但这样删除之后就不符合2-3树的定义了。如下图所示，如果删除结点1，那么结点4本来是一个2结点，此时就不满足定义了。
因此，要分为以下四种情形：
① 此节点的双亲也是2结点，且拥有一个3结点的右孩子，如下图所示，删除结点1，则只需要左旋：
② 此结点的双亲是2结点，它的右孩子也是2结点，如下左图所示。此时删除结点1，如果直接左旋会造成没有右孩子，因此需要对整棵树变形。我们的目标是让7变成3结点，那就得让比7稍大的元素8下来，随即就得让比8稍大的元素9补充结点8的位置，如下中图所示，于是再用左旋的方式，变成右图结果：
③ 此节点的双亲是一个3节点，此时删除结点10，意味着双亲12、14这个结点不能成为3结点了，于是将此节点拆分，并将12与13合并成左孩子。
④ 如果当前树是一个满二叉树的情形，此时删除任何一个叶子都会使得整棵树不能满足2-3树的定义。如下图所示，若叶子结点8，就不得不考虑将2-3树的层数减少，办法是将8的双亲和其左子树6合并成一个3结点，再将14与9合并为3结点，最后成右图的样子：
3、要删除的元素位于非叶子的分支结点，此时通常将树按中序遍历后得到此元素的前驱或后继元素，考虑让它们来补位即可。
① 如果要删除的分支结点是2结点，如下图所示要删除结点4，可知它的前驱是1后继是6，显然，由于6、7是3结点，只需用6来补位即可：
② 如果要删除的结点是3结点，如下图所示，我们要删除12、14结点的12，经过分析，显然应该是将3结点的左孩子的10上升到删除位置即可：
6.2 2-3-4树
2-3-4树是2-3树的扩展，包括了4结点的使用。一个4结点包含小中大三个元素和4个孩子（或没有孩子）。一个4结点要么没有孩子，要么有4个孩子。如果某个4结点有孩子的话，左子树包含小于最小元素的元素，第二子树包含大于最小元素、小于第二大元素的元素，第三子树包含大于第二大元素、小于最大元素的元素，右子树包含大于最大元素的元素。
由于2-3-4树和2-3树类似，这里就简单介绍一下。我们构建一个数组为{7,1,2,5,6,9,8,4,3}的2-3-4树的过程，如下图所示。图1是在分别插入7、1、2时的结果图，因为3个元素满足2-3-4树的单个4结点定义，因此此时不需要拆分，接着插入元素5，因为已经超过了4结点的定义，因此拆分为图2的形状。之后的图其实就是在元素不断插入时不断拆分，最后形成了图7的2-3-4树。
下图是对一个2-3-4树的删除结点的演变过程，删除顺序是1、6、3、4、5、2、9。
6.3 B树
B树即为B-树，其中B即Balanced，平衡的意思。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是另一种树。而事实上是，B-树就是指的B树。
B树（B-tree）是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶（order），2-3树是三阶B树，2-3-4树是四阶B树。
一个m阶的B树具有如下性质：
• 如果根结点不是叶结点，则其至少具有两棵子树；
• 每一个非根的分支结点都有 k-1 个元素和 k 个孩子，其中 ⌈m/2⌉≤k≤m。每一个叶子结点 n 都有 k - 1 个元素，其中⌈m/2⌉≤k≤m；
• 所有叶子结点都位于同一层次；
• 所有分支结点包含下列信息数据（n,A0,K1,A1,K2,A2,......,kn,An），其中：Ki（i=1,2,...,n）为关键字，且Ki<Ki+1（i=1,2,...,n-1）;Ai（i=0,2,......,n）为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki（i=1,2,......,n），An所指子树中所有结点的关键字均大于Kn，n•(⌈m/2⌉-1)≤n≤m-1为关键字的个数（或n+1为子树的个数）。
例如，在讲2-3-4树时插入9个数后的图转成B树后如下图的右图所示。左侧灰色方块表示当前结点的元素个数：
在B树上查找的过程是一个顺时针查找结点和在结点中查找关键字的交叉过程。
比如，要查找数字7，首先从外存（比如硬盘中）读取到根结点3、5、8三个元素，发现7不在当中，但在5和8之间，因此就通过A2再读取外存的6、7结点，查找到所需元素。
B树的插入和删除，与2-3树类似，只不过阶数可能会很大。
前面提到，如果内存与外存交换数据频繁，会造成时间效率上的瓶颈，那么B树是怎么做到减少次数的呢？
外存，比如硬盘，是将所有的信息分割成相等大小的页面，每次硬盘读写的都是一个或多个完整的页面，对于一个硬盘来说，一页的长度可能是211到214个字节。
在一个典型的B树应用中，要处理的硬盘数据量很大，无法一次全部装进内存。因此会对B树进行调整，使得B树的阶数（或结点的元素）与硬盘存储的页面大小匹配。比如一棵B树的阶为1001（有1001棵子树，1个结点包含1000个关键字），高度为2，它可以存储超过10亿个关键字，我们只要让根结点持久地保留在内存中，那么在这棵树上，寻找一个关键字最多需要两次硬盘的读取即可。这就好比普通人数钱是一张一张数，而银行职员则是五张甚至十张一数，速度当然比普通人快了不少。
通过这种方式，在有限内存的情况下，每一次磁盘的访问都可以获得最大数量的数据。由于B树的每个结点可以具有比二叉树多得多的元素，所以与二叉树的操作不同，它们减少了必须访问结点和数据块的数量，从而提高了性能。可以说，B树的数据结构就是为内外存的数据交互准备的。
6.4 B+树
尽管B树有诸多好处，但其实它还是有缺陷的。对于树结构来说，我们都可以通过中序遍历来顺序查找树中的元素，这一切都是在内存中进行的。
可是在B树中，我们往返于每个节点之间也就意味着，我们必须得在硬盘页面之间进行多次访问。如下图所示，我们希望遍历这棵B树，假设每个结点都属于硬盘的不同页面，我们为了中序遍历所有元素，页面2→页面1→页面3→页面1→页面4→页面1→页面5。而且每次经过结点1遍历时，都会对结点中的元素进行一次遍历，这就非常糟糕。有没有可能让遍历时每个元素只访问一次呢？
为了解决这个问题，在原有的B树结构基础上，加上了新的元素组织方式，这就是B+树。
B+树是应文件系统所需而出的一种B树的变形树。在B树中，每一个元素在该树中只出现一次，有可能在叶子结点上，也有可能在分支结点上。而在B+树中，出现在分支结点中的元素会被当做它们在该分支结点位置的中序后继者（叶子结点）中再次列出。另外，每一个叶子结点都会保存一个指向后一叶子结点的指针。
下图所示就是一棵B+树，灰色关键字即是根结点中的关键字在叶子结点再次列出，并且所有叶子结点都链接在一起。
一棵m阶的B+树和m阶的B树的差异在于：
• 有n棵子树的节点包含有n个关键字；
• 所有的叶子结点包含全部的关键字信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接；
• 所有分支结点可以看成是索引，结点中只含有其子树中的最大（或最小）关键字。
B+树的最大好处在于，如果要随机查找，就从根结点出发，与B树的查找方式相同，只不过即使在分支结点中找到了待查找的关键字，它也只是用来索引的，不能提供实际记录的访问，还是需要到达包含此关键字的终端结点。
如果需要从最小关键字进行从小到大的顺序查找，就可以从最左侧的叶子结点出发，不经过分支结点，而是沿着指向下一叶子的指针就可以就可以遍历所有的关键字。
B+树的结构特别适合带有范围的查找。比如查找18到22岁学生的人数，可以通过从根结点出发找到第一个18岁的学生，然后再在叶子结点按顺序查找到符合范围的记录。
B+树的插入、删除与B树类似，只不过插入和删除的元素都是在叶子结点上进行。
