ARTS （第43周）

隔了许久，最近将之前理解的B树实现了出来。发现依然是积累的越多，再去理解会更容易。

Algorithm 算法

红黑树

最近又再度实现了红黑树

package algorithm.senior.redblacktree2;

import jdk8test.RedBlackTree;

/**
 * 红黑树基础特征
 * 
 * 1.节点是红色或黑色。 2.根是黑色。 3.所有叶子都是黑色（NIL节点也是当作黑色）。
 * 4.每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
 * 5.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（简称黑高）。
 * 
 * @author la-huan
 *
 */
public class RedBlackTree2 {
	public static void main(String[] args) {
		while (true) {
			test();
		}
	}

	private static void test() {
		RedBlackTree2 t2 = new RedBlackTree2();
		RedBlackTree t = new RedBlackTree();
		int size = 111;
		for (int i = 0; i < size; i++) {
			int num = (int) (Math.random() * size);
			// num=arr[i];
			System.out.println(">" + num);
			t.add(num);
			t2.add(num);
		}
		//
		int num = (int) (Math.random() * size);
		// num=arr[i];
		System.out.println("<" + num);
		t.remove(num);
		t2.remove(num);

		System.out.println(t);
		System.out.println(t2);
		if (t.toString() == t2.toString()) {

			System.exit(1);
		}
	}

	// 静态常量 红
	private static final Color RED = Color.Red;
	// 静态常量 黑
	private static final Color BLACK = Color.Black;
	// 根节点
	private Node root;
	// 大小
	private int size;

	public void remove(int v) {
		Node n = find(v);
		if (n == null) {
			return;
		}
		size--;

		// 左右子树都有的时候，改成删除后继节点
		if (n.left != null && n.right != null) {
			Node s = findSuccessor(n);
			// 将后继节点的值赋值给当前节点
			n.val = s.val;
			// 替换删除节点为后继节点
			n = s;
		}
		Node p = n.parent;
		// 获取单子树
		Node c = (n.left != null ? n.left : n.right);
		if (c != null) {
			// 单子树的情况
			c.parent = p;
			// 直接替代
			if (p != null) {
				if (isLeft(n)) {
					p.left = c;
				} else {
					p.right = c;
				}
			} else {
				root = c;
			}
			if (getColor(n) == BLACK) {
				fix4Add(c);//
			}
		} else if (p == null) {
			// 删除节点无父节点也无子节点
			root = null;

		} else {
			// 叶子节点
			if (getColor(n) == BLACK) {
				fix4Remove(n);
			}
			if (isLeft(n)) {
				p.left = null;
			} else {
				p.right = null;
			}
			n.parent = null;

		}
	}

	/**
	 * 删除后的调整 （又或者说入参节点的路线上缺了一个黑色的节点 需要调整）
	 * 
	 * 情况1：待删除节点D的兄弟节点S为红色
	 * 父亲节点和兄弟节点的颜色互换，也就是p变成红色，S变成黑色，然后将P树进行右旋操作（兄弟节点是左子树就左旋），这时候变成了情况4
	 * 情况2：兄弟节点S为黑色，且远侄子节点为红色。（左右子树不同判断）
	 * 调整过程为，将P和S的颜色对调，然后对P树进行右旋的操作，最后把远侄子节点变成黑色，并删除D即可。
	 * 情况3：兄弟节点S为黑色，远侄子节点为黑色，近侄子节点为红色（左右子树不同判断）
	 * D为左孩子的情况，此时近侄子节点为S的左孩子，这时候将S右旋，并将S和SL的颜色互换，这个时候就变成了情况2。
	 * 情况4：父亲节p为红色，兄弟节点和兄弟节点的两个孩子（只能是NULL节点）都为黑色的情况。
	 * 将父亲节点P改成黑色，将兄弟节点S改成红色，然后删除D即可
	 * 情况5：父亲节点p，兄弟节点s和兄弟节点的两个孩子（只能为NULL节点）都为黑色的情况。
	 * 方法是将兄弟节点S的颜色改成红色，这样删除D后P的左右两支的黑节点数就相等了，但是经过P的路径上的黑色节点数会少1，
	 * 这个时候，我们再以P为起始点，继续根据情况进行平衡操作（这句话的意思就是把P当成D（只是不要再删除P了），再看是那种情况，再进行对应的调整，
	 * 这样一直向上，直到新的起始点为根节点）
	 * 
	 * 参考自 https://www.cnblogs.com/qingergege/p/7351659.html
	 * 
	 * @param node
	 */
	private void fix4Remove(Node n) {
		// 兄弟节点
		while (true) {
			Node s = getSibling(n);
			Node p = n.parent;
			if (isLeft(n)) {
				// 左树的情况

				if (getColor(s) == RED) {
					// 情况1 并且兄弟是红 父节点一定是黑
					// 关注节点是黑 兄弟节点是红
					changeColor(s, p);
					rotateLeft(p);
					// 重置指针
					s = getSibling(n);
					// p = n.parent;
				}
				// 这里的情况 兄弟节点一定是黑的

				// 情况4、5的大分支
				if (getColor(s.left) == BLACK && getColor(s.right) == BLACK) {

					if (getColor(p) == RED) {
						// 情况4
						// 父亲节p为红色，兄弟节点和兄弟节点的两个孩子（只能是NULL节点）都为黑色
						p.color = BLACK;
						s.color = RED;
						return;// 可以停止了
					} else {
						// 情况5
						// 父亲节点p，兄弟节点s和兄弟节点的两个孩子（只能为NULL节点）都为黑色
						s.color = RED;
						n = p;// 继续迭代（少了一个黑的）
					}

				} else {

					if (getColor(s.right) == BLACK) {
						// 情况3，远侄子节点为黑色 ，则近侄子节点为红色 进入情况3的判断
						changeColor(s, s.left);
						rotateRight(s);
						// 重置指针
						s = getSibling(n);
						// 这时候已经调整成了情况2
					}
					// 情况2
					s.color = p.color;
					p.color = BLACK;
					s.right.color = BLACK;
					rotateLeft(p);
					return;
				}

			} else {
				// 右树的情况
				if (getColor(s) == RED) {
					// 情况1 并且兄弟是红 父节点一定是黑
					// 关注节点是黑 兄弟节点是红
					changeColor(s, p);
					rotateRight(p);
					// 重置指针
					s = getSibling(n);
					// p = n.parent;
				}
				// 这里的情况 兄弟节点一定是黑的

				// 情况4、5的大分支
				if (getColor(s.left) == BLACK && getColor(s.right) == BLACK) {

					if (getColor(p) == RED) {
						// 情况4
						// 父亲节p为红色，兄弟节点和兄弟节点的两个孩子（只能是NULL节点）都为黑色
						p.color = BLACK;
						s.color = RED;
						return;// 可以停止了
					} else {
						// 情况5
						// 父亲节点p，兄弟节点s和兄弟节点的两个孩子（只能为NULL节点）都为黑色
						s.color = RED;
						n = p;// 继续迭代（少了一个黑的）
					}

				} else {

					if (getColor(s.left) == BLACK) {
						// 情况3 ，远侄子节点为黑色 ，则近侄子节点为红色 进入情况3的判断
						changeColor(s, s.right);
						rotateLeft(s);
						// 重置指针
						s = getSibling(n);
						// 这时候已经调整成了情况2
					}
					// 情况2
					s.color = p.color;
					p.color = BLACK;
					s.left.color = BLACK;
					rotateRight(p);
					return;
				}
			}
		}

	}

	/**
	 * 新增
	 * 
	 * @param v
	 */
	public void add(int v) {
		if (find(v) != null) {
			// 重复数据无视
			return;
		}
		size++;
		// 根节点
		if (root == null) {
			Node n = new Node(v, BLACK);
			root = n;
			return;
		}
		// 非根节点
		// 1、找到位置。2、调整
		Node p = findAddParent(v);
		// 应该放左节点还是右节点
		// PS:如果JAVA能支持多返回值的写法 这里可以直接在 findAddParent
		// 方法里返回。又或者可以定义一个结构表示应该插入节点和应插入位置。
		Node node = new Node(v);
		node.parent = p;
		if (p.val > v) {
			p.left = node;
		} else {
			p.right = node;
		}
		// 调整
		fix4Add(node);
	}

	/**
	 * 新增后的调整 不是三点一线的转成三点一线 然后根据情况
	 * 
	 * @param node
	 */
	private void fix4Add(Node n) {
		while (true) {
			// 到了根节点 直接置黑
			if (n.parent == null) {
				root = n;
				root.color = BLACK;
				return;
			} else if (getColor(n.parent) == BLACK) {
				// 父节点是非空黑色的 新节点是红色的 不需要再调整
				return;
			} else {// 父节点是红色的
				Node u = getUncle(n);
				Node p = n.parent;// 父节点
				Node g = p.parent;// 祖父节点
				// 如果叔节点也是红的
				if (getColor(u) == RED) {
					// 父节点、叔叔节点变黑。祖父节点变红。判断祖父节点的情况
					changeColor(p, u, g);
					// 祖父节点变红，需要重新判断
					n = g;
				} else {
					// 父节点是红的 新节点也是红的
					if (isLeft(p)) {
						// 左节点的分支
						if (isRight(n)) {
							// 需要旋转
							rotateLeft(p);
							// 重置指针
							n = p;
							p = n.parent;
							// g = p.parent;
						}
						//
						rotateRight(g);
						changeColor(p, g);
						return;
					} else {
						// 右节点的分支

						if (isLeft(n)) {
							// 需要旋转
							rotateRight(p);
							// 重置指针
							n = p;
							p = n.parent;
							// g = p.parent;
						}
						//
						rotateLeft(g);
						changeColor(p, g);
						return;
					}
				}
			}
		}
	}

	/**
	 * 是否存在
	 * 
	 * @param v
	 * @return
	 */
	public boolean exist(int v) {
		return find(v) != null;
	}

	/**
	 * 颜色
	 * 
	 * @author la-huan
	 */
	private enum Color {
		Black, Red;
	}

	/**
	 * 节点
	 * 
	 * @author la-huan
	 */
	private class Node {
		// 颜色 ：默认红色
		private Color color;
		// 值
		private int val;
		// 父节点
		private Node parent;
		// 左节点
		private Node left;
		// 右节点
		private Node right;

		private Node() {
			// 默认红
			color = RED;
		}

		private Node(int v) {
			val = v;
			// 默认红
			color = RED;
		}

		private Node(int v, Color c) {
			val = v;
			color = c;
		}

		@Override
		public String toString() {
			return "{'color':'" + color + "', 'val':'" + val + "', 'left':" + left + ", 'right':" + right + "}";
		}
	}

	/**
	 * 转换颜色
	 * 
	 * @author la-huan
	 * @param n
	 */
	private void changeColor(Node... ns) {
		for (Node n : ns) {
			// 考虑之后，应该不需要加非空判断。若使用合理，不存在入参为空的时候
			// if (n != null) {
			if (n.color == BLACK) {
				n.color = RED;
			} else {
				n.color = BLACK;
			}
			// }
		}
	}

	/**
	 * 判断当前节点是否是父节点的左节点 这里不考虑父节点为空的情况。只有根节点没有父节点，根节点的判断做另外判断
	 */
	private boolean isLeft(Node n) {
		Node parent = n.parent;
		return parent.left == n;
	}

	/**
	 * 判断当前节点是否是父节点的右节点 这里不考虑父节点为空的情况。只有根节点没有父节点，根节点的判断做另外判断
	 */
	private boolean isRight(Node n) {
		Node parent = n.parent;
		return parent.right == n;
	}

	/**
	 * 获取叔节点 这里不考虑父节点为空的情况。只有根节点没有父节点，根节点的判断做另外判断
	 */
	private Node getUncle(Node n) {
		Node p = n.parent;
		Node g = p.parent;
		if (isLeft(p)) {
			return g.right;
		}
		return g.left;

	}

	/**
	 * 左旋 , 需要控制三对指针 //1、右节点替代当前节点 //2、当前节点的右节点变成原本右节点的左节点 //3、当前节点和变成右节点的左节点
	 * 
	 * @param n
	 */
	private void rotateLeft(Node n) {
		Node r = n.right;// 右子
		Node p = n.parent;// 父
		// 指针1
		r.parent = p;
		if (p == null) {
			root = r;
		} else if (isLeft(n)) {
			p.left = r;
		} else {
			p.right = r;
		}

		// 指针2
		n.right = r.left;
		if (n.right != null)
			n.right.parent = n;
		// 指针3
		// 不做r的非空判断，不考虑没有右节点时候的左旋，没有节点可旋
		r.left = n;
		n.parent = r;

	}

	/**
	 * 右旋, 需要控制三对指针 //1、左节点替代当前节点 //2、当前节点的左节点变成原本左节点的右节点 //3、当前节点和变成左节点的右节点
	 * 
	 * @param n
	 */
	private void rotateRight(Node n) {
		Node l = n.left;
		Node p = n.parent;
		// 指针1
		l.parent = p;
		if (p == null) {
			root = l;
		} else if (isRight(n)) {
			p.right = l;
		} else {
			p.left = l;
		}
		// 指针2
		n.left = l.right;
		if (n.left != null)
			n.left.parent = n;
		// 指针3
		n.parent = l;
		l.right = n;
	}

	/**
	 * 获取节点颜色
	 * 
	 * @author la-huan
	 * @param v
	 */
	private Color getColor(Node n) {
		if (n == null)// 空的叶子节点当黑（NIL）
			return BLACK;
		return n.color;
	};

	/**
	 * 根据值查找节点
	 * 
	 * @param v
	 * @return
	 */
	private Node find(int v) {
		Node cur = root;
		// 二分查找
		while (cur != null) {
			if (v > cur.val) {
				cur = cur.right;
			} else if (v < cur.val) {
				cur = cur.left;
			} else {
				return cur;
			}

		}
		return null;
	}

	/**
	 * 寻找继承节点
	 * 
	 * @param n
	 * @return
	 */
	private Node findSuccessor(Node n) {
		if (n == null || n.right == null) {
			return null;
		}
		n = n.right;
		while (n.left != null) {
			n = n.left;
		}
		return n;
	}

	/**
	 * 获取兄弟节点
	 * 
	 * @param n
	 * @return
	 */
	private Node getSibling(Node n) {
		Node p = n.parent;
		if (p != null) {
			if (isLeft(n)) {
				return p.right;
			}
			return p.left;
		}
		return null;

	}

	/**
	 * 根据值查找节点
	 * 
	 * @param v
	 * @return
	 */
	private Node findAddParent(int v) {
		Node cur = root;
		// 二分查找
		while (true) {
			if (v > cur.val) {
				if (cur.right != null) {
					cur = cur.right;
				} else {
					return cur;//
				}
			} else if (v < cur.val) {
				if (cur.left != null) {
					cur = cur.left;
				} else {
					return cur;
				}
			} else {
				// 其实这里是不应该出现的情况，程序走到这里代表结构和算法有误
				throw new RuntimeException("已存在的节点");
			}

		}
		// throw new RuntimeException("未找到应该在的位置");
	}

	/**
	 * 大小
	 * 
	 * @return
	 */
	public int getSize() {
		return size;
	}

	@Override
	public String toString() {
		if (root == null)
			return null;
		return root.toString();
	}
}

B树

实现了简易的B树

package algorithm.senior.btree;

import java.util.Arrays;
import com.alibaba.fastjson.JSON;

/**
 * B树 简化版。 不做键值对，只保存int类型的key
 * 
 * 如果想要改成键值对的 将节点的key数组的类型改成键值对的类型,以及键值对的键需要实现Comparable
 * 
 * 现在是通过数组保存节点和关键字,如果通过集合来保存,会容易实现很多
 * 
 * @author la-huan
 */
public class BTree {

	public static void main(String[] args) {
		while (true) {
			System.out.println("****************");
			test1();
		}
	}

	public static void test1() {
		int s = 5555;
		boolean[] b = new boolean[s];
		BTree t = new BTree();
		int max = 100;
		for (int i = 0; i < max; i++) {
			int m2 = (int) (Math.random() * s / 2);
			for (int j = 0; j < m2; j++) {

				int v = (int) (Math.random() * s);
				t.addPrint(v);
				b[v] = true;
			}
			m2 = (int) (Math.random() * s / 2);
			for (int j = 0; j < m2; j++) {

				int v = (int) (Math.random() * s);
				t.removePrint(v);
				b[v] = false;
			}
			System.out.println("=================");
			for (int j = 0; j < b.length; j++) {
				if (!b[j] == t.exist(j)) {
					System.out.println("error:" + i);
					System.out.println("t:" + t.exist(j));
					System.out.println(t);
					System.out.println(Arrays.toString(b));
					System.exit(0);
				}
			}
			System.out.println("success");
		}

	}
	/**
	 * 新增和输出
	 */
	public void addPrint(int v) {
		System.out.println("add:" + v);
		add(v);
		System.out.println(this);
	}
	/**
	 * 删除和输出
	 */
	public void removePrint(int v) {
		System.out.println("remove:" + v);
		remove(v);
		System.out.println(this);
	}
	
	BTreeNode root;// 跟
	int size = 0;// 大小
	int height = 0;// 高度
	public BTree() {
		root = new BTreeNode();
		root.isLeaf = true;
		height = 1;

	}
	
	
	
	/**
	 * 删除
	 */
	public void remove(int v) {
		// 查找节点
		BTreeNode n = root;
		int idx = -1;
		out: while (!n.isLeaf) {
			int i = 0;
			for (; i < n.kSize; i++) {
				if (v < n.key[i]) {
					break;
				}
				if (v == n.key[i]) {
					// 找到节点
					idx = i;
					break out;// 跳出外层循环
				}
			}
			n = n.children[i];
		}
		// 叶子节点获取索引
		if (n.isLeaf) {
			int i = 0;
			for (; i < n.kSize; i++) {
				if (v == n.key[i]) {
					idx = i;
					break;
				}
			}
		}
		// System.out.println(idx + ":" + n);
		if (idx == -1) {
			// 未找到节点
			return;
		}
		// 非叶子节点转变为 寻找后续叶子节点，删除后续叶子节点
		if (!n.isLeaf) {
			BTreeNode successor = findSuccessor(n, idx);
			n.key[idx] = successor.key[0];
			// 重建指针
			n = successor;
			idx = 0;
		}

		// 删除叶子节点
		n.removeLeaf(idx);
	}

	/**
	 * 寻找替代的后继节点
	 * 
	 * @param n
	 * @param idx
	 * @return
	 */
	private BTreeNode findSuccessor(BTreeNode n, int idx) {
		// 向右找
		BTreeNode c = n.children[idx + 1];
		// 找到叶子节点为止
		while (!c.isLeaf) {
			// 向左找
			c = c.children[0];
		}
		return c;
	}

	/**
	 * 新增
	 */
	public void add(int... vs) {
		for (int v : vs) {
			add(v);
		}
	}

	/**
	 * 新增
	 * 
	 * @param v
	 */
	public void add(int v) {
		if (size == 0) {
			root.add(v);
			size++;
			return;
		}
		// 获取位置
		BTreeNode n = root;
		while (!n.isLeaf) {
			int i = 0;
			for (; i < n.kSize; i++) {
				if (v < n.key[i]) {
					break;
				}
				if (v == n.key[i]) {
					// 重复不考虑
					return;
				}
			}
			n = n.children[i];
		}
		// 不存在继续
		if (!exist(n, v)) {
			n.add(v);
			size++;
		}
	}

	/**
	 * 判断是否存在 即查找
	 * 
	 * @param v
	 * @return
	 */
	public boolean exist(int v) {
		BTreeNode n = root;
		while (!n.isLeaf) {
			int i = 0;
			for (; i < n.kSize; i++) {
				if (v < n.key[i]) {
					break;
				}
				if (v == n.key[i]) {
					return true;
				}
			}
			n = n.children[i];
		}
		return exist(n, v);
	}

	/**
	 * 判断节点里是否有某个值
	 * 
	 * @param n
	 * @param v
	 * @return
	 */
	private boolean exist(BTreeNode n, int v) {
		if (n == null)
			return false;
		for (int i = 0; i < n.kSize; i++) {
			if (n.key[i] == v) {
				return true;
			}
		}
		return false;
	}

	@Override
	public String toString() {
		String jsonString = JSON.toJSONString(root);
		return jsonString;
	}

	
	// 节点
	class BTreeNode {
		int m = 5;// m阶树 5阶树
		int kSize = 0;// 当前节点key数量
		int cSize = 0;// 子节点数量
		// int[] key = new int[m - 1];// 关键字 考虑删除之后合并，有某个节点有m-1个节点的情况
		int[] key = new int[m];// 关键字
		boolean isLeaf = false;// 叶子节点
		BTreeNode parent;// 父节点
		BTreeNode[] children = new BTreeNode[m + 1];// 子节点

		public int[] getKey() {
			int[] arr = new int[kSize];
			System.arraycopy(key, 0, arr, 0, kSize);
			return arr;
		}

		public boolean isLeaf() {
			return isLeaf;
		}
		/**
		 * 删除叶子节点
		 * @param idx
		 */
		public void removeLeaf(int idx) {
			if (!isLeaf) {
				throw new RuntimeException("当前删除节点非叶子节点,需要寻找后继节点删除");
			}
			// 删除，关键字左移即可
			System.arraycopy(key, idx + 1, key, idx, kSize - idx - 1);
			kSize--;
			// 判断是否需要调整
			if (kSize < m / 2) {
				fix();
			}
		}

		/**
		 * 删除调整
		 */
		private void fix() {
			if (this == root)
				return;
			int idx = getIdx();
			if (idx != 0 && parent.children[idx - 1].kSize > (m / 2)) {
				// 向左节点借
				// 判断左节点 当前节点非首个节点 并且左节点的size 大于 m/2
				// 左节点删除最右边的值 父节点替换值为左节点删除的值 当前节点最左边增加父节点原值
				BTreeNode s = parent.children[idx - 1];
				int v = s.key[--s.kSize];
				add(parent.key[idx - 1], 0);
				parent.key[idx - 1] = v;
				// 如果有子节点，也需要借一个来
				if (!isLeaf) {
					s.children[--s.cSize].parent = this;
					addChild(s.children[s.cSize], 0);
				}

			} else if (idx != parent.cSize - 1 && parent.children[idx + 1].kSize > (m / 2)) {
				// 向右节点借
				// 判断左节点 当前节点非尾节点 并且右节点的size 大于 m/2
				// 右节点删除最左边的值 父节点替换值为右节点删除的值 当前节点最右边增加父节点原值
				BTreeNode s = parent.children[idx + 1];
				int v = s.key[0];
				// 关键字左移
				System.arraycopy(s.key, 1, s.key, 0, --s.kSize);
				add(parent.key[idx], kSize);
				parent.key[idx] = v;
				// 如果有子节点，也需要借一个来
				if (!isLeaf) {
					s.children[0].parent = this;
					addChild(s.children[0], cSize);
					System.arraycopy(s.children, 1, s.children, 0, --s.cSize);
				}
			} else {
				// 左右都不够借
				// 向父节点借值和兄弟节点合并
				if (idx != 0) {
					// 左节点合并
					BTreeNode s = parent.children[idx - 1];
					merge(s, this, idx - 1);
					if (parent == root && parent.kSize == 0) {
						// 父节点空了 树高度降低
						root = s;
						s.parent = null;
						height--;
						return;
					}
				} else if (idx != parent.cSize - 1) {
					// 右节点合并
					BTreeNode s = parent.children[idx + 1];
					merge(this, s, idx);
					if (parent == root && parent.kSize == 0) {
						// 父节点空了 树高度降低
						root = this;
						this.parent = null;
						height--;
						return;
					}
				} else {
					// 逻辑错误情况
					throw new RuntimeException("删除后的调整出错 -->BTreeNode.fixLeaf()");
				}
			}

			// 调整逐级向上
			if (parent != root && parent.kSize < m / 2) {
				parent.fix();
			}
		}

		/**
		 * 合并
		 * 
		 * @param l
		 * @param r
		 * @param idx
		 */
		private void merge(BTreeNode l, BTreeNode r, int lIdx) {
			BTreeNode parent = l.parent;
			int v = parent.key[lIdx];
			l.add(v, l.kSize);// 增加父节点的值
			//
			for (int i = 0; i < r.kSize; i++) {
				v = r.key[i];
				l.add(v, l.kSize);// 当前节点的值
			}
			if (!l.isLeaf) {
				// 非叶子节点考虑子节点转移
				for (int i = 0; i < r.cSize; i++) {
					r.children[i].parent = l;
					l.addChild(r.children[i]);
				}
			}
			// 父节点删除key的索引
			int parentKeyDel = lIdx;
			// 关键字左移
			System.arraycopy(parent.key, parentKeyDel + 1, parent.key, parentKeyDel, parent.kSize - 1 - parentKeyDel);
			parent.kSize--;
			// 父节点删除child的索引
			int parentChildDel = lIdx + 1;
			// 子节点左移
			System.arraycopy(parent.children, parentChildDel + 1, parent.children, parentChildDel,
					parent.cSize - 1 - parentChildDel);
			parent.cSize--;
		}

		public BTreeNode[] getChildren() {
			BTreeNode[] arr = new BTreeNode[cSize];
			System.arraycopy(children, 0, arr, 0, cSize);
			return arr;
		}

		@Override
		public String toString() {
			return "{m=" + m + ", kSize=" + kSize + ", cSize=" + cSize + ", key=" + Arrays.toString(key) + ", isLeaf="
					+ isLeaf + ", children=" + Arrays.toString(children) + "}";
		}

		/**
		 * 新增
		 * 
		 * @param v
		 */
		private void add(int v) {
			int i = 0;
			for (; i < kSize; i++) {
				if (v < key[i]) {
					break;
				}
			}
			System.arraycopy(key, i, key, i + 1, kSize - i);
			key[i] = v;
			kSize++;
			if (kSize >= m - 1) {
				// 分裂
				split();
			}
		}

		/**
		 * 新增
		 * 
		 * @param v
		 */
		private void add(int v, int idx) {
			System.arraycopy(key, idx, key, idx + 1, kSize - idx);
			key[idx] = v;
			kSize++;
		}

		/**
		 * 新增子节点
		 * 
		 * @param n
		 */
		private void addChild(BTreeNode n) {
			children[cSize++] = n;
		}

		/**
		 * 新增子节点
		 * 
		 * @param n
		 */
		private void addChild(BTreeNode n, int idx) {
			System.arraycopy(children, idx, children, idx + 1, cSize - idx);
			children[idx] = n;
			cSize++;
		}

		/**
		 * 获取当前节点在父级节点里的索引 错误返回-1
		 * 
		 * @return
		 */
		private int getIdx() {
			if (parent == null) {
				throw new RuntimeException("没有父级");
			}
			for (int i = 0; i < parent.cSize; i++) {
				if (parent.children[i] == this) {
					return i;
				}
			}
			throw new RuntimeException("未找到索引");
		}

		/**
		 * 分裂
		 */
		private void split() {
			// 将节点分成中间节点 中间节点前（左节点） 中间节点后（右节点）
			// 中间节点上升成父节点 左右节点分裂
			int mid = kSize / 2;// key[mid]待会插入到父节点

			BTreeNode next = new BTreeNode();
			next.parent = parent;
			next.isLeaf = this.isLeaf;
			// 关键字分裂
			for (int i = mid + 1; i < kSize; i++) {
				next.add(key[i]);
			}
			this.kSize = mid;
			// 子节点分裂
			if (cSize != 0) {
				// 是否有子节点 用是否叶子节点判断也可以
				// 子节点分裂
				for (int i = mid + 1; i < cSize; i++) {
					children[i].parent = next;
					next.addChild(children[i]);
				}
				cSize = kSize + 1;
			}

			// 父节点新增
			// 根节点的情况
			if (parent == null) {
				height++;// 高度增加
				root = new BTreeNode();
				parent = root;
				next.parent = root;
				// 关键字
				root.add(key[mid]);
				// 子节点
				root.addChild(this);
				root.addChild(next);
				return;
			}

			// 找到当前节点在父节点的索引
			int idx = getIdx();
			parent.add(key[mid], idx);
			parent.addChild(next, idx + 1);

			// 递归父节点判断
			if (parent.kSize >= m - 1) {
				// 分裂
				parent.split();
			}
		}
	}

}

Review 英文文章

https://vuejs.org/v2/guide/components-custom-events.html

vue的 事件

Tip 技巧

JDBC

https://blog.csdn.net/qq_22172133/article/details/81266048 Java中JDBC的使用详解。

因为最近项目的原因可能需要使用JDBC，就又回顾了下JDBC，感觉完全不一样了。

正则表达式

《java编程的逻辑》第25章

里面还有很多演示和案例，在有需要的时候也可以打开这本书的相关章节进行编写正则表达式。

Share 分享

https://blog.csdn.net/weixin_38229356/article/details/80739307 不可见字符的坑

https://blog.csdn.net/lantian_123/article/details/103172069 so easy！ 10行代码写个”狗屁不通”文章生成器

https://www.jianshu.com/p/2cccb07d9a4e jieba分词详解（python的插件，非python的可以了解看看原理）