在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

我想在这里进行一次理智检查。我相信维基百科页面上列出的算法 Day–Stout–Warren algorithm 平衡BST存在问题。

这个伪代码旨在将BST变成一个“藤蔓”(有行列表)。

routine tree-to-vine(root)
    // Convert tree to a "vine", i.e., a sorted linked list,
    // using the right pointers to point to the next node in the list
    tail ← root
    rest ← tail.right
    while rest ≠ nil
        if rest.left = nil
            tail ← rest
            rest ← rest.right
        else
            temp ← rest.left
            rest.left ← temp.right
            temp.right ← rest
            rest ← temp
            tail.right ← temp

问题是算法跳过了根节点的左侧节点。因此,如果你从一个有两个子节点的根节点开始,你最终会得到一个LL,如果它存在,它会丢失根节点的左子树。

我认为这解决了它,虽然不优雅。它基本上发生了变化 tail 和 rest 每升一级,并增加一个 head 变量,用于记住列表开头的最低值。

routine tree-to-vine-fixed(root)
    head ← null
    tail ← null
    rest ← root

    while rest ≠ null
        if rest.left = null
            if tail = null
                // Set head to the minimum value of the tree (left-most node)
                head ← rest
            // No left child, move the tail and rest pointers forward
            tail ← rest
            rest ← rest.right
        else
            // Left child exists, perform rotations
            temp ← rest.left
            rest.left ← temp.right
            temp.right ← rest
            rest ← temp
            if tail ≠ null
                tail.right ← temp

    return head

我创建了一个java函数来测试它。(我还创建了一个有缺陷的算法的java版本,以确认它确实删除了根节点的左子树)。

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
public class DSW {
    public static TreeNode treeToVineFixed(TreeNode root) {
        TreeNode head = null, tail = null;  // ** change: shift tail and rest up
        TreeNode rest = root;

        while (rest != null) {
            if (rest.left == null) {
                if (tail == null)  // ** change: set the head to be the min value of the tree, i.e. left-most path
                    head = rest;
                // No left child, move the tail and rest pointers forward
                tail = rest;
                rest = rest.right;
            } else {
                // Left child exists, perform rotations
                TreeNode temp = rest.left;
                rest.left = temp.right;
                temp.right = rest;
                rest = temp;
                if (tail != null)  // **change: otherwise NPE
                    tail.right = temp;
            }
        }
        return head;
    }

在修复之前和之后,我都用这个进行了测试,以确认原始版本不起作用,而我的更新版本起作用了:

        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(5);
        root.right = new TreeNode(10);
        root.right.left = new TreeNode(8);
        root.right.right = new TreeNode(20);
        root.right.left.left = new TreeNode(7);
        root.right.left.right = new TreeNode(9);

        System.out.println("Original Tree");
        System.out.println(renderAsciiTree(root));

        var head = treeToVineOriginal(root);  // not shown
        System.out.println("Incorrect Vine");
        System.out.println(renderAsciiTree(head));

        var head = treeToVineFixed(root);
        System.out.println("Vine");
        System.out.println(renderAsciiTree(head));

如果我错过了什么,请告诉我。