数据结构基础12———非线性数据结构之自平衡查找树之2-3树

2-3树是最简单的B-树（或-树）结构，其每个非叶节点都有两个或三个子女，而且所有叶都在统一层上。2-3树不是二叉树，其节点可拥有3个孩子。不过，2-3树与满二叉树相似。若某棵2-3树不包含3-节点，则看上去像满二叉树，其所有内部节点都可有两个孩子，所有的叶子都在同一级别。另一方面，2-3树的一个内部节点确实有3个孩子，故比相同高度的满二叉树的节点更多。高为h的2-3树包含的节点数大于等于高度为h的满二叉树的节点数，即至少有2^h-1个节点。换一个角度分析，包含n的节点的2-3树的高度不大于[log2(n+1)](即包含n个节点的二叉树的最小高度)。

1.对于 2- 节点，和普通的 BST 节点一样，有一个数据域和两个子节点指针，两个子节点要么为空，要么也是一个2-3树，当前节点的数据的值要大于左子树中所有节点的数据，要小于右子树中所有节点的数据。

2.对于 3- 节点，有两个数据域 a 和 b 和三个子节点指针，左子树中所有的节点数据要小于a，中子树中所有节点数据要大于 a 而小于 b ，右子树中所有节点数据要大于 b 。

（1）对于每一个结点有 1 或者 2 个关键码。

（2）当节点有一个关键码的时，节点有 2 个子树。

（3）当节点有 2 个关键码时，节点有 3 个子树。

（4）所有叶子点都在树的同一层。

再简单一点定义：
2-3树中一个父节点可以有两个子节点，也可以有三个子节点，并且其也满足类似二叉搜索树的定义（父节点的值大于左子树，但小于右子树），所有叶子节点都在同一层。分为【2节点】和【3节点】

2节点：父节点存储一个值，最多有左右两个子树。
假设父节点为p，子节点为l(左节点)、r(有节点)，且满足：

l < p < r

3节点：父节点存储两个值，最多有左中右三个子树。假设父节点分别为p1,p2，子节点分别为l(左节点)、m(中间节点)、r(右节点)，且满足：

l < p1
p1 < m < p2
r > p2

场景：
前面讲到了二叉搜索树 (BST) 和二叉平衡树 (AVL) ，二叉搜索树在最好的情况下搜索的时间复杂度为 O(logn) ，但如果插入节点时，插入元素序列本身就是有序的，那么BST树就退化成一个线性表了，搜索的时间复杂度为 O(n)。

如果想要减少比较次数，就需要降低树的高度。在插入和删除节点时，要保证插入节点后不能使叶子节点之间的深度之差大于 1，这样就能保证整棵树的深度最小，这就是AVL 树解决 BST 搜索性能降低的策略。但由于每次插入或删除节点后，都可能会破坏 AVL 的平衡，而要动态保证 AVL 的平衡需要很多操作，这些操作会影响整个数据结构的性能，除非是在树的结构变化特别少的情形下，否则 AVL 树平衡带来的搜索性能提升有可能还不足为了平衡树所带来的性能损耗。

因此，引入了 2-3 树来提升效率。2-3 树本质也是一种平衡搜索树，但 2-3 树已经不是一棵二叉树了，因为 2-3 树允许存在 3 这种节点，3- 节点中可以存放两个元素，并且可以有三个子节点。

2-3树的查找

2-3树的查找和二叉查找树类似，要确定一个树是否属于2-3树，我们首先和其跟节点进行比较，如果相等，则查找成功；否则根据比较的条件，在其左中右子树中递归查找，如果找到的节点为空，则未找到，否则返回。查找过程如下图：

如上图
找“H”，首先判断比根节点M小（ASCII码或字母顺序），所以找左节点EJ,E<H<J所以到EJ节点的中间子树寻找,H=H。
找“B”，首先判断比根节点M小（ASCII码或字母顺序），所以找左节点EJ,E>B所以到EJ节点的左子树寻找。到AC节点，A < B < C所以到AC的中间子树查找。

2-3树的插入

和AVL树一样插入需要分成不同的情况

往2-3树中插入元素和往二叉查找树中插入元素一样，首先要进行查找，然后将节点加到未找到的节点上。

2-3树之所以能够保证在最差的情况下的效率的原因在于其插入之后仍然能够保持平衡状态。

如果查找后未找到的节点是一个2节点，那么很容易，我们只需要将新的元素放到这个2节点里面使其变成一个3节点即可。

如图找到需要插入的节点L，因为是一个2节点所以直接加进去变成3节点就可以了。当然如果更简单的如果是空树加入即可。

但是如果查找的节点不幸结束于一个3节点:

节点分裂

由于2-3树只能存在2节点和3节点，但是插入的时候会引入4节点(一个节点有3个值)，所以我们需要将其分裂。

比如单个3节点，只需将中间节点往上提，左边值作为其左子树，右边值作为其右子树即可。
如：

节点合并

比如有父节点的4节点，节点分裂后，需与父节点进行合并。若合并后父节点还是4节点，则继续分裂，直至满足定义为止。下图中6与3合并后，满足条件，无需再进行操作。

当待插入节点为3节点时，假定待插入节点为p，待插入节点的父节点为pp。

将节点强插到p中，此时p中会有三个值，我们暂且称之为4节点。

4节点是不满足2-3树的定义的，因此需要将4节点中的某个节点往上抽离，与pp进行合并。这时需要考虑pp的类型了：

1.若pp为二节点

将分裂的节点放到pp中，则pp成为3节点，满足定义。比如我们在这棵树中插入13。

首先找到要插入的节点"9 12" 变为 "9 12 13"因为3节点中最多只能有两个值，所以进行分裂,取节点中的中间值12，与父节点合并。即父节点的2节点8变为3节点8,12即可




2.若pp为三节点

将分裂的节点放到pp中，则pp成为了4节点，不满足定义，那么4-节点需要提出一个值，并向上合并，这时需要重新设置新旧节点的关系。往上合并的过程就是继续套用这几种情况。好的情况是往上的过程中遇到了2节点，且平衡，则结束；坏的情况是一直到根节点，并且根节点是3树，那么只好继续往上分裂出新的根节点，然后处理新节点与其他节点的关系，此时树高增加了1。

比如在这颗树中插入18。




完成

3.根节点已经是3节点
当根节点已经是3节点时，因为上面没有节点了，不能继续向上继续分裂，所以这时需要增加树的高度来满足平衡条件

比如在这棵树中插入32。







完成

2-3树的删除

同样删除可以分为以下几种情况

待删除的值在叶子节点

1.叶子节点为3节点

直接删除即可






2.叶子节点为2节点
这里需要区分临近兄弟节点的类型。先将节点删除。

（1）兄弟节点为3节点时:
此时被删除后，节点会为空。通过向兄弟节点借一个最近的键值，然后再调整该节点与父节点的值。
比如在这颗树中删除7。







（2）兄弟节点为2节点，这时需要判断父节点类型

a. 父节点为3节点
此时兄弟节点不够借，父节点降元，从3节点变成2节点，与兄弟节点合并。

比如从这棵树中删除36。





b. 父节点为2节点
将父节点和兄弟节点合并，形成新的节点，这是把新节点当做当前节点，不断套用上述几种情况进行调整，直至平衡。这种情况下，若根节点是2节点，树的高度会减1。
1.从这颗树中删除12

兄弟节点和父节点都为2节点，进行合并。此时新节点为[8,9]

当前节点([8,9])的父节点和兄弟节点都为2节点，还需进行合并（即节点2,5合并）合并完成如下图。

2.从这棵树中删除30

节点30的父节点和兄弟节点为2节点，进行合并，此时[22,25]为新节点。

把[22,25]看作当前节点，由于其兄弟节点为2节点，父节点为3节点，套用2.a中的情况，父节点降元，调整完成。

待删除的值在父节点

将该节点与其中序遍历时前驱或后继节点交换，然后删除交换后的叶子节点，此时转换成上一种情况的处理。

前驱节点：该节点左子树最右节点
后继节点：该节点右子树最左节点
那为什么要用前驱/后继节点交换呢？

因为，用前驱/后继节点交换后，才能保持大小顺序。后继节点是右子树中最小的节点，与父节点交换后，排除待删除的叶节点，仍保持左子树<新父节点<右子树的关系。同理，前驱节点是左子树中最大的节点，交换后，仍能保持。

这里我们使用后继节点来进行替换。

从这颗树中删除节点5。


由于5的后继节点是7，先将值进行交换。这时候目的就是删除叶子节点5，于是可以转换成其父节点和兄弟节点都为2节点的情况进行调整。

简单记法

修改后节点中元素：

逢3进1(到上一层)，逢0减1（空节点），根补位多加一层，根借位减一层

用3进制表示各个节点中的元素个数，类比加减乘除的补位借位就可以了。和AVL一样不用死记硬背

2-3树实现

public class Tree23<Key extends Comparable<Key>, Value> {

	/**
	 * 根节点
	 */
	private Node23 root = new Node23();

	/**
	 * 保存key和value的键值对
	 * 
	 * @param <Key>
	 * @param <Value>
	 */
	private class Data<Key extends Comparable<Key>, Value> {
		private Key key;
		private Value value;

		public Data(Key key, Value value) {
			this.key = key;
			this.value = value;
		}

		public void displayData() {
			System.out.println("/" + key + "---" + value);
		}
	}

	/**
	 * 保存树结点的类
	 * 
	 * @param <Key>
	 * @param <Value>
	 */
	private class Node23<Key extends Comparable<Key>, Value> {

		public void displayNode() {
			for (int i = 0; i < itemNum; i++) {
				itemDatas[i].displayData();
			}
			System.out.println("/");
		}

		private static final int N = 3;
		// 该结点的父节点
		private Node23 parent;
		// 子节点，子节点有3个，分别是左子节点，中间子节点和右子节点
		private Node23[] chirldNodes = new Node23[N];
		// 代表结点保存的数据（为一个或者两个）
		private Data[] itemDatas = new Data[N - 1];
		// 结点保存的数据个数
		private int itemNum = 0;

		/**
		 * 判断是否是叶子结点
		 * 
		 * @return
		 */
		private boolean isLeaf() {
			// 假如不是叶子结点。必有左子树（可以想一想为什么？）
			return chirldNodes[0] == null;
		}

		/**
		 * 判断结点储存数据是否满了 （也就是是否存了两个键值对）
		 * 
		 * @return
		 */
		private boolean isFull() {
			return itemNum == N - 1;
		}

		/**
		 * 返回该节点的父节点
		 * 
		 * @return
		 */
		private Node23 getParent() {
			return this.parent;
		}

		/**
		 * 将子节点连接
		 * 
		 * @param index 连接的位置（左子树，中子树，还是右子树）
		 * @param child
		 */
		private void connectChild(int index, Node23 child) {
			chirldNodes[index] = child;
			if (child != null) {
				child.parent = this;
			}
		}

		/**
		 * 解除该节点和某个结点之间的连接
		 * 
		 * @param index 解除链接的位置
		 * @return
		 */
		private Node23 disconnectChild(int index) {
			Node23 temp = chirldNodes[index];
			chirldNodes[index] = null;
			return temp;
		}

		/**
		 * 获取结点左或右的键值对
		 * 
		 * @param index 0为左，1为右
		 * @return
		 */
		private Data getData(int index) {
			return itemDatas[index];
		}

		/**
		 * 获得某个位置的子树
		 * 
		 * @param index 0为左指数，1为中子树，2为右子树
		 * @return
		 */
		private Node23 getChild(int index) {
			return chirldNodes[index];
		}

		/**
		 * @return 返回结点中键值对的数量，空则返回-1
		 */
		public int getItemNum() {
			return itemNum;
		}

		/**
		 * 寻找key在结点的位置
		 * 
		 * @param key
		 * @return 结点没有key则放回-1
		 */
		private int findItem(Key key) {
			for (int i = 0; i < itemNum; i++) {
				if (itemDatas[i] == null) {
					break;
				} else if (itemDatas[i].key.compareTo(key) == 0) {
					return i;
				}
			}
			return -1;
		}

		/**
		 * 向结点插入键值对：前提是结点未满
		 * 
		 * @param data
		 * @return 返回插入的位置 0或则1
		 */
		private int insertData(Data data) {
			itemNum++;
			for (int i = N - 2; i >= 0; i--) {
				if (itemDatas[i] == null) {
					continue;
				} else {
					if (data.key.compareTo(itemDatas[i].key) < 0) {
						itemDatas[i + 1] = itemDatas[i];
					} else {
						itemDatas[i + 1] = data;
						return i + 1;
					}
				}
			}
			itemDatas[0] = data;
			return 0;
		}

		/**
		 * 移除最后一个键值对（也就是有右边的键值对则移右边的，没有则移左边的）
		 * 
		 * @return 返回被移除的键值对
		 */
		private Data removeItem() {
			Data temp = itemDatas[itemNum - 1];
			itemDatas[itemNum - 1] = null;
			itemNum--;
			return temp;
		}
	}

	/**
	 * 查找含有key的键值对
	 * 
	 * @param key
	 * @return 返回键值对中的value
	 */
	public Value find(Key key) {
		Node23 curNode = root;
		int childNum;
		while (true) {
			if ((childNum = curNode.findItem(key)) != -1) {
				return (Value) curNode.itemDatas[childNum].value;
			}
			// 假如到了叶子节点还没有找到，则树中不包含key
			else if (curNode.isLeaf()) {
				return null;
			} else {
				curNode = getNextChild(curNode, key);
			}
		}
	}

	/**
	 * 在key的条件下获得结点的子节点（可能为左子结点，中间子节点，右子节点）
	 * 
	 * @param node
	 * @param key
	 * @return 返回子节点，若结点包含key,则返回传参结点
	 */
	private Node23 getNextChild(Node23 node, Key key) {
		for (int i = 0; i < node.getItemNum(); i++) {
			if (node.getData(i).key.compareTo(key) > 0) {
				return node.getChild(i);
			} else if (node.getData(i).key.compareTo(key) == 0) {
				return node;
			}
		}
		return node.getChild(node.getItemNum());
	}

	/**
	 * 最重要的插入函数
	 * 
	 * @param key
	 * @param value
	 */
	public void insert(Key key, Value value) {
		Data data = new Data(key, value);
		Node23 curNode = root;
		// 一直找到叶节点
		while (true) {
			if (curNode.isLeaf()) {
				break;
			} else {
				curNode = getNextChild(curNode, key);
				for (int i = 0; i < curNode.getItemNum(); i++) {
					// 假如key在node中则进行更新
					if (curNode.getData(i).key.compareTo(key) == 0) {
						curNode.getData(i).value = value;
						return;
					}
				}
			}
		}

		// 若插入key的结点已经满了，即3-结点插入
		if (curNode.isFull()) {
			split(curNode, data);
		}
		// 2-结点插入
		else {
			// 直接插入即可
			curNode.insertData(data);
		}
	}

	/**
	 * 这个函数是裂变函数，主要是裂变结点。 这个函数有点复杂，我们要把握住原理就好了
	 * 
	 * @param node 被裂变的结点
	 * @param data 要被保存的键值对
	 */
	private void split(Node23 node, Data data) {
		Node23 parent = node.getParent();
		// newNode用来保存最大的键值对
		Node23 newNode = new Node23();
		// newNode2用来保存中间key的键值对
		Node23 newNode2 = new Node23();
		Data mid;

		if (data.key.compareTo(node.getData(0).key) < 0) {
			newNode.insertData(node.removeItem());
			mid = node.removeItem();
			node.insertData(data);
		} else if (data.key.compareTo(node.getData(1).key) < 0) {
			newNode.insertData(node.removeItem());
			mid = data;
		} else {
			mid = node.removeItem();
			newNode.insertData(data);
		}
		if (node == root) {
			root = newNode2;
		}
		/**
		 * 将newNode2和node以及newNode连接起来 其中node连接到newNode2的左子树，newNode 连接到newNode2的右子树
		 */
		newNode2.insertData(mid);
		newNode2.connectChild(0, node);
		newNode2.connectChild(1, newNode);
		/**
		 * 将结点的父节点和newNode2结点连接起来
		 */
		connectNode(parent, newNode2);
	}

	/**
	 * 链接node和parent
	 * 
	 * @param parent
	 * @param node   node中只含有一个键值对结点
	 */
	private void connectNode(Node23 parent, Node23 node) {
		Data data = node.getData(0);
		if (node == root) {
			return;
		}
		// 假如父节点为3-结点
		if (parent.isFull()) {
			// 爷爷结点（爷爷救葫芦娃）
			Node23 gParent = parent.getParent();
			Node23 newNode = new Node23();
			Node23 temp1, temp2;
			Data itemData;

			if (data.key.compareTo(parent.getData(0).key) < 0) {
				temp1 = parent.disconnectChild(1);
				temp2 = parent.disconnectChild(2);
				newNode.connectChild(0, temp1);
				newNode.connectChild(1, temp2);
				newNode.insertData(parent.removeItem());

				itemData = parent.removeItem();
				parent.insertData(itemData);
				parent.connectChild(0, node);
				parent.connectChild(1, newNode);
			} else if (data.key.compareTo(parent.getData(1).key) < 0) {
				temp1 = parent.disconnectChild(0);
				temp2 = parent.disconnectChild(2);
				Node23 tempNode = new Node23();

				newNode.insertData(parent.removeItem());
				newNode.connectChild(0, newNode.disconnectChild(1));
				newNode.connectChild(1, temp2);

				tempNode.insertData(parent.removeItem());
				tempNode.connectChild(0, temp1);
				tempNode.connectChild(1, node.disconnectChild(0));

				parent.insertData(node.removeItem());
				parent.connectChild(0, tempNode);
				parent.connectChild(1, newNode);
			} else {
				itemData = parent.removeItem();

				newNode.insertData(parent.removeItem());
				newNode.connectChild(0, parent.disconnectChild(0));
				newNode.connectChild(1, parent.disconnectChild(1));
				parent.disconnectChild(2);
				parent.insertData(itemData);
				parent.connectChild(0, newNode);
				parent.connectChild(1, node);
			}
			// 进行递归
			connectNode(gParent, parent);
		}
		// 假如父节点为2结点
		else {
			if (data.key.compareTo(parent.getData(0).key) < 0) {
				Node23 tempNode = parent.disconnectChild(1);
				parent.connectChild(0, node.disconnectChild(0));
				parent.connectChild(1, node.disconnectChild(1));
				parent.connectChild(2, tempNode);
			} else {
				parent.connectChild(1, node.disconnectChild(0));
				parent.connectChild(2, node.disconnectChild(1));
			}
			parent.insertData(node.getData(0));
		}
	}
}