java 类型树〈K,V>中的方法getMax(树节点〈Pair〈K,V>>)不适用于参数(树节点〈Pair〈K,V>>)

snz8szmq  于 2022-12-21  发布在  Java
关注(0)|答案(2)|浏览(132)

TreeMap.java 文件:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class TreeMap<K, V> {
    private TreeNode<Pair<K, V> > root;

    TreeMap() {
        root = null;
    }

    public void delete(Pair<K, V> data) {
        root = delete(root, data);
    }

    private static <K, V> TreeNode<Pair<K, V> > delete(TreeNode<Pair<K, V> > root, Pair<K, V> data) {
        if (root == null) {                                                 //  empty tree
            return root;
        }
        if (data.compare(root.data) == 0 ) {                                //  target on left side of tree
            root.left = delete(root.left, data);
        } else if (data.compare(root.data) > 0) {                           //  target on right side of tree
            root.right = delete(root.right, data);
        } else if (root.left == null || root.right == null) {               //  root is target, but less than two children
            root = root.left != null ? root.left : root.right;
        } else {                                                            //  root is target, but two children
            root.data = getMax(root.left);
            root.left = delete(root.left, root.data);
        }
        if (root == null) {
            return root;
        }
        root.height = Math.max(height(root.left), height(root.right) ) + 1; //  update height for balanceFactor purpose
        int rootBalanceFactor = getBalanceFactor(root);
        if (rootBalanceFactor > 1) {                                        //  if left subtree is unbalanced
            int leftBalanceFactor = getBalanceFactor(root.left);
            if (leftBalanceFactor < 0) {                                    //  make sure balanceFactor of left node >= 0
                root.left = leftRotate(root.left);
            }
            root = rightRotate(root);
            return root;
        }
        if (rootBalanceFactor < -1) {                                       //  if right subtree is unbalanced
            int rightBalanceFactor = getBalanceFactor(root.right);
            if (rightBalanceFactor > 0) {                                   //  make sure balanceFactor of right node <= 0
                root.right = rightRotate(root.right);                       
            }
            root = leftRotate(root);
            return root;
        }
        return root;
    }

    private Pair<K, V> getMax(TreeNode<Pair<K, V> > root) {
        if (root == null) {
            return null;
        }
        if (root.right == null) {
            return root.data;
        }
        Pair<K, V> result = getMax(root.right);
        return result;
    }

    public boolean search(Pair<K, V> data) {
        boolean result = search(root, data);
        return result;
    }

    private boolean search(TreeNode<Pair<K, V> > root, Pair<K, V> data) {
        if (root == null) {
            return false;
        }
        if (data.compare(root.data) < 0) {
            boolean result = search(root.left, data);
            return result;
        }
        if (data.compare(root.data) > 0) {
            boolean result = search(root.right, data);
            return result;
        }
        return true;
    }

    public void insert(Pair<K, V> data) {
        root = insert(root, data);
    }

    private TreeNode<Pair<K, V> > insert(TreeNode<Pair<K, V> > root, Pair<K, V> data) {
        if (root == null) {                                                 //  create new node at target location
            return new TreeNode<Pair<K, V> >(data);
        }
        if (data.compare(root.data) < 0) {                                  //  target in left subtree
            root.left = insert(root.left, data);
        } else if (data.compare(root.data) > 0) {                           //  target in right subtree
            root.right = insert(root.right, data);     
        } else {                                                            //  target already exists
            return root;
        }
        root.height = Math.max(height(root.left), height(root.right) ) + 1; //  update height for balanceFactor purpose
        int rootBalanceFactor = getBalanceFactor(root);
        if (rootBalanceFactor > 1) {                                        //  if left subtree is unbalanced
            if (data.compare(root.left.data) > 0) {                         //  LR case
                root.left = leftRotate(root.left);
            }
            root = rightRotate(root);                                       //  right rotation necessary in both cases
            return root;
        }
        if (rootBalanceFactor < -1) {                                       //  if right subtree is unbalanced
            if (data.compare(root.right.data) < 0) {                        //  RL case
                root.right = rightRotate(root.right);
            }
            root = leftRotate(root);                                        //  left rotation necessary in both cases
            return root;
        }
        return root;
    }
    
    private int getBalanceFactor(TreeNode<Pair<K, V> > root) {
        if (root == null) {
            return 0;
        }
        int result = height(root.left) - height(root.right);
        return result;
    }

    private int height(TreeNode<Pair<K, V> > root) {
        if (root == null) {
            return -1;
        }
        return root.height;
    }

    private TreeNode<Pair<K, V> > leftRotate(TreeNode<Pair<K, V> > root) {
        if (root == null) {
            return root;
        }
        if (root.right == null) {
            return root;
        }
        TreeNode<Pair<K, V> > rightChild = root.right;
        root.right = rightChild.left;
        rightChild.left = root;
        root.height = Math.max(height(root.left), height(root.right) ) + 1;
        rightChild.height = Math.max(height(rightChild.left), height(rightChild.right) ) + 1;
        return rightChild;
    }

    private TreeNode<Pair<K, V> > rightRotate(TreeNode<Pair<K, V> > root) {
        if (root == null) {
            return root;
        }
        if (root.left == null) {
            return root;
        }
        TreeNode<Pair<K, V> > leftChild = root.left;
        root.left = leftChild.right;
        leftChild.right = root;
        root.height = Math.max(height(root.left), height(root.right) ) + 1;
        leftChild.height = Math.max(height(leftChild.left), height(leftChild.right) ) + 1;
        return leftChild;
    }
}

Pair.java 文件:

public class Pair<K, V> {
    K key;
    V value;

    Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public int compare(Pair<K, V> pair1) {
        return this.hashCode() - pair1.hashCode();
    }

    @Override
    public int hashCode() {
        return this.key.hashCode();
    }
}

TreeNode.java 文件:

public class TreeNode<T> {
    public T data;
    int height;
    public TreeNode<T> left, right;

    public TreeNode(T data) {
        this.data = data;
        height = 0;
        left = right = null;
    }
}

我正在尝试用Java自己实现一个treeMap。
到目前为止,我已经编写了以下代码。
www.example.com中的方法TreeMap.java:getMax()、height()、getBalanceFactor()、leftRotate()和rightRotate()抛出错误:“类型Tree〈K,V〉中的方法getMax(TreeNode〈Pair〈K,V〉〉)不适用于参数(TreeNode〈Pair〈K,V〉〉)”与上述方法的其余部分及其各自的参数相同。
我做错什么了?怎么补救?谢谢。

wj8zmpe1

wj8zmpe11#

删除static关键字(static不能调用示例方法,也不能访问示例字段),并且不要隐藏泛型参数(类定义已经定义了它们):
发件人:

private static <K, V> TreeNode<Pair<K, V> > delete(TreeNode<Pair<K, V> > root, Pair<K, V> data)

收件人:

private TreeNode<Pair<K, V> > delete(TreeNode<Pair<K, V> > root, Pair<K, V> data)
hiz5n14c

hiz5n14c2#

您得到这个编译错误是因为您在static和示例方法上做了手脚。
你的delete方法被定义为static,你试图在没有实际类示例的情况下从它调用示例方法:

root.data = getMax(root.left); // getMax() - is an instance method
...
root.height = Math.max(height(root.left), height(root.right) ) + 1; // hight() - is an instance method
...
root.left = leftRotate(root.left); // leftRotate() - is an instance method

delete()的声明更改为:

private TreeNode<Pair<K, V>> delete(TreeNode<Pair<K, V>> root, Pair<K, V> data)

它不需要是静态的。
记住,当你从一个示例方法调用另一个示例方法时,总是有一个对this的隐式引用:

foo(); // means this.foo() if foo() is an instance method

但是,如果封闭方法是static,则没有对this的隐式引用,因为可以在不创建类示例的情况下调用static方法。

相关问题