我正在自己写红黑树。但是当我测试涉及要旋转的根的旋转时,它在某种程度上失去了参考。
树结构:
45
/ \
40x 70
/ \ /
7 41 50
/ \
6 39
旋转逻辑说:“以 45(根)为顶部,在提升 X(即 40)的方向上旋转”
所以这意味着右旋转,结果应该如下所示:
40x
/ \
7 45
/ \ / \
6 39 41 70
/
50
假设节点 45 是祖父节点,7 是父节点,41 是当前节点。(我知道顺序没有意义但请忽略,这是因为我已经旋转了一次)
代码:
//current is node 45
//parent is node 7
//grandparent is node 45 (root)
//first detach cross node (i.e. 41)
Node crossNode2 = grandparent.left.right;
grandparent.left.right = null; //detach
45
/ \
40x 70
/ \ /
7 null 50
/ \
6 39
grandparent.left = null;
45
/ \
null 70
/
50
current.right = grandparent;
40
/ \
7 45
/ \ / \
6 39 null 70
/
50
grandparent.left = crossNode2; //attach
40
/ \
7 45
/ \ / \
6 39 41 70
/
50
但不知何故,这段代码不起作用。当我测试时:
preorder
45, 39, 70, 50
breadth-first
45, 39, 70, 50
所以我认为结果实际上是:
45
/ \
39 70
/
50
谁能给我提示我的轮换代码有什么问题?