Treap数据结构打印缺失节点，请求技术协助

我用Java实现了Treap数据结构，但调用toString方法打印时发现部分节点缺失。以下是完整代码、测试用例、实际输出及期望输出，请求协助排查原因。

完整Treap代码 #

import java.util.Random;
import java.util.Stack;

public class Treap <E extends Comparable<E>>{
    private Random priorityGenerator;
    private Node<E> root;


    public Treap() {
        root = null;
        priorityGenerator = new Random();
    }

    public Treap(long seed) {
        root = null;
        priorityGenerator = new Random(seed);
    }
    
    private static class Node<E> {
        public E data; //key for the search
        public int priority; //random heap priority
        public Node <E> left;
        public Node <E> right;
        
        public  Node (E data, int priority) {
            if (data == null) {
                throw new IllegalArgumentException("Data is Null");
            }
            this.data = data;       
            this.priority = priority;
            this.left = null;
            this.right = null;
        }
        /**implementation of rotateRight */
        Node<E> rotateRight() {
            Node<E> newRoot = new Node<E>(this.data, this.priority);
            newRoot.right = this.right;
            if (this.left.right != null) {
                newRoot.left = this.left.right;
            }
            this.data = this.left.data;
            this.priority = this.left.priority;
            this.right = newRoot;
            if (this.left.left != null) {
                this.left = this.left.left;
            } else {
                this.left = null;
            }
            return newRoot;
        }
        /**implementation of rotateLeft */
        Node<E> rotateLeft() {
            Node<E> newRoot = new Node<E>(this.data, this.priority);
            newRoot.left = this.left;
            if (this.right.left != null) {
                newRoot.right = this.right.left;
            }
            this.data = this.right.data;
            this.priority = this.right.priority;
            this.left = newRoot;
            if (this.right.right != null) {
                this.right = this.right.right;
            } else {
                this.right = null;
            }
            return newRoot;
        }


    }
    boolean add(E key) {
        int priority = priorityGenerator.nextInt();
        return add(key, priority);
    }

    boolean add(E key, int priority) {
        Node<E> newNode = new Node<E>(key, priority);
        if (root == null) {
            root = newNode;
            return true;
        }
        Node<E> curr = root;
        Stack<Node<E>> stack = new Stack<>();
        while (curr != null) {
            int cmp = key.compareTo(curr.data);
            if (cmp == 0) {
                return false; // key already exists, no need to add again
            }
            stack.push(curr);
            if (cmp < 0) {
                if (curr.left == null) {
                    curr.left = newNode;
                    reheap(stack, newNode);
                    return true;
                }
                curr = curr.left;
            } else {
                if (curr.right == null) {
                    curr.right = newNode;
                    reheap(stack, newNode);
                    return true;
                }
                curr = curr.right;
            }
        }
        return false; // should never reach this point
    }

    private void reheap(Stack<Node<E>> stack, Node<E> curr) {
        while (!stack.empty()) {
            Node<E> parent = stack.pop();
            if (parent.priority > curr.priority) {
                return; // heap invariant already satisfied
            }
            if (curr == parent.left) {
                parent.rotateRight();
            } else {
                parent.rotateLeft();
            }
        }
        // if we reach this point, we have rotated the root node
        root = curr;
    }

    /**Delete method, that was delete a desired node */
    public boolean delete(E key) {
        Node<E> curr = root;
        Node<E> parent = null;
        Stack<Node<E>> stack = new Stack<>();
        while (curr != null) {
            int cmp = key.compareTo(curr.data);
            if (cmp == 0) {
                break;
            }
            parent = curr;
            stack.push(parent);
            if (cmp < 0) {
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
        if (curr == null) {
            return false; // key not found
        }
        while (curr.left != null || curr.right != null) {
            if (curr.right == null || (curr.left != null && curr.left.priority > curr.right.priority)) {
                curr.rotateRight();
                if (parent == null) {
                    root = curr;
                } else if (parent.left == curr) {
                    parent.left = curr;
                } else {
                    parent.right = curr;
                }
                parent = curr;
                curr = curr.right;
            } else {
                curr.rotateLeft();
                if (parent == null) {
                    root = curr;
                } else if (parent.left == curr) {
                    parent.left = curr;
                } else {
                    parent.right = curr;
                }
                parent = curr;
                curr = curr.left;
            }
        }
        if (parent == null) {
            root = null;
        } else if (parent.left == curr) {
            parent.left = null;
        } else {
            parent.right = null;
        }
        return true;
    }
    
    /**Find operation */
    private boolean find(Node<E> root, E key) {
        if (root == null) {
            return false;
        }
        int cmp = key.compareTo(root.data);
        if (cmp == 0) {
            return true;
        } else if (cmp < 0) {
            return find(root.left, key);
        } else {
            return find(root.right, key);
        }
    }

    public boolean find(E key) {
        return find(root, key);
    }
    
    /** toString operation */
    public String toString() {
        return toString(root);
    }

    private String toString(Node<E> node) {
        if (node == null) {
            return "null";
        }

        String leftString = toString(node.left);
        String rightString = toString(node.right);

        String nodeString = "(key = " + node.data.toString() + " , priority = " + node.priority + ")";

        if (node.left == null && node.right == null) {
            return nodeString;
        } else if (node.left == null) {
            return nodeString + " (null) " + rightString;
        } else if (node.right == null) {
            return nodeString + " " + leftString + " (null)";
        } else {
            return nodeString + " " + leftString + " " + rightString;
        }
    }
}

测试用例代码 #

public class main_ {
    public static void main(String[] args) {
        Treap<Integer> testTree = new Treap <Integer>();
        
        // Add nodes to the treap
        testTree.add(4,19);
        testTree.add(2,31);
        testTree.add(6, 70); 
        testTree.add(1 ,84);
        testTree.add(3 ,12); 
        testTree.add(5 ,83);
        testTree.add(7 ,26);

        
        // Print the treap using the toString method
        System.out.println(testTree.toString());
       
    }
}

实际输出 #

(key = 1 , priority = 84) (null) (key = 5 , priority = 83) (key = 3 , priority = 12) (key = 7 , priority = 26)

期望输出 #

(key =1 , priority =84)
 null
( key =5 , priority =83)
( key =2 , priority =31)

null
 ( key =4 , priority =19)
( key =3 , priority =12)
 null
null
 null
( key =6 , priority =70)
 null
( key =7 , priority =26)
 null 

问题原因及解决方案 #

核心问题：旋转方法实现错误 #

当前rotateRight和rotateLeft方法通过新建节点转移数据，而非直接调整指针引用，破坏了Treap的节点结构，导致部分节点丢失，无法被toString方法遍历到。

修正后的旋转方法 #

替换原旋转方法为标准指针调整实现：

/**implementation of rotateRight */
Node<E> rotateRight() {
    Node<E> newRoot = this.left;
    this.left = newRoot.right;
    newRoot.right = this;
    return newRoot;
}

/**implementation of rotateLeft */
Node<E> rotateLeft() {
    Node<E> newRoot = this.right;
    this.right = newRoot.left;
    newRoot.left = this;
    return newRoot;
}

修正reheap方法 #

原reheap方法未更新旋转后的节点引用，导致后续堆调整逻辑错误，修正后：

private void reheap(Stack<Node<E>> stack, Node<E> curr) {
    Node<E> parent;
    while (!stack.empty()) {
        parent = stack.pop();
        if (parent.priority > curr.priority) {
            return;
        }
        if (curr == parent.left) {
            curr = parent.rotateRight();
        } else {
            curr = parent.rotateLeft();
        }
        if (!stack.isEmpty()) {
            Node<E> grandParent = stack.peek();
            if (grandParent.left == parent) {
                grandParent.left = curr;
            } else {
                grandParent.right = curr;
            }
        } else {
            root = curr;
        }
    }
}

修正delete方法中的旋转逻辑 #

原delete方法依赖错误的旋转实现，修正后适配新的旋转方法：

public boolean delete(E key) {
    Node<E> curr = root;
    Node<E> parent = null;
    while (curr != null) {
        int cmp = key.compareTo(curr.data);
        if (cmp == 0) {
            break;
        }
        parent = curr;
        if (cmp < 0) {
            curr = curr.left;
        } else {
            curr = curr.right;
        }
    }
    if (curr == null) {
        return false;
    }
    while (curr.left != null || curr.right != null) {
        if (curr.right == null || (curr.left != null && curr.left.priority > curr.right.priority)) {
            Node<E> newCurr = curr.rotateRight();
            if (parent == null) {
                root = newCurr;
            } else if (parent.left == curr) {
                parent.left = newCurr;
            } else {
                parent.right = newCurr;
            }
            parent = newCurr;
            curr = newCurr.right;
        } else {
            Node<E> newCurr = curr.rotateLeft();
            if (parent == null) {
                root = newCurr;
            } else if (parent.left == curr) {
                parent.left = newCurr;
            } else {
                parent.right = newCurr;
            }
            parent = newCurr;
            curr = newCurr.left;
        }
    }
    if (parent == null) {
        root = null;
    } else if (parent.left == curr) {
        parent.left = null;
    } else {
        parent.right = null;
    }
    return true;
}

优化toString方法（实现期望格式） #

如果需要输出带换行和缩进的格式，替换原toString方法为：

public String toString() {
    StringBuilder sb = new StringBuilder();
    toString(root, sb, 0);
    return sb.toString();
}

private void toString(Node<E> node, StringBuilder sb, int depth) {
    if (node == null) {
        sb.append("null\n");
        return;
    }
    sb.append("(key = ").append(node.data).append(" , priority = ").append(node.priority).append(")\n");
    // 左子树缩进
    sb.append(" ".repeat(depth + 2));
    toString(node.left, sb, depth + 2);
    // 右子树缩进
    sb.append(" ".repeat(depth + 2));
    toString(node.right, sb, depth + 2);
}

内容的提问来源于stack exchange，提问作者Pmesh