基になる構造として AVL ツリーを使用して単純なマップを実装しようとしています。基本構造として二分探索ツリーを使用してマップを実装しましたが、必要に応じてツリーをチェックしてバランスを取る方法を思い描くのに苦労しています。キーと値のペアを入れるときは、ツリーのバランスをチェックして、それに応じて行動する必要があります。これを行う方法がわかりません。MyAVLMap のコードは次のとおりです (二分探索ツリーの実装を利用しています)。どんな助けでも大歓迎です!!
これが私のクラスです：
public class MyAVLMap<K, V> implements BasicMap<K, V> {
// the root of the "tree" that structures the map
private AVLNode root;
// the number of key-value mappings currently in the map
private int numKeys;
/**
* Constructs MyAVLMap object.
*/
public MyAVLMap() {
root = null;
numKeys = 0;
}
/**
* Associates the specified value with the specified
* key in the current map.
*
* @param key The key with which the specified value
* is to be associated.
* @param value The value to be associated with the
* specified key.
*/
public void put(K key, V value){
// input validation
if(key == null || value == null) {
throw new IllegalArgumentException();
}
root = put(root, (Comparable) key, value);
}
// // This helper method adds the specified key-value mapping
// // to the tree rooted at "r".
// @SuppressWarnings("unchecked")
// private AVLNode put(AVLNode r, Comparable key, V value){
// if(r == null) {
// numKeys++;
// return new AVLNode(key, value);
// }
//
// int compare = key.compareTo(r.key);
// if(compare == 0) {
// r.value = value;
// } else if(compare < 0) {
// r.left = put(r.left, key, value);
// } else { // (compare > 0)
// r.right = put(r.right, key, value);
// }
//
// return r;
// }
/**
* Internal method to insert into a subtree.
*
* @param x the item to insert.
* @param t the node that roots the tree.
* @return the new root.
*/
@SuppressWarnings("unchecked")
private AVLNode put(AVLNode r, Comparable key, V value)
{
if(r == null) {
return new AVLNode(key, value);
} else if(key.compareTo(r.key) < 0) {
r.left = put(r.left, key, value);
if((r.left.height - r.right.height == 2) &&
(key.compareTo(r.left.key) < 0)) {
r = rotateWithLeftChild(r);
} else {
r = doubleWithLeftChild(r);
}
} else if(key.compareTo(r.key) > 0 ) {
r.right = put(r.right, key, value);
if((r.right.height - r.left.height == 2) &&
(key.compareTo(r.right.key) > 0)) {
r = rotateWithRightChild(r);
}
else {
r = doubleWithRightChild(r);
}
}
// else: Duplicate; do nothing
r.height = max(r.left.height, r.right.height) + 1;
return r;
}
// This helper method returns the greater of two integers.
private static int max(int n1, int n2)
{
if(n1 > n2) {
return n1;
} else { // left <= right
return n2;
}
}
/**
* Rotate binary tree node with left child.
* For AVL trees, this is a single rotation for case 1.
* Update heights, then return new root.
*/
private AVLNode rotateWithLeftChild(AVLNode root2) {
AVLNode root1 = root2.left;
root2.left = root1.right;
root1.right = root2;
root2.height = max(root2.left.height, root2.right.height) + 1;
root1.height = max(root1.left.height, root2.height) + 1;
return root1;
}
/**
* Rotate binary tree node with right child.
* For AVL trees, this is a single rotation for case 4.
* Update heights, then return new root.
*/
private AVLNode rotateWithRightChild(AVLNode root1) {
AVLNode root2 = root1.right;
root1.right = root2.left;
root2.left = root1;
root1.height = max(root1.left.height, root1.right.height) + 1;
root2.height = max(root2.right.height, root1.height) + 1;
return root2;
}
/**
* Double rotate binary tree node: first left child
* with its right child; then node k3 with new left child.
* For AVL trees, this is a double rotation for case 2.
* Update heights, then return new root.
*/
private AVLNode doubleWithLeftChild(AVLNode r) {
r.left = rotateWithRightChild(r.left);
return rotateWithLeftChild(r);
}
/**
* Double rotate binary tree node: first right child
* with its left child; then node r1 with new right child.
* For AVL trees, this is a double rotation for case 3.
* Update heights, then return new root.
*/
private AVLNode doubleWithRightChild(AVLNode r) {
r.right = rotateWithLeftChild(r.right);
return rotateWithRightChild(r);
}
/**
* Returns the value to which the specified key is mapped,
* or <tt>null</tt> if the specified key is not mapped.
*
* @param key The key whose associated value is to be returned.
* @return The value to which the specified key is mapped,
* or <tt>null</tt> if the specified key is not mapped.
*/
public V get(Object key){
return get(root, (Comparable) key);
}
// This helper method retrieves the value associated with the
// specified key in the tree rooted at "r".
@SuppressWarnings("unchecked")
private V get(AVLNode r, Comparable key){
if(r == null) {
return null;
}
int compare = key.compareTo(r.key);
if(compare == 0) {
return (V) r.value;
} else if(compare < 0) {
return get(r.left, key);
} else { // compare > 0
return get(r.right, key);
}
}
/**
* Returns true if the current map contains a mapping for the
* specified key.
*
* @param key The key whose presence in the map is being tested.
* @return If this map contains a mapping for the specified
* key.
*/
public boolean containsKey(Object key) {
return get((Comparable) key) != null;
}
/**
* Returns true if the current map contains no key-value mappings.
*
* @return If the current map contains no key-value mappings.
*/
public boolean isEmpty() {
return root == null;
}
/**
* Removes all of the mappings from the current map.
*/
public void clear() {
root = null;
numKeys = 0;
}
/**
* Returns the number of key-value mappings in this map
* @return The number of key-value mappings in this map
*/
public int size(){
return numKeys;
}
/**
* Returns the String representation of this map.
*
* @return The String representation of this map.
*/
@Override
public String toString() {
return "(" + subtreeToString(root) + ")";
}
// This helper method returns a String representation of the contents
// of the map for (sub-)tree with root "r".
private String subtreeToString(AVLNode r) {
String str = "";
if(r == null) {
return str;
}
str += r.key + ":" + r.value;
str += " (" + subtreeToString(r.left) + ") (" +
subtreeToString(r.right) + ")";
return str;
}
// This inner class creates each of the node(s) that
// compose the AVL tree structure.
class AVLNode<K, V> {
/**
* The key stored in the node.
*/
public K key;
/**
* The corresponding value associated with a key in the node.
*/
public V value;
/**
* The node to the left of "this" node.
*/
public AVLNode left;
/**
* The node to the right of "this" node.
*/
public AVLNode right;
/**
* The height of "this" node.
*/
public int height;
/**
* Constructs the AVLNode object (four parameters).
*
* @param key The key to be stored in the node.
* @param value The corresponding value to be stored in the node.
* @param left The node to the left of "this" node.
* @param right The node to the right of "this" node.
*/
@SuppressWarnings("unchecked")
public AVLNode(Object key, Object value, AVLNode left, AVLNode right) {
// bind to references
this.key = (K) key;
this.value = (V) value;
this.left = left;
this.right = right;
height = 0;
}
/**
* Constructs the AVLNode (two parameters).
*
* @param key The key to be stored in the node.
* @param value The corresponding value to be stored in the node.
*/
public AVLNode(Object key, Object value) {
// call three parameter constructor
this(key, value, null, null);
height = 0;
}
}
}
そして、これが実装するインターフェースです：
public interface BasicMap<K, V> {
/**
* Associates the specified value with the specified
* key in the current map. Neither key nor value should
* be <tt>null</tt>.
* @param key The key with which the specified value
* is to be associated.
* @param value The value to be associated with the
* specified key.
*/
public void put(K key, V value);
/**
* Returns the value to which the specified key is mapped,
* or <tt>null</tt> if the specified key is not mapped.
* @param key The key whose associated value is to be returned
* @return The value to which the specified key is mapped,
* or <tt>null</tt> if the specified key is not mapped.
*/
public V get(Object key);
/**
* Returns true if the current map contains a mapping for the
* specified key.
* @param key The key whose presence in the map is being tested.
* @return true if this map contains a mapping for the specified
* key.
*/
public boolean containsKey(Object key);
/**
* Returns true if the current map contains no key-value mappings.
* @return true if the current map contains no key-value mappings.
*/
public boolean isEmpty();
/**
* Removes all of the mappings from the current map.
*/
public void clear();
/**
* Returns the number of key-value mappings in this map
* @return The number of key-value mappings in this map
*/
public int size();
/**
* Returns the String representation of this map
* @return The String representation of this map
*/
public String toString();
}