TreeMap.java file:
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 file:
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 file:
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;
}
}
I'm trying to implement a treeMap on my own in Java.
I've written the following code so far.
The methods in TreeMap.java: getMax(), height(), getBalanceFactor(), leftRotate() and rightRotate() are throwing the error: "The method getMax(TreeNode<Pair<K,V>>) in the type Tree<K,V> is not applicable for the arguments (TreeNode<Pair<K,V>>)" same with rest of the above mentioned methods with their respective parameters.
What have I done wrong? How to fix this? Thank you.
CodePudding user response：
Remove the static keyword (static can't call the instance methods and cannot access the instance fields) and don't hide the generic parameters (the class definition already defines them):
From:
private static <K, V> TreeNode<Pair<K, V> > delete(TreeNode<Pair<K, V> > root, Pair<K, V> data)
To:
private TreeNode<Pair<K, V> > delete(TreeNode<Pair<K, V> > root, Pair<K, V> data)
CodePudding user response：
You're getting this compilation error because you've messed around with static and instance methods.
Your method delete is defined as static and you're trying to invoke instance methods from it without the actual class instance:
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
Change the declaration of delete() to:
private TreeNode<Pair<K, V>> delete(TreeNode<Pair<K, V>> root, Pair<K, V> data)
it doesn't need to be static.
Remember, when you're invoking an instance method from another instance method, there's always an implicit reference to this:
foo(); // means this.foo() if foo() is an instance method
But if the enclosing method is static there's no implicit reference to this because static method can be invoked without creating a class instance.