江苏龙网

  1. 主页 > 生活百科 > >

面试让我手写红黑树( 五 )

红黑树


1. 2-3树数据结构
2–3树是一种树型数据结构，由约翰·霍普克洛夫特于1970年发明 。它通过在一个节点存放1-2个元素来平衡树高 。从而也使2-3树存在2叉节点和3叉节点 。

面试让我手写红黑树

文章插图
 
这里要提到一点，在BST二叉搜索树可能退化成链表的基础上 。引出了自平衡二叉树，也就是包括上一章实现的AVL树和Java API HashMap中用到的红黑树，它们都属于BalancedTree，也统称为B树，平衡的意思 。
而本章实现的2-3树也是一种简单的平衡树，其中每个具有子节点（内部节点）的节点要么有两个子节点（2 节点）和一个数据元素，要么有三个子节点（3 节点）和两个数据元素 。另外 2-3 树是3阶B 树，2-3-4 树是4阶B树 。
在实现2-3树之前，先通过图稿演示下在2-3树中顺序插入1、2、3、4、5、6、7，七个元素时，2-3树的调衡处理 。
面试让我手写红黑树

文章插图
 
【面试让我手写红黑树】 
  • 2-3 树的插入过程与 BST 树类似，会通过树的左右节点大小，找到自己的插入位置 。
  • 一个节点可以右1-3个元素，但当元素个数为3时，则需要调衡 。把三个节点的中间节点晋升上来，其余两个节点为子节点 。
  • 如果进行一次调衡后，上一层父节点达到3个元素，则需要2次调衡，来满足2-3树的规则 。
 
咋样，是不看过这个图之后对于2-3树的实现已经有感觉了，想动手写写试试了？
 
  • 源码地址：https://github.com/fuzhengwei/java-algorithms
  • 本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/tree
2. 2-3树结构实现 
2-3 树的实现并不复杂，但在实现前要思考以下几个问题；
 
  • Node 节点属性信息都包括什么？
  • 插入值，是否需要创建新的 Node？
  • 插入后，节点内有3个元素后，怎么迁移元素？
2.1 节点定义 public class Node_2_3 { // 元素 public int[] items; // 序号 public int number; // 孩子 public Node_2_3[] children; // 父亲【非必须】 public Node_2_3 parent; public Node_2_3() { this.items = new int[3]; this.number = 0; this.children = new Node_2_3[4]; this.parent = null; } public void insert(int e) { int idx = this.number - 1; while (idx >= 0) { if (this.items[idx] < e) break; this.items[idx + 1] = this.items[idx]; --idx; } this.items[idx + 1] = e; ++this.number; } // ... 省略部分代码 }
  • 2-3树的几点元素需要包括；一个数组的元素集合、元素的序号、孩子元素 。因为一个节点最多可临时放入3个元素，那么就会最多有4个孩子元素，所以孩子元素也是一个数组并且在构造函数中按照4个元素进行初始化 。
  • 由于本身2-3树插入元素的开始阶段，并不是直接创建一个新的节点，而是在初始化的数组空间中存入元素 。所以在节点中提供了一个插入元素的方法 insert 来处理新增元素 。
  • 另外2-3树的节点类，还提供了一个方便查询的方法 。包括：获取左边元素、中间元素、右边元素，以及最小值、最大值和判断是否有孩子节点 。这些内容可以源码 。
2.2 拆分节点 
当一个节点内有3个元素的时候，就要发起拆分东西，拆分的过程分为；
 
  1. 对3个节点的中间节点，插入到父节点上 。
  2. 剩余2个节点创建出新的节点 。
  3. 建立父节点和新创建的2个节点间关系 。
 
整个操作流程如图所示
面试让我手写红黑树

文章插图
 
2.1 插入父节点 private Node_2_3 split(Node_2_3 node, Node_2_3 parent) { if (parent == null) { parent = new Node_2_3(node); } parent.insert(node.getMiddleItem()); Node_2_3[] newNodes = this.triangle(node); this.replaceChild(parent, node, newNodes[0], newNodes[1]); return parent; }
  • 整个2-3树拆分的过程就是在 split 这个方法里，第一步解决了是否有父节点，没有则创建 。
  • 之后将原节点的中间值插入到父节点中 。接下来的操作就是拆分新节点和更换孩子节点建立新连接 。
2.2 拆分新节点 private Node_2_3[] triangle(Node_2_3 node) { Node_2_3[] newNodes = new Node_2_3[2]; newNodes[0] = new Node_2_3(node.items[0]); newNodes[1] = new Node_2_3(node.items[2]); if (!node.isLeaf()) { // 左孩子 newNodes[0].children[0] = node.children[0]; newNodes[0].children[1] = node.children[1]; // 右孩子 newNodes[1].children[0] = node.children[2]; newNodes[1].children[1] = node.children[3]; } return newNodes; }


推荐阅读


上一篇：比红黑树更快的跳表到底是什么数据结构？如何实现？

下一篇：Springboot 之 Filter 实现 Gzip 压缩超大 json 对象