# 定义

2-3-4 树是多路搜索树；4 阶的 B 树；所有结点有序
是一棵自平衡树；每个叶子结点的深度一样、完美平衡。
叶子结点除外，内部结点只能是：2 结点、3 结点、4 结点

# 结点类型

2 结点：1 个元素，2 个子结点
2结点

3 结点：2 个元素，3 个子结点
3结点

4 结点：3 个元素，4 个子结点
4结点

# 插入

插入操作都是在叶子结点进行合并或分裂。

# 插入情形

2 - 结点、3 - 结点：直接合并（nodeMerge）
4 - 结点：分裂（nodeSplit）
a. 4 - 结点先分裂，插入结点再和左、右子结点合并
b. 分裂后的结点继续向上合并或再分裂

# 代码实现

# 类结构

TwoFourTree 对象结构：

	@SuppressWarnings({ "unchecked", "rawtypes", "hiding" })
	public class TwoFourTree<K extends Comparable<K>, V> {
	// 2-3-4 树是阶为 4 的 B 树
	private static final int ORDER = 4;

	// 结点最多元素个数
	private static final int MAX_SIZE = 3;

	private Node<K, V> root;

	private int size = 0;

	// 创建 key 数组的类型，泛型数组创建需要通过反射机制
	private Class<?> keyclass;
	// 创建 value 数组的类型，泛型数组创建需要通过反射机制
	private Class<?> valueclass;

	public TwoFourTree(Class<?> keyClass, Class<?> valueClass) {
	this.keyclass = keyClass;
	this.valueclass = valueClass;
	}

	// ......
	}

Node 对象结构：

	private class Node<K extends Comparable<K>, V> {
	// 父结点
	Node parent;
	// 结点的子树
	Node[] children = new Node[ORDER];

	// 结点的元素（key，value），以及元素个数
	K[] keys = (K[]) Array.newInstance(keyclass, MAX_SIZE);
	V[] values = (V[]) Array.newInstance(valueclass, MAX_SIZE);
	int size;

	private Node(Node parent, K key, V value) {
	this.parent = parent;
	size = 1;
	keys[0] = key;
	values[0] = value;
	}

	// for gc, unbind connected obj
	private void delete() {
	parent = null;
	children = null;
	keys = null;
	values = null;
	size = 0;
	}
	}

# 结点合并

	private Node nodeMerge(Node node, Node insertNode, int instIdx) {
	if (instIdx < node.size) {
	// 数组元素往后移动 1 格，腾出插入空间
	moveElement(node, instIdx, node, instIdx + 1, node.size - instIdx);
	//instIdx 位置的子结点被替换；instIdx+1 位置需要插入新的子结点
	moveChild(node, instIdx + 1, node, instIdx + 2, node.size - instIdx);
	}

	// 插入元素
	moveElement(insertNode, 0, node, instIdx);
	// 插入 2 个新的子结点
	moveChild(insertNode, 0, node, instIdx, 2);
	// 结点元素个数 + 1
	node.size++;

	// 删除插入结点
	insertNode.delete();
	return node;
	}

# 结点分裂

	private Node nodeSplit(Node node, Node insertNode, int instIdx) {
	// 分裂 4 - 结点：中间元素成为父结点，两边元素成为（左 / 右）子结点
	Node split2Parent, split2Left, split2Right;
	// 分裂出父结点
	split2Parent = new Node(node.parent, node.keys[1], node.values[1]);

	// 分裂出右子结点
	split2Right = new Node(split2Parent, node.keys[2], node.values[2]);
	moveChild(node, 2, split2Right, 0, 2);

	// 分裂出左子结点
	split2Left = node;
	split2Left.size = 1;
	split2Left.parent = split2Parent;

	// 设置分裂父结点的 2 个子结点
	split2Parent.children[0] = split2Left;
	split2Parent.children[1] = split2Right;

	// 插入结点再与左右子结点合并
	if (instIdx < 2) {
	// instIdx = 0, 1 [0-left or 1-right]
	nodeMerge(split2Left, insertNode, instIdx);
	} else {
	// instIdx = 2, 3 [0-left or 1-right]
	// instIdx - 2 = 0, 1
	nodeMerge(split2Right, insertNode, instIdx - 2);
	}

	return split2Parent;
	}

# 元素迁移，孩子结点迁移

	private void moveElement(Node oldNode, int oldIdx, Node newNode, int newIdx) {
	System.arraycopy(oldNode.keys, oldIdx, newNode.keys, newIdx, 1);
	System.arraycopy(oldNode.values, oldIdx, newNode.values, newIdx, 1);
	}

	private void moveElement(Node oldNode, int oldIdx, Node newNode, int newIdx, int size) {
	System.arraycopy(oldNode.keys, oldIdx, newNode.keys, newIdx, size);
	System.arraycopy(oldNode.values, oldIdx, newNode.values, newIdx, size);
	}

	private void moveChild(Node oldParent, int oldChildIdx, Node newParent, int newChildIdx) {
	// jvm: -ea
	assert oldChildIdx < ORDER && newChildIdx < ORDER
	: "child's position out-of-bounds. " + oldChildIdx + ", " + newChildIdx;

	System.arraycopy(oldParent.children, oldChildIdx, newParent.children, newChildIdx, 1);

	// update child's parent
	if (newParent.children[newChildIdx] != null) {
	newParent.children[newChildIdx].parent = newParent;
	}
	}

	private void moveChild(Node oldParent, int oldChildIdx, Node newParent, int newChildIdx, int size) {
	// jvm: -ea
	assert oldChildIdx < ORDER && newChildIdx < ORDER
	: "child's position out-of-bounds. " + oldChildIdx + ", " + newChildIdx;

	System.arraycopy(oldParent.children, oldChildIdx, newParent.children, newChildIdx, size);

	for (int i = 0; i < size; i++) {
	// update child's parent
	if (newParent.children[newChildIdx + i] != null) {
	newParent.children[newChildIdx + i].parent = newParent;
	}
	}
	}

# 插入

	public V put(K key, V value) {
	if (key == null) {
	throw new IllegalArgumentException("key can not be null.");
	}

	// 查找插入的结点，以及结点的插入位置
	Node node = null;
	int i = 0;
	Node p = root;
	while (p != null) {
	i = 0;
	node = p;
	for (i = 0; i < p.size; i++) {
	int cmp = key.compareTo((K) p.keys[i]);
	if (cmp < 0) {
	p = p.children[i];
	break;
	} else if (cmp > 0 && i == p.size - 1) {
	i++;
	p = p.children[i];
	break;
	} else if (cmp == 0) { // updated
	V oldValue = (V) p.values[i];
	p.values[i] = value;
	return oldValue;
	}
	}
	}

	// 0. 根结点
	if (node == null) {
	root = new Node<K, V>(null, key, value);
	size++;
	return null;
	}

	Node insertNode = new Node(node.parent, key, value);
	// 1. 4 - 结点分裂
	while (node.size == MAX_SIZE) {
	// 结点分裂
	node = nodeSplit(node, insertNode, i);

	// 1_1. 根结点分裂，更新 root
	if (node.parent == null) {
	root = node;
	size++;
	return null;
	}

	// 分裂的结点递归向上合并或再分裂
	insertNode = node;
	node = insertNode.parent;

	// 找出向上合并或再分裂的插入位置
	for (i = 0; i < node.size; i++) {
	int cmp = insertNode.keys[0].compareTo(node.keys[i]);
	if (cmp < 0) {
	break;
	} else if (cmp > 0 && i == node.size - 1) {
	i++;
	break;
	}
	}
	// 结点分裂新的结点，需要更新新的结点
	node.children[i] = insertNode;
	}

	// 2. 2 - 结点、3 - 结点直接合并
	nodeMerge(node, insertNode, i);
	size++;
	return null;
	}

# 删除

都是在叶子结点中删除（非叶子结点转化为叶子结点情形）
叶子结点元素多，则直接删除；不够则向兄弟借，兄弟不够向父辈借
树的高度降低只发生在：根结点为 2 - 结点，且孩子结点均为 2 - 结点时，合并结点导致的

# 删除情形

# 内部结点（非叶子结点）

找前驱或后继元素，转化为删除叶子结点。
删除情形一

# 叶子结点

富有 / 只有一个根结点：直接删除元素
贫穷但兄弟结点富有：向兄弟借元素
贫穷且兄弟结点也贫穷，但父结点富有：合并（fuse）
贫穷且兄弟结点、父结点都贫穷，均为 2 - 结点：
a. 合并然后递归向上再合并（直到根结点结束）

b. 合并然后向上向借元素

# 代码实现

# borrow

	private void borrow(Node node, int childIdx) {
	Node parent = node.parent;
	if (childIdx == 0) {
	Node rightSiblings = parent.children[childIdx + 1];
	moveElement(parent, 0, node, 0);
	moveChild(rightSiblings, 0, node, 1);
	node.size = 1;
	moveElement(rightSiblings, 0, parent, 0);
	moveElement(rightSiblings, 1, rightSiblings, 0, rightSiblings.size - 1);
	moveChild(rightSiblings, 1, rightSiblings, 0, rightSiblings.size);
	rightSiblings.size--;
	} else {
	Node leftSiblings = parent.children[childIdx - 1];
	moveElement(parent, childIdx - 1, node, 0);
	moveChild(node, 0, node, 1);
	moveChild(leftSiblings, leftSiblings.size, node, 0);
	node.size = 1;
	moveElement(leftSiblings, leftSiblings.size - 1, parent, childIdx - 1);
	leftSiblings.size--;
	}
	}

# fuse

	private void fuse(Node node, int childIdx) {
	Node parent = node.parent;
	if (childIdx == 0) {
	Node rightSiblings = parent.children[childIdx + 1];
	moveElement(parent, 0, node, 0);
	moveElement(rightSiblings, 0, node, 1);
	moveChild(rightSiblings, 0, node, 1, rightSiblings.size + 1);
	node.size = 2;

	parent.children[childIdx + 1] = null;
	if (parent.size > 1) {
	moveElement(parent, 1, parent, 0, parent.size - 1);
	moveChild(parent, 2, parent, 1, parent.size - 1);
	}

	parent.size--;
	rightSiblings.delete();
	} else {
	Node leftSiblings = parent.children[childIdx - 1];
	moveElement(parent, childIdx - 1, leftSiblings, leftSiblings.size);
	moveChild(node, 0, leftSiblings, leftSiblings.size + 1);
	leftSiblings.size = 2;

	parent.children[childIdx] = null;
	if (childIdx < parent.size) {
	moveElement(parent, childIdx, parent, childIdx - 1, parent.size - childIdx);
	moveChild(parent, childIdx + 1, parent, childIdx, parent.size - childIdx);
	}

	node.delete();
	parent.size--;
	}
	}

# isLeaf

	private boolean isLeaf(Node node) {
	if (node == null \|\| node.size == 0) {
	return true;
	}

	return node.children[0] == null;
	}

# getIndexInParent

Node 对象的方法：获取结点 node 在父结点 children 数组的下标。例如：node.getIndexInParent ()。用于删除结点操作中，需要根据 node 的位置进行调整。

	private int getIndexInParent() {
	for (int index = 0; index < parent.size + 1; index++) {
	if (parent.children[index] == this) {
	return index;
	}
	}
	// should not reach here.
	return -1;
	}

# underflow

结点元素不富有，需要借元素时，称为下溢出（underflow）。

下溢出的处理包括：删除情形③、④、⑤，即：向兄弟借、与父结点合并、向上合并 / 向上借元素。

	private void underflow(Node node) {
	while (true) {
	Node parent = node.parent;
	int childIdx = node.getIndexInParent();

	// 兄弟有的借
	if (childIdx == 0 && parent.children[childIdx + 1].size > 1) {
	borrow(node, childIdx);
	return;
	} else if (childIdx > 0 && parent.children[childIdx - 1].size > 1) {
	borrow(node, childIdx);
	return;
	}
	// 兄弟没得借但父亲有的借：合并
	if (parent.size > 1) {
	fuse(node, childIdx);
	return;
	}
	// 兄弟父亲都没得借：合并，然后向上递归
	// parent.size == 1
	fuse(node, childIdx);
	// cascade up the tree
	node = parent;

	// 根结点降低树高
	if (node == root) {
	root = node.children[0];
	root.parent = null;
	node.delete();
	return;
	}
	}
	}

# remove

getNode 方法参见：查找

	public V remove(K key) {
	if (key == null) { // key invalid
	throw new IllegalArgumentException("key can not be null.");
	}

	Pair<Integer, Node> pair = getNode(key);
	if (pair == null) { // key not found
	return null;
	}

	Node delElemInNode = pair.value;
	int delElemIdx = pair.key;

	V returnValue = (V) delElemInNode.values[delElemIdx];

	// 1. 非叶子结点情形
	if (!isLeaf(delElemInNode)) {
	// 获取后驱结点：右兄弟结点的最左子树
	Node successor = delElemInNode.children[delElemIdx + 1];
	// 沿着最左子树遍历
	while (!isLeaf(successor)) { // successor.children[0] != null
	successor = successor.children[0];
	}

	// swap
	moveElement(successor, 0, delElemInNode, delElemIdx);
	// 转化为删除叶子结点情形
	delElemInNode = successor;
	delElemIdx = 0;
	}

	//------------ 叶子结点情形 ------------

	// 2. 结点富有 [2 - 结点、3 - 结点] 或仅有根结点一个结点：直接移除元素
	if (delElemInNode.size > 1 \|\| delElemInNode == root) {
	// 删除元素
	moveElement(delElemInNode, delElemIdx + 1, delElemInNode, delElemIdx,
	delElemInNode.size - delElemIdx - 1);
	delElemInNode.size--;
	// tree empty
	if (delElemInNode.size == 0) {
	root = null;
	delElemInNode.delete();
	}
	size--;
	return returnValue;
	}

	// 3. 结点贫穷：借元素或合并结点
	underflow(delElemInNode);

	size--;
	return returnValue;
	}

# 查找

	// 用于 return 返回 2 个值时的包装，
	// 例如：因为结点包含多个元素、子结点，需要获取元素值、以及下标位置
	private static class Pair<K, V> {
	K key;
	V value;

	public Pair(K key, V value) {
	this.key = key;
	this.value = value;
	}
	}

	// 根据 key 获取值
	public V get(K key) {
	if (key == null) {
	throw new IllegalArgumentException("key can not be null.");
	}

	// 元素下标，结点
	Pair<Integer, Node> pair = getNode(key);
	return pair == null ? null : (V) pair.value.values[pair.key];
	}

	// 返回结点，以及元素在结点内的下标
	private Pair<Integer, Node> getNode(K key) {
	Node p = root;
	// 查找
	while (p != null) {
	for (int i = 0; i < p.size; i++) {
	int cmp = key.compareTo((K) p.keys[i]);
	if (cmp < 0) {
	p = p.children[i];
	break;
	} else if (cmp > 0 && i == p.size - 1) {
	p = p.children[i + 1];
	break;
	} else if (cmp == 0) {
	// 返回结点，以及元素在结点内的下标
	return new Pair<>(i, p);
	}
	}
	}
	// not found
	return null;
	}

# 空间复杂度

平均、最差： $O(n)$

# 时间复杂度

搜索、插入、删除，平均和最差都是： $O(\log n)$

# 缺点

代码实现复杂，需要考虑：结点的数据结构、操作结点时需要考虑数组的下标位置、元素和结点在数组中移动等。
需要使用多种数据结构：结点之间的关系 [链表 + 数组]、结点内的元素 [数组]。

# 定义

# 结点类型

# 插入

# 插入情形

# 代码实现

# 类结构

# 结点合并

# 结点分裂

# 元素迁移，孩子结点迁移

# 插入

# 删除

# 删除情形

# 内部结点（非叶子结点）

# 叶子结点

# 代码实现

# borrow

# fuse

# isLeaf

# getIndexInParent

# underflow

# remove

# 查找

# 空间复杂度

# 时间复杂度

# 缺点

二叉搜索树（Binary Search Tree）

B+树

B⁺树