0

我一直在尝试学习一些数据结构的来龙去脉，并且试图让二叉树能够正常工作。每次我运行以下代码并且我正在寻找的节点超过根时它告诉我它在那里，然后只是从根向下删除整个边。如果节点仅从顶部向下一层，则它可以正常工作。

我不确定出了什么问题，但我想这与我的旋转功能有关。我让它在我之后建模的插入函数中正常工作。

public class SplayBST {
    Node root;
    int count;
    int level = 0;
    boolean found = false;
    public SplayBST() {
        root = null;
        count = 0;
    }

public String searchIt(String x) {
    //after finishing search method I need to check if splaySearch exists then don't insert just splay it
    splaySearch(root, x);
    if (this.found == true) {
        this.found = false;
        return x;
    }
    else {
        return null;
    }
}


    Node splaySearch(Node h, String x) {
        if (h == null) {
            return null;
        }
        if (x.compareTo(h.value) < 0) {
            try {
            if (x.compareTo(h.left.value) < 0) {
                h.left.left = splaySearch(h.left.left, x);
                h = rotateRight(h);
            } else if (x.compareTo(h.left.value) > 0) {
                h.left.right = splaySearch(h.left.right, x);
                h.left = rotateLeft(h.left);
            }
            else {
                this.found = true;
                return h.left;
            }
            return rotateRight(h);
            } 
        catch (NullPointerException ex) {
            return null;
            }
        }

        else { //basically x.compareTo(h.value)>0
            try {
            if (x.compareTo(h.right.value) > 0) {
                h.right.right = splaySearch(h.right.right, x);                
                h = rotateLeft(h);
            } else if (x.compareTo(h.right.value) < 0) {
                h.right.left = splaySearch(h.right.left, x);
                h.right = rotateRight(h.right);
            }
            else {
                this.found = true;
                return h.right;
            }
            return rotateLeft(h);
            }
            catch (NullPointerException ex) {
                return null;
            }
        }
    }


    Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        return x;
    }
    Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        return x;
    }


    class Node {
        Node left;
        Node right;
        String value;
        int pos;
        public Node(String x) {
            left = null;
            right = null;
            value = x;
        }
    }
}
4

2 回答 2

2

我支持 Tristan Hull 使用“有效”搜索方法创建常规 BST 的方法。一旦你开始工作，添加一个 splay 方法就相当简单了。当我在 Java 中实现 Splay Tree时，我实际上做了同样的事情。这是一个更好的软件设计和更简单的实现。

于 2012-10-09T00:00:59.030 回答
1

您的问题是，当您旋转时，您更新了函数“SplaySearch”中对节点 H 的引用，但没有更新原始“searchIt”函数中的父节点。因此，程序“认为”原始父节点仍然是父节点，即使旋转节点应该是父节点。因此，当您运行用于打印树的任何方法时，您从一个节点打印，该节点实际上不是树的父节点，而是一个子节点（它所在的级别取决于您的程序调用 rotateLeft 和 rotateRight 的次数）。

为了解决这个问题，我建议在普通二叉树中实现搜索，然后将“展开”函数与将节点展开到树顶部的搜索函数完全分开。您将在每次搜索结束时调用此 splay 函数，确保正确更新您的参考。这是实现伸展树的传统方式，我建议你看看它（也许看看关于伸展树的维基百科文章或谷歌搜索）。此外，您可能想知道您的旋转功能不完整。在展开树方面，您还有 2 种不同类型的双旋转，它们与单旋转非常不同。同样，我建议查找 splay 树以更深入地了解它们。

于 2012-10-08T23:05:26.693 回答