如何在 AVL 树中找到最大值（不是键）？

Question

我构建了一个简单的AVL树如下，每个节点都有键和值。现在我想实现一个方法，可以 return 具有最大值的节点的键。例如，如果我有这样一棵树：

               (7,1)
             /       \
        (4,3)       (13,8)
        /  \       /      \
    (2,4) (6,3) (11,8)      (15,2)
     / \   /      /  \      /     \
(1,9)(3,0)(5,16)(9,2)(12,3)(14,3)(16,5)
                 / \
              (8,19)(10,4)

该方法将 return 8，因为节点 (8,19) 具有最大值。以下是我的 avl 树和节点构造函数。我确实尝试手动实现此方法，但不知何故它不起作用。如果有人能帮助我，我将不胜感激。

public class AVLTreeImp<T extends Comparable<? super T>,V> implements AVLTree<T,V>{
    private Node<T, V> root;
    public class Node<T extends Comparable<? super T>,V> implements AVLTree.Node{
        T key;
        V value;
        Node<T,V> left;
        Node<T,V> right;
        Node<T,V> parent;
        int height;
        public Node(){
            this.key = null;
            this.left = null;
            this.right = null;
            this.parent = null;
            this.height = 0;
            this.value = null;
        }
        public Node(T key, V value, Node<T,V> left, Node<T,V> right){
            this.key = key;
            this.left = left;
            this.right = right;
            this.parent = null;
            this.height = 0;
            this.value = value;
        }
    }

    public AVLTreeImp(){
        this.root = null;
    }
@Override
    public void insert(T key, V value){
        root = insert(root,key,value);

    }
    private Node<T,V> insert(Node<T,V> node, T key, V value){
        if (node == null){
            node = new Node<T,V>(key, value,null,null);
        }else{
            if (key.compareTo(node.key) < 0){
                node.left = insert(node.left, key, value);
                if (!(isBalanced(node))) {
                    if (key.compareTo(node.left.key) < 0) {
                        node = leftLeftRotation(node);
                    } else {
                        node = leftRightRotation(node);
                    }
                }
            }else if (key.compareTo(node.key) > 0){
                node.right = insert(node.right,key,value);
                if (!(isBalanced(node))){
                    if (key.compareTo(node.right.key) > 0){
                        node = rightRightRotation(node);
                    }else{
                        node = rightLeftRotation(node);
                    }
                }
            }
        }
        regenerateHeight(node);
        return node;
    }

下面是我实现的这个方法，不知道有什么问题。

public Integer findMax(){
        Node<Integer,Integer> result = (Node<Integer,Integer>)root;
        result.value = 0;
        return findMax((Node<Integer, Integer>) root,result);
    }
    private Integer findMax(Node<Integer,Integer> node,Node<Integer,Integer> result){
        if (node == null){
            return result.key;
        }
        if (node.value > result.value || 
                (node.value == result.value && node.key.compareTo(result.key) < 0)){
            result = node;
        }
        findMax(node.left,result);
        findMax(node.right,result);
        return result.key;
    }

Answer 1

你有一个平衡的 BST！这意味着像下面这样的操作是有效的，

Insert/Remove
Max/Min 键
会员查询

但事实证明，正如评论所建议的那样，您必须遍历整个树才能找到符合您条件的元素，这是一个 O(N) 操作，不是最优的。更糟糕的是，你的结构是递归的！

可以，

维护一个由您的“值”键控的优先级队列
再建一棵以您的“价值”为关键字的树

它们都比完整的树查找更有效。

但是，没有进一步的上下文，我发现你对树的用法有问题？为什么你的树以你没有操作的东西为键？

Answer 2

您的递归 findMax 方法不正确。您正在分配 result = node; 但这只是本地分配，而不是在调用 findMax(node.left,result); 和 findMax(node.right,result); 时更新结果 .这应该有效：

public Integer findMax(){
    Node<Integer,Integer> result = (Node<Integer,Integer>)root;
    result = findMax((Node<Integer, Integer>) root,result);
    return result.key;
}

private Node<Integer,Integer> findMax(Node<Integer,Integer> node,Node<Integer,Integer> result){
    if (node == null){
        return result;
    }
    if (node.value > result.value || 
            (node.value == result.value && node.key.compareTo(result.key) < 0)){
        result = node;
    }
    result = findMax(node.left,result);
    result = findMax(node.right,result);
    return result;
}

更多关于传递 java 参数的信息 Is Java "pass-by-reference" or "pass-by-value"?

如何在 AVL 树中找到最大值（不是键）？

How to find max value(not key) in an AVL tree?

java

data-structures

avl-tree