江苏龙网

  1. 主页 > 生活百科 > >

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

红黑树

  • 首先判断插入元素时候是否有树根，没有则会把当前节点创建出一颗树根来 。
  • 如果当前树是有树根的，则对插入元素与当前树进行一个节点遍历操作，找到元素可以插入的索引位置 parent（挂到这个父节点下） 。也就是 search 搜索过程 。
  • 最后就是插入元素，通过给插入值创建一个 Node 节点，并绑定它的父元素，以及把新元素挂到索引到的 parent 节点下 。
2.3 索引节点 public Node search(int e) { Node node = root; while (node != null && node.value != null && node.value != e) { if (e < node.value) { node = node.left; } else { node = node.right; } } return node; }
  • 值查找的过程，就是对二叉搜索树的遍历，不断的循环节点，按照节点值的左右匹配，找出最终相当的值节点 。
2.4 删除节点 public Node delete(int e) { Node delNode = search(e); if (null == delNode) return null; return delete(delNode); } private Node delete(Node delNode) { if (delNode == null) return null; Node result = null; if (delNode.left == null) { result = transplant(delNode, delNode.right); } else if (delNode.right == null) { result = transplant(delNode, delNode.left); } else { // 因为删除的节点，有2个孩子节点，这个时候找到这条分支下，最左侧做小的节点 。用它来替换删除的节点 Node miniNode = getMiniNode(delNode.right); if (miniNode.parent != delNode) { // 交换位置，用miniNode右节点，替换miniNode transplant(miniNode, miniNode.right); // 把miniNode 提升父节点，设置右子树并进行挂链 。替代待删节点 miniNode.right = delNode.right; miniNode.right.parent = miniNode; } // 交换位置，删除节点和miniNode 可打印测试观察；System.out.println(this); transplant(delNode, miniNode); // 把miniNode 提升到父节点，设置左子树并挂链 miniNode.left = delNode.left; miniNode.left.parent = miniNode; result = miniNode; } size--; return result; } private Node getMinimum(Node node) { while (node.left != null) { node = node.left; } return node; } private Node transplant(Node delNode, Node addNode) { if (delNode.parent == null) { this.root = addNode; } // 判断删除元素是左/右节点 else if (delNode.parent.left == delNode) { delNode.parent.left = addNode; } else { delNode.parent.right = addNode; } // 设置父节点 if (null != addNode) { addNode.parent = delNode.parent; } return addNode; } 2.4.1 删除单节点 
面试让我手写红黑树

文章插图
 
 
  • 待删除节点14，判断此节点的父节点的孩子节点，哪个等于14，找出左右
  • 把待删节点的右孩子节点，挂到删除节点的右节点
  • 给待删节点的右孩子节点，设置上父节点
2.4.2 删除双节点 
面试让我手写红黑树

文章插图
 
 
  • 待删除节点64，含有双子节点，则需要根据第一个右子节点查找最小左子节点 。从89到72，如果有比72还小的左子节点，继续排查 。
  • 排查到节点72，将72这个准备替换待删元素的节点，与右子节点73进行位置交换，过程与 4.1 相同 。使用交换函数 transplant
  • 最后是进行节点72与待删节点64的交换过程，更换三角关系，父节点、左子节点、右子节点 。
3. 二叉搜索树功能测试 
为了方便观察树结构的变化，这里小傅哥找了一些资料资料，一种是我们可以通过程序来打印（类似大家之前打印99乘法表，另外是使用线上的可视化图：https://visualgo.NET/zh/bst?slide=1）
3.1 随机插入元素 @Test public void test_binary_search_tree() { BinarySearchTree tree = new BinarySearchTree(); for (int i = 0; i < 10; i++) { tree.insert(new Random().nextInt(100)); } System.out.println(tree); }
测试结果
/----- 91 | ----- 78 /----- 74 | ----- 67 61 | /----- 51 ----- 40 | /----- 28 ----- 14 ----- 7 Process finished with exit code 0
  • 因为你测试时的随机数不同，可能会出现很多不同结构的二叉搜索树，也可能是一个类似链表结构的退化树 。
3.2 插入并且删除 @Test public void test_insert_delete(){ BinarySearchTree tree = new BinarySearchTree(); tree.insert(32); tree.insert(7); tree.insert(64); tree.insert(63); tree.insert(89); tree.insert(72); tree.insert(94); tree.insert(6); tree.insert(14); tree.insert(18); tree.insert(73); System.out.println(tree); // 删除单节点，只有一个孩子的父节点 // tree.delete(14); // 删除双节点，拥有二个孩子的父节点 tree.delete(64); System.out.println(tree); }


推荐阅读


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

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