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

通过节点4拿到父节点2和右子节点5，把父节点2和右子节点5建立关联

节点5的左子节点，相当于是大于4小于4的那么一个值，只不过这里不体现。那么这个节点4的左子节点，应该被迁移到节点3的右子节点上。

整理节点5的关系，左子节点为4 。左子节点4的父节点为5

如果说迁移上来的节点5无父节点，那么它就是父节点 root = temp

迁移上来的节点5，找到原节点4是对应父节点的左子节点还是右子节点，对应的设置节点5的左右位置

2.2 右旋
图解右旋操作；它就是一种摘链更换调整节点的处理过程，小傅哥把它分解展示，整个过程如下；

文章插图

代码实现

protected Node rotateRight(Node node) { Node temp = node.left; temp.parent = node.parent; node.left = temp.right; if (node.left != null) { node.left.parent = node; } temp.right = node; node.parent = temp; if (temp.parent == null) { root = temp; } else { if (temp.parent.left == node) { temp.parent.left = temp; } else { temp.parent.right = temp; } } return temp; }

右旋的作用，相当于通过向上迁移树高差大于1的右子节点来降低树高的操作。
通过节点3拿到父节点4和左子节点2，把父节点7和左子节点2建立关联
节点2的右子节点，相当于是大于2小于3的那么一个值，只不过这里不体现。那么这个节点2的右子节点，应该被迁移到节点3的左子节点上。
整理节点2的关系，右子节点为3 。右子节点3的父节点为2
如果说迁移上来的节点2无父节点，那么它就是父节点 root = temp
迁移上来的节点2，找到原节点3是对应父节点的左子节点还是右子节点，对应的设置节点2的左右位置

2.3 左旋 + 右旋
之所以会有左旋 + 右旋，是因为一次右旋操作没法平衡树高，而这种树的不平衡节点的左子节点的右子节点过长，所以要把不平衡节点的左子节点向左旋转一次，之后再进行右旋操作。

文章插图

代码实现

if (factor(node.left) >= 0) { Node temp = super.rotateRight(node); refreshHeight(temp.right); refreshHeight(temp); } else { Node temp = super.rotateLeft(node.left); refreshHeight(temp.left); refreshHeight(temp); node.left = temp; temp = super.rotateRight(node); refreshHeight(temp.right); refreshHeight(temp); }

2.4 右旋 + 左旋
之所以会有右旋 + 左旋，是因为一次左旋操作没法平衡树高，而这种树的不平衡节点的右子节点的左子节点过长，所以要把不平衡节点的右子节点向右旋转一次，之后再进行左旋操作。

文章插图

代码实现

if (factor(node.right) <= 0) { Node temp = super.rotateLeft(node); refreshHeight(temp.left); refreshHeight(temp); } else { Node temp = super.rotateRight(node.right); refreshHeight(temp.right); refreshHeight(temp); node.right = temp; temp = super.rotateLeft(node); refreshHeight(temp.left); refreshHeight(temp); }

3. AVL树功能测试
为了验证AVL树的实现正确与否，这里我们做一下随机节点的插入，如果它能一直保持平衡，那么它就是一颗可靠 AVL 平衡树。
单元测试

@Test public void test_random() { AVLTree tree = new AVLTree(); for (int i = 0; i < 30; i++) { tree.insert(new Random().nextInt(100)); } System.out.println(tree); }

测试结果

输入节点：61,3,34,82,1,75,56,65,87,18,3,96,53,50,42,24,69,11,95,69,1,1,84,22,5,70,28,55,38,92 /----- 96(0) /----- 95(1) | ----- 92(0) /----- 87(2) | | /----- 84(0) | ----- 82(1) /----- 75(3) | | /----- 70(0) | | /----- 69(1) | ----- 69(2) | ----- 65(0) 61(5) | /----- 56(1) | | ----- 55(0) | /----- 53(2) | | | /----- 50(0) | | ----- 42(1) | | ----- 38(0) ----- 34(4) | /----- 28(0) | /----- 24(1) | | ----- 22(0) | /----- 18(2) | | ----- 11(1) | | ----- 5(0) ----- 3(3) | /----- 3(1) | | ----- 1(0) ----- 1(2) ----- 1(0) Process finished with exit code 0