江苏龙网

  1. 主页 > 生活百科 > >

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

红黑树


 
Node uncle = grandParent.left; // 染色 if(uncle.color == Node.Color.RED){ parent.color = Node.Color.BLACK; uncle.color = Node.Color.BLACK; grandParent.color = Node.Color.RED; current= grandParent; }

  • 染色时根据当前节点的爷爷节点，找到当前节点的叔叔节点 。
  • 再把父节点染黑、叔叔节点染黑，爷爷节点染红 。但爷爷节点染红是临时的，当平衡树高操作后会把根节点染黑 。具体参考源码
2.3 左旋调衡 2.3.1 一次左旋 
对照2-3树，只有当一个节点内有3个节点的时候，才需要调衡 。那么红黑树则是判断当前节点的叔叔节点是否为红色节点，如果不是则没法通过染色调衡，也就是需要选择进行调衡 。
面试让我手写红黑树

文章插图
 
parent.color = Node.Color.BLACK; grandParent.color = Node.Color.RED; super.rotateLeft(grandParent);
  • 当你把红黑树对照理解成2-3树，如图中第1步骤下的左侧小图，新增的节点5倒置2-3树不平衡 。
  • 那么这个时候需要把2-3树中节点4提起来，而对应红黑树则需要先进行染色，待操作的节点4为黑色，两个孩子节点为红色 。
  • 最后是把节点3进行一次左旋操作，完成树的平衡 。对应步骤3中的左侧小图是2-3树调衡后的结果 。
2.3.2 右旋 + 左旋 
当一次左旋没法调衡，需要右旋+左旋的情况，在AVL树中有同样的场景 。本身树需要左旋操作，但整体分支树节点偏左，此时需要右旋调整树结构再左旋 。此处可参考小傅哥编写的AVL树
面试让我手写红黑树

文章插图
 
// 偏左↙，先右旋一次调衡 if (current == parent.left){ current = parent; super.rotateRight(current); parent = current.parent; } parent.color = Node.Color.BLACK; grandParent.color = Node.Color.RED; super.rotateLeft(grandParent);
  • 红黑树新增节点4以后，4↙5 结构偏左，需要先进行右旋调衡树结构，再进行左旋 。其实这个时候再进行的左旋就和上面一次左旋操作一致了 。
4. 右旋调衡 2.4.1 一次右旋 
对照2-3树，只有当一个节点内有3个节点的时候，才需要调衡 。那么红黑树则是判断当前节点的叔叔节点是否为红色节点，如果不是则没法通过染色调衡，也就是需要选择进行调衡 。
面试让我手写红黑树

文章插图
 
parent.color = Node.Color.BLACK; grandParent.color = Node.Color.RED; super.rotateRight(grandParent);
  • 当你把红黑树对照理解成2-3树，如图中第1步骤下的右侧小图，新增的节点1倒置2-3树不平衡 。
  • 那么这个时候需要把2-3树中节点2提起来，而对应红黑树则需要先进行染色，待操作的节点2为黑色，两个孩子节点为红色 。
  • 最后是把节点2进行一次右旋操作，完成树的平衡 。对应步骤3中的右侧小图是2-3树调衡后的结果 。
2.4.2 左旋 + 右旋 
当一次左旋没法调衡，需要左旋+右旋的情况，在AVL树中有同样的场景 。本身树需要右旋操作，但整体分支树节点偏右，此时需要左旋调整树结构再右旋 。
面试让我手写红黑树

文章插图
 
// 偏右↘，先左旋一次调衡 if (current == parent.right){ current = parent; super.rotateLeft(current); parent = current.parent; } parent.color = Node.Color.BLACK; grandParent.color = Node.Color.RED; super.rotateRight(grandParent);
  • 红黑树新增节点2以后，1↘2 结构偏右，需要先进行左旋调衡树结构，再进行右旋 。其实这个时候再进行的右旋就和上面一次右旋操作一致了 。
3. 红黑树实现测试 
为了验证红黑树的实现正确与否，这里我们做一下随机节点的插入，如果它能一直保持平衡，那么它就是一颗可靠红黑平衡树 。
@Test public void test_binary_search_tree() { Tree tree = new RedBlackTree(); for (int i = 0; i < 20; i++) { tree.insert(new Random().nextInt(100)); } System.out.println(tree); }
测试结果
RedBlackTree，输入节点：79,92,36,35,72,22,11,66,98,28,30,39,56,26,1,25,33,80,22,23 /----- /----- 98(红) | ----- /----- 92(黑) | | /----- | ----- 80(红) | ----- /----- 79(黑) | | /----- | | /----- 72(黑) | | | ----- | ----- 66(红) | | /----- | | /----- 56(红) | | | ----- | ----- 39(黑) | ----- 36(黑) | /----- | /----- 35(黑) | | | /----- | | ----- 33(红) | | ----- | /----- 30(红) | | | /----- | | ----- 28(黑) | | ----- ----- 26(黑) | /----- | /----- 25(红) | | ----- | /----- 23(黑) | | | /----- | | ----- 22(红) | | ----- ----- 22(红) | /----- ----- 11(黑) | /----- ----- 1(红) ----- 对照2-3树结构 /----- [98] /----- [92] | ----- [80] /----- [79] | | /----- [72] | ----- [66] | ----- [39,56] [36] | /----- [33,35] | /----- [30] | | ----- [28] ----- [26] | | /----- [25] ----- [22,23]----- [22] ----- [1,11]


推荐阅读


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

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