二分查找树求successor似乎比想象的要复杂，请老师看下我写的对不对

Question

我发现successor并不是简单的Hibbard算法就可以的，Hibbard似乎只适合删除，因为删除的时候已经确认左子树和右子树都存在在。但计算successor并不是，比如课程的例子的树：
5
/
3 6
/ \
2 4 8

5、3、6可以使用Hibbard搞定，但2、4、8不可以。我发现只有被查节点存在右子树，才可以用Hibbard，比如图中的2不存在右子树，无法使用。那应该怎么做呢？我自己观察了一下，要先判断自身是parent的左子还是右子，如果是左子，则父节点即是successor，因为此时parent刚刚好比node大一点点，如果自身是parent的右子，则情况很麻，要判断parent是grandParent的左子还是右子，并且需要循环向上找parent，直到找到为左子的祖先parent。先写一下伪代码：
if (node 是左子) {
successor = parent
}
if (node = 是右子) {
while(true) {
if (parent 是左子) {
successor = parent.parent
}
parent = parent.parent
}
}

我根据这种想法实现了代码，跟老师的Node相比，我多维护了parent、nodeType等成员变量，最终successor的求解是：

	public E successor(E e) {
        if (contains(e)) {
            Node<E> successorNode = getSuccessorByHibbarb(root, e);
            if (successorNode == null) {
                successorNode = getSuccessorByBian(root, e);
            }
            return successorNode == null ? null : successorNode.e;
        }else {
            return e;
        }
    }

    public Node<E> getSuccessorByHibbarb(Node<E> node, E e) {
        if (e.compareTo(node.e) == 0) {
            Node<E> resNode = null;
            if (node.left == null) {
                resNode = node.right;
            } else if (node.right == null) {
                resNode = node.left;
            } else {
                return minimum(node.right);
            }
            node = null;
            return resNode;
        }

        if (e.compareTo(node.e) < 0) {
            return getSuccessorByHibbarb(node.left, e);
        }else {
            return getSuccessorByHibbarb(node.right, e);
        }
    }

    public Node<E> getSuccessorByBian(Node<E> node, E e) {
        if (e.compareTo(node.e) == 0) {
            if (node.isLeftChild()) {
                return node.parent;
            }
            if (node.isRightChild()) {
                Node<E> turnNode = node.parent;
                while (true) {
                    if (turnNode.isLeftChild()) {
                        return turnNode.parent;
                    }
                    if (turnNode.isRoot()) {
                        return null;
                    }
                    turnNode = turnNode.parent;
                }
            }
        }

        if (e.compareTo(node.e) < 0) {
            return getSuccessorByBian(node.left, e);
        }else {
            return getSuccessorByBian(node.right, e);
        }
    }

我测试了代码，在少量数据的时候是可以得到正确答案的，请问老师，是我想复杂了嘛？求successor有更简单的办法嘛？

Answer 1

liuyubobobo 2020-02-08 02:13:17

我在我的另一门课程《算法与数据结构》的补充代码中，提供过一版 successor 的参考实现，可以参考研究一下，看看和你的思路是否一致？

传送门：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/05-Binary-Search-Tree/Course%20Code%20(Java)/Optional-06-Predecessor-and-Successor-in-BST/src/bobo/algo/BST.java

有时间我把这个参考代码也根据这个课程的讲解，放到这个课程的代码仓下。感谢提醒。

继续加油！：）

• 提问者 慕码人1018289 #1

  非常感谢您的回复，我最近问的问题比较多。
  
  我看了您代码，咱们都是先找右子树中最小的，找不到再用另一个方法找，此时您使用了一招“从root开始，在这个路径上寻找到比key大的最小值”，是从root到叶子节点的方法，我则是从叶子节点向上望，期望存在一个parent是转折的，我因此被迫维护了一个parent，在add方法中设置，以后不动。您之所以没用parent，是因为把parent已经融合在compare大小中了。
  
  我不知道哪种好，但您不需要维护parent。我尝试会用您的思路再实现一下前驱。另外，为什么您不喜欢维护一个parent呢？或者说套路上为什么BST一般不维护parent呢？

• liuyubobobo 回复 提问者 慕码人1018289 #2

  我也不知道我为什么不喜欢维护 parent。思考了一下，或许是因为这样其实破坏了递归的性质。所谓的递归，就是现在更小的范围里解决问题，然后用这个更小范围的解，去构造更大范围的解。而去看 parent，其实相当于“破坏”了这个更小范围的解的独立性。这样的思路，更适合非递归的思考。个人见解：）继续加油！：）

• 提问者 慕码人1018289 回复 liuyubobobo #3

  非常感谢您的回复！您的回复真是太快了~！
  看来递归思维并不是那么好建立的，我之前自学的递归，递归的不那么彻底，我现在在不断的拧这个思路，不是拧成别人的，是期望可以掌握两种思路。再次感谢您的回复~！