java - 树操作的复杂性

Question

我有这段代码:

package rr.fe.op.lab.proc;

class TreeNode {
    TreeNode left;
    TreeNode right;
    String data;
}

class TreeProgram {
    public static void main(String[] args) {
        TreeNode node = null;
        node = insert(node, "Han");
        node = insert(node, "Luke");
        node = insert(node, "Leia");
        node = insert(node, "Padme");
        node = insert(node, "Vader");
        node = insert(node, "Yoda");

        System.out.println("Writing tree inorder:");
        writeTree(node);

        node = reverseTreeOrder(node);
        System.out.println("Writing reversed tree inorder:");

        writeTree(node);
        int size = sizeOfTree(node);
        System.out.println("Number of nodes in tree is "+size+".");

        boolean found = containsData(node, "Padme");
        System.out.println("Searched element is found: "+found);
    }

    static boolean containsData(TreeNode treeRoot, String data) {
        if(treeRoot == null)
            return false;
        else if(data.compareTo(treeRoot.data) == 0)
        return true;
        else if(data.compareTo(treeRoot.data) < 1)
            return containsData(treeRoot.left,data);
        else 
            return containsData(treeRoot.right,data);
    }

    static int sizeOfTree(TreeNode treeRoot) {
        if(treeRoot == null)
            return 0;
        else 
            return 1 + sizeOfTree(treeRoot.right) + sizeOfTree(treeRoot.left);
    }

    static TreeNode insert(TreeNode treeRoot, String data) {
        if(treeRoot == null){
            TreeNode newnode = new TreeNode();
            newnode.data = data;
            newnode.left = null;
            newnode.right = null;
            return newnode;
        }
        else if (data.compareTo(treeRoot.data) < 1)
            treeRoot.left = insert(treeRoot.left,data);
        else 
            treeRoot.right = insert(treeRoot.right,data);
        return treeRoot;
    }

    static void writeTree(TreeNode treeRoot) {
        if(treeRoot != null){
            writeTree(treeRoot.left);
            System.out.println(treeRoot.data);
            writeTree(treeRoot.right);
        }
    }

    static TreeNode reverseTreeOrder(TreeNode treeRoot) {
        if(treeRoot == null)
            return null;

        TreeNode node = new TreeNode();
        node = treeRoot.left;
        treeRoot.left = treeRoot.right;
        treeRoot.right = node;

        reverseTreeOrder(treeRoot.left);
        reverseTreeOrder(treeRoot.right);
        return treeRoot;
    }
}

我想知道 containsData 方法的复杂性(以大 O 表示法表示)。我知道方法 containsData 每次在方法verseTreeOrder 之后都找不到数据。但是，我想编写方法 contansData2 ，它将 100% 在树中找到数据，无论它是否反转。该方法的复杂程度如何？你能帮我吗？

Answer 1

复杂度将是O(n)，因为我总是可以给你输入，这将导致每个新元素被放置在每个先前节点的右侧(或左侧)，从而产生一棵不平衡的树:

输入:a、b、c、d

树:

a
 \
  b
   \
    c
     \
      d

对于大多数输入，树会更加平衡，containsData() 会更快，但 O 表示法关心最坏情况。

要使此 O(log n) 为 amortized complexity ，你必须 rebalance the tree .

<小时/>

至于反转树，这会破坏树的不变量，因此 containsData() 方法在查找数据时使用错误的 Twig 。一种解决方案是始终搜索整棵树，但这会抵消排序树带来的任何好处。另一种方法可能是使用“黑客” - 查看根，比较根数据和左右子节点的数据，以确定树是否实际上已反转，然后使用此信息在树中下降。

最坏情况下的复杂度仍为 O(n)。