java - 获取 BST 子树中第 n 个最大的数据值

Question

我希望在 BST 中以该节点为根的子树中返回第 n 个最大的数据值，该值可以具有重复值。

现在我有这个，但它似乎不起作用

static int get(BSTNode node, int n) {
    
    if ( node == null || n < 0)
    return 0;
            
    if ( n == 0)
        return node.data;
    
    get(node.right, n--);           
    get(node.left, n--);

    return 0;
}

这是我的节点类

private int data; // key
    private int dataCount; // no. of keys with equal value stored at this node
    private int treeSize; // no. of keys stored in the subtree rooted at this node
    private BSTNode leftChild;
    private BSTNode rightChild;

Answer 1

我已经实现了一个迭代解决方案。

想法

基本思想是始终尽可能向右移动，因为只要节点尚未针对 n 进行计数，最大值就会在那里。并将我们经过的所有值保存在堆栈中。如果我们不能再向右走并且我们没有将此节点计入 n我们已经找到了树中我们尚未考虑的最大节点。所以在那种情况下，我们可以通过从堆栈中获取节点来计算该值，递减 n并将该节点添加到我们已经考虑过的节点集中。要找到下一个最大值，我们必须检查当前节点是否有左子树，如果有，我们需要在那里继续。如果不是，我们需要返回到我们的父节点，我们通过从堆栈中获取下一个值来做到这一点。然后，此父节点将自动成为下一个最大值。

此处说明了当处于未考虑的最大值时可能出现的这两种情况。

我们处于未被计算的最大节点并且它没有左节点，因此我们需要返回到将成为下一个最大节点的父节点(使用堆栈)。

   Parent
    /  \
   /    \
  x    largest

或者:有一个左子树，我们需要先检查。

   Parent
    /  \
   /    \
  x    largest
         /
        /
  left subtree
     /  \
    /    \

实现

/**
 * Finds the n-th largest key in a given subtree.
 * @param root root node to start from
 * @param n n-th largest key to get, n =< 1 will result in the largest key being returned
 * @return returns n-th larges value, if n <= 1 return largest value
 */
public Node findNthLargestKey(Node root, int n){
    if(root == null) return null;
    if(n < 1) n = 1;
    // early out: if you know how many nodes you have in the tree return if n is bigger than that
    // based on number of nodes compared to n some assumptions could be made to speed up algorithm
    // e.g. n == number of nodes -> get to left-most node and return it
    // if n is close to number of nodes also probably start in left branch instead of all the way on the right side at the biggest node
    var stack = new Stack<Node>();
    // remember nodes that have been visited and have been counted against n
    var done = new HashSet<Integer>();
    // start at root node
    stack.add(root);
    // continue as long as the stack is not empty, if it is n was to big and the n-th largest value could not be found
    while (!stack.empty()){
        // pop next value from the stack (will be root in first iteration)
        current = stack.pop();
        // always try to go as far to the right as possible to get the biggest value that has not yet been counted against n
        while (current != null && !done.contains(current.getKey())){
            stack.add(current);
            current = current.getRight();
        }
        // if we are here we've found the biggest value that has not yet been counted against n
        var prev = stack.pop();
        // if we have found the nth biggest value return
        if(--n == 0){
            return prev;
        }
        // otherwise mark this node as done and counted against n
        done.add(prev.getKey());
        // if node has a left successor, visit it first as this node has no right successors that have not been counted against n already
        if(prev.getLeft() != null) stack.add(prev.getLeft());
    }
    // n-th largest value was not found (n was too big)
    return null;
}

我的节点看起来像这样，当然定义了 getter 和 setter。但是该实现也适用于您的节点，因为具有相同值的节点数与找到第 n 个最大节点无关。即使它们不是，相同的算法也可以工作，但是您需要减少具有相同值的节点数，并且需要将条件调整为 n <= 0。返回。

public class Node {

    private int key;
    private Node right;
    private Node left;
    private Object anyData;

    public Node(int key) {
        this(key, null);
    }

    public Node(int key, Object anyData) {
        this.key = key;
        this.anyData = anyData;
        this.left = null;
        this.right = null;
    }
}

测试

我已经针对随机树测试了我的实现，结果始终是正确的。这Test然而，类只检查根节点的结果，以便能够测试树中每个节点的方法。我还运行了一些测试 n > number of nodes in tree总是必须返回 null对于 not found和较小的子树。

public class Test {

    public static void main(String[] args){
        // values to insert into the tree
        int[] curVals = fillArrayRand(20, 1, 200);

        // Create tree
        BinarySearchTree tree = new BinarySearchTree();
        System.out.println("Tree has been created.");

        // fill tree
        for (var cur: curVals) {
            tree.insertIter(new Node(cur));
        }
        // print values in order of insertion, first value will be the root value
        System.out.println("Tree was filled with the following values: %s".formatted(Arrays.toString(curVals)));
        // print tree in using inorder traversal
        tree.printRec(Traversal.INORDER);

        var sorted = Arrays.stream(curVals).sorted().distinct().toArray();
        // always start at root node; which is the first node that gets inserted
        // find() returns a given node by key
        var startNode = tree.find(curVals[0]);

        // now loop over sorted values (sorted in ascending order -> nth largest is at position n - i in the sorted array)
        for (int i = 0; i < sorted.length; i++) {
            var result = tree.findNthLargestKey(startNode, sorted.length - i);

            // if key in i-th position of sorted array is the same as the key of result => success
            // if result is null, the node was not found (should not happen here as sorted.length - i is never > sorted.length)
            System.out.printf("#%d largest value:\t%d (expected)\t-\t%s (result)\t", sorted.length - i, sorted[i], result == null ? "not found": result.getKey());
            if (result != null && sorted[i] == result.getKey()) {
                System.out.println("SUCCESS");
            } else System.out.println("FAILED");
        }
    }

    public static int[] fillArrayRand(int size, int randStart, int randEnd){
        int[] randArray = new int[size];
        for(int i = 0; i < size; i++){
            randArray[i] = (int)( (randEnd - randStart) * Math.random() + randStart);
        }
        return randArray;
    }
}

预期输出

Tree has been created.
Tree was filled with the following values: [148, 65, 18, 168, 8, 148, 194, 186, 114, 22, 102, 51, 123, 169, 68, 118, 37, 18, 26, 18]
((((n,8,n),18,(n,22,(((n,26,n),37,n),51,n))),65,(((n,68,n),102,n),114,((n,118,n),123,n))),148,(n,168,(((n,169,n),186,n),194,n)))
#17 largest value:  8 (expected)    -   8 (result)  SUCCESS
#16 largest value:  18 (expected)   -   18 (result) SUCCESS
#15 largest value:  22 (expected)   -   22 (result) SUCCESS
#14 largest value:  26 (expected)   -   26 (result) SUCCESS
#13 largest value:  37 (expected)   -   37 (result) SUCCESS
#12 largest value:  51 (expected)   -   51 (result) SUCCESS
#11 largest value:  65 (expected)   -   65 (result) SUCCESS
#10 largest value:  68 (expected)   -   68 (result) SUCCESS
#9 largest value:   102 (expected)  -   102 (result)    SUCCESS
#8 largest value:   114 (expected)  -   114 (result)    SUCCESS
#7 largest value:   118 (expected)  -   118 (result)    SUCCESS
#6 largest value:   123 (expected)  -   123 (result)    SUCCESS
#5 largest value:   148 (expected)  -   148 (result)    SUCCESS
#4 largest value:   168 (expected)  -   168 (result)    SUCCESS
#3 largest value:   169 (expected)  -   169 (result)    SUCCESS
#2 largest value:   186 (expected)  -   186 (result)    SUCCESS
#1 largest value:   194 (expected)  -   194 (result)    SUCCESS

Note: the output of the line with all the parenthesis is the output of the inorder traversal where (left node, parent, right node) and n means null for i. e. no node. The first node that gets inserted is the root node, so it's best to start to read the output from there.

正确性

我应该可以使用循环不变量和归纳来证明算法是正确的，并为每个正确的二叉搜索树和输入产生预期的结果。循环变体(非正式地)将在迭代之后i在外层 while 循环中，我们找到了 i-th 1 <= i <= n 树中的最大节点。我在这里没有这样做，但使用应该很简单的想法。

有效性

我没有做过复杂性分析，但很明显，最好的情况，例如根节点是最大值，我们想要最大值，复杂度是 O(1) .在最坏的情况下它将是 O(n)无论我们搜索哪个节点。该算法当然可以针对某些输入 i 进行改进。 e.如果我们有 n靠近number of nodes在树中，这意味着我们正在搜索一个小值。在这种情况下，从最左边的最小节点开始搜索 (number of nodes - n)-th 会更快。最小值。如果您要实现类似的东西，您当然可以大大提高平均用例运行时间。