面试让我手写红黑树( 六 ) _红黑树

基于传递进来的节点，将节点的左右孩子创建新节点，如果这个孩子节点还有分支节点，则一并更新。

2.3 建立新连接

private void replaceChild(Node_2_3 parent, Node_2_3 oldChild, Node_2_3 child01, Node_2_3 child02) { if (oldChild == parent.children[0]) { parent.children[3] = parent.children[2]; parent.children[2] = parent.children[1]; parent.children[1] = child02; parent.children[0] = child01; } else if (oldChild == parent.children[1]) { parent.children[3] = parent.children[2]; parent.children[2] = child02; parent.children[1] = child01; } else { parent.children[3] = child02; parent.children[2] = child01; } }

建立新连接需要判断这个节点 oldChild 是父节点的左、中、右，之后进行依次的更换。
如拆分节点的介绍图中，用到的就是 parent.children[1] = child02;parent.children[0] = child01; 两步操作过程。

2.3 新增节点

public void insert(int e) { // 记录元素 elementList.add(e); // 插入元素 if (root == null) { root = new Node_2_3(e); } else { root = insert(e, root); if (root.number == 3) { root = split(root, null); } } } private Node_2_3 insert(int e, Node_2_3 parent) { if (parent.isLeaf()) { parent.insert(e); return parent; } Node_2_3 child = null; if (parent.number == 1) { if (e < parent.getMinItem()) { child = insert(e, parent.getLeft()); } else { child = insert(e, parent.getMiddle()); } } else { if (e < parent.getMinItem()) { child = insert(e, parent.getLeft()); } else if (e > parent.getMiddleItem()) { child = insert(e, parent.getRight()); } else { child = insert(e, parent.getMiddle()); } } if (child.number == 3) { return this.split(child, parent); } return parent; }

新增节点的过程就比较简单了，一种是使用递归找到可以插入的位置，另外一种就是 where 循环。我们再BST、AVL两种数据结构种都是用了 where 循环。
在2-3树中 insert 方法递归到对应的插入位置后，开始插入元素。当插入元素结束后判断这个节点是否已经达到了3个节点，如果是则进行拆分。拆分就调用了上面的步骤

3. 2-3树结构测试
为了让读者更好的理解2-3树的结构，小傅哥在程序的控制台打印了插入的过程。网上没有2-3树在线的动画演示，如果读者看到也可以留言给小傅哥

@Test public void test_insert_incr() { Tree_2_3 tree = new Tree_2_3(); for (int i = 1; i <= 10; i++) { tree.insert(i); System.out.println(tree); } }

顺序插入10个节点，如果这是一颗BST树，它将会退化成链表。那么我们使用自平衡的2-3树，来看看它的插入效果。

测试效果

输入节点(1个)：1 [1] 输入节点(2个)：1,2 [1,2] 输入节点(3个)：1,2,3 /----- [3] [2] ----- [1] 输入节点(4个)：1,2,3,4 /----- [3,4] [2] ----- [1] 输入节点(5个)：1,2,3,4,5 /----- [5] [2,4]---- [3] ----- [1] 输入节点(6个)：1,2,3,4,5,6 /----- [5,6] [2,4]---- [3] ----- [1] 输入节点(7个)：1,2,3,4,5,6,7 /----- [7] /----- [6] | ----- [5] [4] | /----- [3] ----- [2] ----- [1] 输入节点(8个)：1,2,3,4,5,6,7,8 /----- [7,8] /----- [6] | ----- [5] [4] | /----- [3] ----- [2] ----- [1] 输入节点(9个)：1,2,3,4,5,6,7,8,9 /----- [9] /----- [6,8]---- [7] | ----- [5] [4] | /----- [3] ----- [2] ----- [1] 输入节点(10个)：1,2,3,4,5,6,7,8,9,10 /----- [9,10] /----- [6,8]---- [7] | ----- [5] [4] | /----- [3] ----- [2] ----- [1] Process finished with exit code 0

有了这样的数据结构示意，是不是再来看2-3树就非常清晰了。—— 我说过，理科生 + 技术，不要只抛理论，要看效果的！东西到手了，能拿捏了，再补充理论。

五、红黑树
红黑树的历史
红黑树（Red Black Tree）是一种自平衡二叉查找树，于 1972 年由 Rudolf Bayer 发明的对称二叉B树演化而来，并以2-3-4树、2-3树流行。最终在 1978 年由 Leonidas J. Guibas 和 Robert Sedgewick 从对称二叉 B 树中推导出红黑树。PS：之所以选择“红色”，是因为它是作者在Xerox PARC工作时可用的彩色激光打印机产生的最好看的颜色。
1. 红黑树数据结构
建立在 BST 二叉搜索树的基础上，AVL、2-3树、红黑树都是自平衡二叉树（统称B-树）。但相比于AVL树，高度平衡所带来的时间复杂度，红黑树对平衡的控制要宽松一些，红黑树只需要保证黑色节点平衡即可。也正因红黑树在插入和删除时不需要太多的平衡操作，也让它成为；Java中HashMap的元素碰撞后的转换、linux的CFS进行调度算法、多路复用技术的Epoll等各类底层的数据结构实现。
但红黑树并不是一个那么容易理解的知识点，甚至很多资料都只是给出红黑树的理论，但为什么要染色、为什么要左旋、为什么还要左旋接右旋。这样的知识点本就不应该是考死记硬背来学习的，这根本不是学习编程的”套路“ 。—— 你背的再溜，也没法理解核心本质，忘也只是时间的问题！