Return to Question

public class AVLTreeDictionary<K extends Comparable<K>,V> implements Dictionary<K,V>
{
 /* Duplicate keys handling by overwriting value. Null keys
 * unsupported. It is assumed they will not be passed in.
 * Duplicate and null values supported.
 */
 private Node root;
 public AVLTreeDictionary()
 {
 root = null;
 }
 public V insert(K key, V value)
 {
 /* Adds a new entry to the tree. If the key already exists
 * overwrites the value and returns the old value. Performs
 * AVL rebalancing afterwords.
 */
 Path path = getPath(key);
 if(path.child() != null)
 {
 V previous = path.child().value;
 path.child().value = value;
 return previous;
 }
 path.setChild(new Node(key, value));
 path.pop();
 balancePath(path);
 return null;
 }
 public V delete(K key)
 {
 /* Deletes an entry from the tree if it exists.
 * If 0 children: Deletes entry.
 * If 1 child: Replaces entry with child.
 * If 2 children: Randomly selected between successor/predecessor
 * and copies values then deletes succ/pred and replaces it with
 * its one child if it exists. Performs AVL rebalancing afterwords.
 */
 Path path = getPath(key);
 Node node = path.child();
 if(node == null)
 {
 return null;
 }
 if(node.right == null)
 {
 path.setChild(node.left);
 }
 else if(node.left == null)
 {
 path.setChild(node.right);
 }
 else
 {
 boolean direction = Math.random() >= 0.5;
 path.push(direction);
 while(path.grandChild(!direction) != null)
 {
 path.push(!direction);
 }
 node.key = path.child().key;
 node.value = path.child().value;
 path.setChild(path.grandChild(direction));
 }
 path.pop();
 balancePath(path);
 return null;
 }
 public V search(K key)
 {
 // Standard binary search.
 Node search = root;
 while(search != null)
 {
 int compare = key.compareTo(search.key);
 if(compare == 0)
 {
 return search.value;
 }
 search = search.child(compare > 0);
 }
 return null;
 }
 private Path getPath(K key)
 {
 /* Returns a path from the root to the key specified or the
 * position it would be added in if it does not exist. Includes
 * the root edge.
 */
 Path path = new Path(new Edge(null, false));
 while(true)
 {
 if(path.child() == null)
 {
 return path;
 }
 int compare = key.compareTo(path.child().key);
 if(compare == 0)
 {
 return path;
 }
 path.push(compare > 0);
 }
 }
 private void rotate(Edge edge, boolean direction)
 {
 /* Rotates the child of the edge with its child
 * in the direction specified. It is assumed both the child
 * and grandchild are not null.
 */
 Edge rotate = new Edge(edge.child(), direction);
 edge.setChild(rotate.child());
 rotate.setChild(rotate.grandChild(!direction));
 edge.child().setChild(rotate.parent, !direction);
 }
 private void balancePath(Path path)
 {
 /* Follows a path up the tree performing AVL rebalancing
 * and height updates as needed.
 */
 while(path.peek() != null)
 {
 int previous = path.child().height;
 if(Math.abs(path.child().balance()) > 1)
 {
 boolean direction = path.child().balance() > 0;
 if(path.child().balance() * path.grandChild(direction).balance() < 0)
 {
 path.push(direction);
 rotate(path.peek(), !direction);
 path.pop().grandChild(direction).updateHeight();
 }
 rotate(path.peek(), direction);
 path.grandChild(!direction).updateHeight();
 }
 if(path.pop().child().updateHeight() == previous)
 {
 break;
 }
 }
 }
 private class Node
 {
 /* This node class has get/set child functions that use a variable
 * to select which child. This allows us to avoid writing duplicate
 * code for the mirror image of operations. The balance of a node
 * refers to the difference in height between the right and left
 * subtrees. A positive balance is right-heavy, negative is left-heavy.
 * False = Left, True = Right.
 */
 public Node left;
 public Node right;
 public K key;
 public V value;
 public int height;
 public Node(K key, V value)
 {
 left = null;
 right = null;
 this.key = key;
 this.value = value;
 height = 0;
 }
 public Node child(boolean direction)
 {
 if(direction)
 {
 return right;
 }
 else
 {
 return left;
 }
 }
 public void setChild(Node child, boolean direction)
 {
 if(direction)
 {
 right = child;
 }
 else
 {
 left = child;
 }
 }
 public int balance()
 {
 return (right != null ? right.height : -1) - (left != null ? left.height : -1);
 }
 public int updateHeight()
 {
 height = Math.max((left != null ? left.height : -1), (right != null ? right.height : -1)) + 1;
 return height;
 }
 }
 private class Edge
 {
 /* An edge is a connection between two nodes. It is represented by the parent
 * node and the directon to the child node. An edge may point to a null child.
 * There is also a special edge called the root edge which has the root as its
 * child, it is represented by a null parent. This representation allows us
 * to avoid writing duplicate code for handling operations involving the root.
 */
 public Node parent;
 public boolean direction;
 public Edge(Node parent, boolean direction)
 {
 this.parent = parent;
 this.direction = direction;
 }
 public Node child()
 {
 if(parent == null)
 {
 return root;
 }
 else
 {
 return parent.child(direction);
 }
 }
 public void setChild(Node child)
 {
 if(parent == null)
 {
 root = child;
 }
 else
 {
 parent.setChild(child, direction);
 }
 }
 public Node grandChild(boolean direction)
 {
 /* Returns the grandchild in the direction specified.
 * It is assumed this will not be called if the child
 * is null.
 */
 return child().child(direction);
 }
 }
 private class Path
 {
 /* A path is a list of adjacent edges going down the tree. All operations
 * are performed on the bottom-most edge of the path.
 */
 private Stack<Edge> stack;
 public Path(Edge edge)
 {
 stack = new LinkedListStack<Edge>();
 stack.push(edge);
 }
 public void push(boolean direction)
 {
 /* Extends the path downwards in the direction specified. It is
 * assumed this will not be called if the path points to a null
 * child.
 */
 stack.push(new Edge(child(), direction));
 }
 public Edge pop()
 {
 /* Retracts the bottom of the path upwards one edge and
 * returns the deleted edge.
 */
 return stack.pop();
 }
 public Edge peek()
 {
 return stack.peek();
 }
 public Node child()
 {
 return stack.peek().child();
 }
 public void setChild(Node child)
 {
 stack.peek().setChild(child);
 }
 public Node grandChild(boolean direction)
 {
 return stack.peek().grandChild(direction);
 }
 }
 public String toString()
 {
 return toString(root, "", false);
 }
 public String toString(Node node, String prefix, boolean direction)
 {
 String string = "";
 if(node != null)
 {
 string += toString(node.right, prefix + (direction ? " " : "│ "), true);
 string += prefix + (direction ? "┌─────" : "└─────") + String.format("(%s,%s)\n", node.key, node.value);
 string += toString(node.left, prefix + (direction ? "│ " : " "), false);
 }
 return string;
 }
}

public class AVLTreeDictionary<K extends Comparable<K>,V> implements Dictionary<K,V>
{
 /* Duplicate keys handling by overwriting value. Null keys
 * unsupported. It is assumed they will not be passed in.
 * Duplicate and null values supported.
 */
 private Node root;
 public AVLTreeDictionary()
 {
 root = null;
 }
 public V insert(K key, V value)
 {
 /* Adds a new entry to the tree. If the key already exists
 * overwrites the value and returns the old value. Performs
 * AVL rebalancing afterwords.
 */
 Path path = getPath(key);
 if(path.child() != null)
 {
 V previous = path.child().value;
 path.child().value = value;
 return previous;
 }
 path.setChild(new Node(key, value));
 path.pop();
 balancePath(path);
 return null;
 }
 public V delete(K key)
 {
 /* Deletes an entry from the tree if it exists.
 * If 0 children: Deletes entry.
 * If 1 child: Replaces entry with child.
 * If 2 children: Randomly selected between successor/predecessor
 * and copies values then deletes succ/pred and replaces it with
 * its one child if it exists. Performs AVL rebalancing afterwords.
 */
 Path path = getPath(key);
 Node node = path.child();
 if(node == null)
 {
 return null;
 }
 if(node.right == null)
 {
 path.setChild(node.left);
 }
 else if(node.left == null)
 {
 path.setChild(node.right);
 }
 else
 {
 boolean direction = Math.random() >= 0.5;
 path.push(direction);
 while(path.grandChild(!direction) != null)
 {
 path.push(!direction);
 }
 node.key = path.child().key;
 node.value = path.child().value;
 path.setChild(path.grandChild(direction));
 }
 path.pop();
 balancePath(path);
 return null;
 }
 public V search(K key)
 {
 // Standard binary search.
 Node search = root;
 while(search != null)
 {
 int compare = key.compareTo(search.key);
 if(compare == 0)
 {
 return search.value;
 }
 search = search.child(compare > 0);
 }
 return null;
 }
 private Path getPath(K key)
 {
 /* Returns a path from the root to the key specified or the
 * position it would be added in if it does not exist. Includes
 * the root edge.
 */
 Path path = new Path(new Edge(null, false));
 while(true)
 {
 if(path.child() == null)
 {
 return path;
 }
 int compare = key.compareTo(path.child().key);
 if(compare == 0)
 {
 return path;
 }
 path.push(compare > 0);
 }
 }
 private void rotate(Edge edge, boolean direction)
 {
 /* Rotates the child of the edge with its child
 * in the direction specified. It is assumed both the child
 * and grandchild are not null.
 */
 Edge rotate = new Edge(edge.child(), direction);
 edge.setChild(rotate.child());
 rotate.setChild(rotate.grandChild(!direction));
 edge.child().setChild(rotate.parent, !direction);
 }
 private int height(Node node)
 {
 if(node == null)
 {
 return -1;
 }
 else
 {
 return node.height;
 }
 }
 private void balancePath(Path path)
 {
 /* Follows a path up the tree performing AVL rebalancing
 * and height updates as needed.
 */
 while(path.peek() != null)
 {
 int previous = path.child().height;
 if(Math.abs(path.child().balance()) > 1)
 {
 boolean direction = path.child().balance() > 0;
 if(path.child().balance() * path.grandChild(direction).balance() < 0)
 {
 path.push(direction);
 rotate(path.peek(), !direction);
 path.pop().grandChild(direction).updateHeight();
 }
 rotate(path.peek(), direction);
 path.grandChild(!direction).updateHeight();
 }
 if(path.pop().child().updateHeight() == previous)
 {
 break;
 }
 }
 }
 private class Node
 {
 /* This node class has get/set child functions that use a variable
 * to select which child. This allows us to avoid writing duplicate
 * code for the mirror image of operations. The balance of a node
 * refers to the difference in height between the right and left
 * subtrees. A positive balance is right-heavy, negative is left-heavy.
 * False = Left, True = Right.
 */
 public Node left;
 public Node right;
 public K key;
 public V value;
 public int height;
 public Node(K key, V value)
 {
 left = null;
 right = null;
 this.key = key;
 this.value = value;
 height = 0;
 }
 public Node child(boolean direction)
 {
 if(direction)
 {
 return right;
 }
 else
 {
 return left;
 }
 }
 public void setChild(Node child, boolean direction)
 {
 if(direction)
 {
 right = child;
 }
 else
 {
 left = child;
 }
 }
 public int balance()
 {
 return height(right) - height(left);
 }
 public int updateHeight()
 {
 height = Math.max(height(right), height(left)) + 1;
 return height;
 }
 }
 private class Edge
 {
 /* An edge is a connection between two nodes. It is represented by the parent
 * node and the directon to the child node. An edge may point to a null child.
 * There is also a special edge called the root edge which has the root as its
 * child, it is represented by a null parent. This representation allows us
 * to avoid writing duplicate code for handling operations involving the root.
 */
 public Node parent;
 public boolean direction;
 public Edge(Node parent, boolean direction)
 {
 this.parent = parent;
 this.direction = direction;
 }
 public Node child()
 {
 if(parent == null)
 {
 return root;
 }
 else
 {
 return parent.child(direction);
 }
 }
 public void setChild(Node child)
 {
 if(parent == null)
 {
 root = child;
 }
 else
 {
 parent.setChild(child, direction);
 }
 }
 public Node grandChild(boolean direction)
 {
 /* Returns the grandchild in the direction specified.
 * It is assumed this will not be called if the child
 * is null.
 */
 return child().child(direction);
 }
 }
 private class Path
 {
 /* A path is a list of adjacent edges going down the tree. All operations
 * are performed on the bottom-most edge of the path.
 */
 private Stack<Edge> stack;
 public Path(Edge edge)
 {
 stack = new LinkedListStack<Edge>();
 stack.push(edge);
 }
 public void push(boolean direction)
 {
 /* Extends the path downwards in the direction specified. It is
 * assumed this will not be called if the path points to a null
 * child.
 */
 stack.push(new Edge(child(), direction));
 }
 public Edge pop()
 {
 /* Retracts the bottom of the path upwards one edge and
 * returns the deleted edge.
 */
 return stack.pop();
 }
 public Edge peek()
 {
 return stack.peek();
 }
 public Node child()
 {
 return stack.peek().child();
 }
 public void setChild(Node child)
 {
 stack.peek().setChild(child);
 }
 public Node grandChild(boolean direction)
 {
 return stack.peek().grandChild(direction);
 }
 }
 public String toString()
 {
 return toString(root, "", false);
 }
 public String toString(Node node, String prefix, boolean direction)
 {
 String string = "";
 if(node != null)
 {
 string += toString(node.right, prefix + (direction ? " " : "│ "), true);
 string += prefix + (direction ? "┌─────" : "└─────") + String.format("(%s,%s)\n", node.key, node.value);
 string += toString(node.left, prefix + (direction ? "│ " : " "), false);
 }
 return string;
 }
}

public class AVLTreeDictionary<K extends Comparable<K>,V> implements Dictionary<K,V>
{
 /* Duplicate keys handling by overwriting value. Null keys
 * unsupported. It is assumed they will not be passed in.
 * Duplicate and null values supported.
 */
 private Node root;
 public AVLTreeDictionary()
 {
 root = null;
 }
 public V insert(K key, V value)
 {
 /* Adds a new entry to the tree. If the key already exists
 * overwrites the value and returns the old value. Performs
 * AVL rebalancing afterwords.
 */
 Path path = getPath(key);
 if(path.child() != null)
 {
 V previous = path.child().value;
 path.child().value = value;
 return previous;
 }
 path.setChild(new Node(key, value));
 path.pop();
 balancePath(path);
 return null;
 }
 public V delete(K key)
 {
 /* Deletes an entry from the tree if it exists.
 * If 0 children: Deletes entry.
 * If 1 child: Replaces entry with child.
 * If 2 children: Randomly selected between successor/predecessor
 * and copies values then deletes succ/pred and replaces it with
 * its one child if it exists. Performs AVL rebalancing afterwords.
 */
 Path path = getPath(key);
 Node node = path.child();
 if(node == null)
 {
 return null;
 }
 if(node.right == null)
 {
 path.setChild(node.left);
 }
 else if(node.left == null)
 {
 path.setChild(node.right);
 }
 else
 {
 boolean direction = Math.random() >= 0.5;
 path.push(direction);
 while(path.grandChild(!direction) != null)
 {
 path.push(!direction);
 }
 node.key = path.child().key;
 node.value = path.child().value;
 path.setChild(path.grandChild(direction));
 }
 path.pop();
 balancePath(path);
 return null;
 }
 public V search(K key)
 {
 // Standard binary search.
 Node search = root;
 while(search != null)
 {
 int compare = key.compareTo(search.key);
 if(compare == 0)
 {
 return search.value;
 }
 search = search.child(compare > 0);
 }
 return null;
 }
 private Path getPath(K key)
 {
 /* Returns a path from the root to the key specified or the
 * position it would be added in if it does not exist. Includes
 * the root edge.
 */
 Path path = new Path(new Edge(null, false));
 while(true)
 {
 if(path.child() == null)
 {
 return path;
 }
 int compare = key.compareTo(path.child().key);
 if(compare == 0)
 {
 return path;
 }
 path.push(compare > 0);
 }
 }
 private void rotate(Edge edge, boolean direction)
 {
 /* Rotates the child of the edge with its child
 * in the direction specified. It is assumed both the child
 * and grandchild are not null.
 */
 Edge rotate = new Edge(edge.child(), direction);
 edge.setChild(rotate.child());
 rotate.setChild(rotate.grandChild(!direction));
 edge.child().setChild(rotate.parent, !direction);
 }
 private void balancePath(Path path)
 {
 /* Follows a path up the tree performing AVL rebalancing
 * and height updates as needed.
 */
 while(path.peek() != null)
 {
 if(Math.abs(path.child().balance()) > 1)
 {
 boolean direction = path.child().balance() > 0;
 if(path.child().balance() * path.grandChild(direction).balance() < 0)
 {
 path.push(direction);
 rotate(path.peek(), !direction);
 path.pop().grandChild(direction).updateHeight();
 }
 rotate(path.peek(), direction);
 path.grandChild(!direction).updateHeight();
 }
 if(!path.pop().child().updateHeight())
 {
 break;
 }
 }
 }
 private class Node
 {
 /* This node class has get/set child functions that use a variable
 * to select which child. This allows us to avoid writing duplicate
 * code for the mirror image of operations. The balance of a node
 * refers to the difference in height between the right and left
 * subtrees. A positive balance is right-heavy, negative is left-heavy.
 * False = Left, True = Right.
 */
 public Node left;
 public Node right;
 public K key;
 public V value;
 public int height;
 public Node(K key, V value)
 {
 left = null;
 right = null;
 this.key = key;
 this.value = value;
 height = 0;
 }
 public Node child(boolean direction)
 {
 if(direction)
 {
 return right;
 }
 else
 {
 return left;
 }
 }
 public void setChild(Node child, boolean direction)
 {
 if(direction)
 {
 right = child;
 }
 else
 {
 left = child;
 }
 }
 public int balance()
 {
 return (right != null ? right.height : -1) - (left != null ? left.height : -1);
 }
 public boolean updateHeight()
 {
 // Returns true if the height changed.
 int previous = height;
 height = Math.max((left != null ? left.height : -1), (right != null ? right.height : -1)) + 1;
 return height != previous;
 }
 }
 private class Edge
 {
 /* An edge is a connection between two nodes. It is represented by the parent
 * node and the directon to the child node. An edge may point to a null child.
 * There is also a special edge called the root edge which has the root as its
 * child, it is represented by a null parent. This representation allows us
 * to avoid writing duplicate code for handling operations involving the root.
 */
 public Node parent;
 public boolean direction;
 public Edge(Node parent, boolean direction)
 {
 this.parent = parent;
 this.direction = direction;
 }
 public Node child()
 {
 if(parent == null)
 {
 return root;
 }
 else
 {
 return parent.child(direction);
 }
 }
 public void setChild(Node child)
 {
 if(parent == null)
 {
 root = child;
 }
 else
 {
 parent.setChild(child, direction);
 }
 }
 public Node grandChild(boolean direction)
 {
 /* Returns the grandchild in the direction specified.
 * It is assumed this will not be called if the child
 * is null.
 */
 return child().child(direction);
 }
 }
 private class Path
 {
 /* A path is a list of adjacent edges going down the tree. All operations
 * are performed on the bottom-most edge of the path.
 */
 private Stack<Edge> stack;
 public Path(Edge edge)
 {
 stack = new LinkedListStack<Edge>();
 stack.push(edge);
 }
 public void push(boolean direction)
 {
 /* Extends the path downwards in the direction specified. It is
 * assumed this will not be called if the path points to a null
 * child.
 */
 stack.push(new Edge(child(), direction));
 }
 public Edge pop()
 {
 /* Retracts the bottom of the path upwards one edge and
 * returns the deleted edge.
 */
 return stack.pop();
 }
 public Edge peek()
 {
 return stack.peek();
 }
 public Node child()
 {
 return stack.peek().child();
 }
 public void setChild(Node child)
 {
 stack.peek().setChild(child);
 }
 public Node grandChild(boolean direction)
 {
 return stack.peek().grandChild(direction);
 }
 }
 public String toString()
 {
 return toString(root, "", false);
 }
 public String toString(Node node, String prefix, boolean direction)
 {
 String string = "";
 if(node != null)
 {
 string += toString(node.right, prefix + (direction ? " " : "│ "), true);
 string += prefix + (direction ? "┌─────" : "└─────") + String.format("(%s,%s)\n", node.key, node.value);
 string += toString(node.left, prefix + (direction ? "│ " : " "), false);
 }
 return string;
 }
}

public class AVLTreeDictionary<K extends Comparable<K>,V> implements Dictionary<K,V>
{
 /* Duplicate keys handling by overwriting value. Null keys
 * unsupported. It is assumed they will not be passed in.
 * Duplicate and null values supported.
 */
 private Node root;
 public AVLTreeDictionary()
 {
 root = null;
 }
 public V insert(K key, V value)
 {
 /* Adds a new entry to the tree. If the key already exists
 * overwrites the value and returns the old value. Performs
 * AVL rebalancing afterwords.
 */
 Path path = getPath(key);
 if(path.child() != null)
 {
 V previous = path.child().value;
 path.child().value = value;
 return previous;
 }
 path.setChild(new Node(key, value));
 path.pop();
 balancePath(path);
 return null;
 }
 public V delete(K key)
 {
 /* Deletes an entry from the tree if it exists.
 * If 0 children: Deletes entry.
 * If 1 child: Replaces entry with child.
 * If 2 children: Randomly selected between successor/predecessor
 * and copies values then deletes succ/pred and replaces it with
 * its one child if it exists. Performs AVL rebalancing afterwords.
 */
 Path path = getPath(key);
 Node node = path.child();
 if(node == null)
 {
 return null;
 }
 if(node.right == null)
 {
 path.setChild(node.left);
 }
 else if(node.left == null)
 {
 path.setChild(node.right);
 }
 else
 {
 boolean direction = Math.random() >= 0.5;
 path.push(direction);
 while(path.grandChild(!direction) != null)
 {
 path.push(!direction);
 }
 node.key = path.child().key;
 node.value = path.child().value;
 path.setChild(path.grandChild(direction));
 }
 path.pop();
 balancePath(path);
 return null;
 }
 public V search(K key)
 {
 // Standard binary search.
 Node search = root;
 while(search != null)
 {
 int compare = key.compareTo(search.key);
 if(compare == 0)
 {
 return search.value;
 }
 search = search.child(compare > 0);
 }
 return null;
 }
 private Path getPath(K key)
 {
 /* Returns a path from the root to the key specified or the
 * position it would be added in if it does not exist. Includes
 * the root edge.
 */
 Path path = new Path(new Edge(null, false));
 while(true)
 {
 if(path.child() == null)
 {
 return path;
 }
 int compare = key.compareTo(path.child().key);
 if(compare == 0)
 {
 return path;
 }
 path.push(compare > 0);
 }
 }
 private void rotate(Edge edge, boolean direction)
 {
 /* Rotates the child of the edge with its child
 * in the direction specified. It is assumed both the child
 * and grandchild are not null.
 */
 Edge rotate = new Edge(edge.child(), direction);
 edge.setChild(rotate.child());
 rotate.setChild(rotate.grandChild(!direction));
 edge.child().setChild(rotate.parent, !direction);
 }
 private void balancePath(Path path)
 {
 /* Follows a path up the tree performing AVL rebalancing
 * and height updates as needed.
 */
 while(path.peek() != null)
 {
 int previous = path.child().height;
 if(Math.abs(path.child().balance()) > 1)
 {
 boolean direction = path.child().balance() > 0;
 if(path.child().balance() * path.grandChild(direction).balance() < 0)
 {
 path.push(direction);
 rotate(path.peek(), !direction);
 path.pop().grandChild(direction).updateHeight();
 }
 rotate(path.peek(), direction);
 path.grandChild(!direction).updateHeight();
 }
 if(path.pop().child().updateHeight() == previous)
 {
 break;
 }
 }
 }
 private class Node
 {
 /* This node class has get/set child functions that use a variable
 * to select which child. This allows us to avoid writing duplicate
 * code for the mirror image of operations. The balance of a node
 * refers to the difference in height between the right and left
 * subtrees. A positive balance is right-heavy, negative is left-heavy.
 * False = Left, True = Right.
 */
 public Node left;
 public Node right;
 public K key;
 public V value;
 public int height;
 public Node(K key, V value)
 {
 left = null;
 right = null;
 this.key = key;
 this.value = value;
 height = 0;
 }
 public Node child(boolean direction)
 {
 if(direction)
 {
 return right;
 }
 else
 {
 return left;
 }
 }
 public void setChild(Node child, boolean direction)
 {
 if(direction)
 {
 right = child;
 }
 else
 {
 left = child;
 }
 }
 public int balance()
 {
 return (right != null ? right.height : -1) - (left != null ? left.height : -1);
 }
 public int updateHeight()
 {
 height = Math.max((left != null ? left.height : -1), (right != null ? right.height : -1)) + 1;
 return height;
 }
 }
 private class Edge
 {
 /* An edge is a connection between two nodes. It is represented by the parent
 * node and the directon to the child node. An edge may point to a null child.
 * There is also a special edge called the root edge which has the root as its
 * child, it is represented by a null parent. This representation allows us
 * to avoid writing duplicate code for handling operations involving the root.
 */
 public Node parent;
 public boolean direction;
 public Edge(Node parent, boolean direction)
 {
 this.parent = parent;
 this.direction = direction;
 }
 public Node child()
 {
 if(parent == null)
 {
 return root;
 }
 else
 {
 return parent.child(direction);
 }
 }
 public void setChild(Node child)
 {
 if(parent == null)
 {
 root = child;
 }
 else
 {
 parent.setChild(child, direction);
 }
 }
 public Node grandChild(boolean direction)
 {
 /* Returns the grandchild in the direction specified.
 * It is assumed this will not be called if the child
 * is null.
 */
 return child().child(direction);
 }
 }
 private class Path
 {
 /* A path is a list of adjacent edges going down the tree. All operations
 * are performed on the bottom-most edge of the path.
 */
 private Stack<Edge> stack;
 public Path(Edge edge)
 {
 stack = new LinkedListStack<Edge>();
 stack.push(edge);
 }
 public void push(boolean direction)
 {
 /* Extends the path downwards in the direction specified. It is
 * assumed this will not be called if the path points to a null
 * child.
 */
 stack.push(new Edge(child(), direction));
 }
 public Edge pop()
 {
 /* Retracts the bottom of the path upwards one edge and
 * returns the deleted edge.
 */
 return stack.pop();
 }
 public Edge peek()
 {
 return stack.peek();
 }
 public Node child()
 {
 return stack.peek().child();
 }
 public void setChild(Node child)
 {
 stack.peek().setChild(child);
 }
 public Node grandChild(boolean direction)
 {
 return stack.peek().grandChild(direction);
 }
 }
 public String toString()
 {
 return toString(root, "", false);
 }
 public String toString(Node node, String prefix, boolean direction)
 {
 String string = "";
 if(node != null)
 {
 string += toString(node.right, prefix + (direction ? " " : "│ "), true);
 string += prefix + (direction ? "┌─────" : "└─────") + String.format("(%s,%s)\n", node.key, node.value);
 string += toString(node.left, prefix + (direction ? "│ " : " "), false);
 }
 return string;
 }
}

public class AVLTreeDictionary<K extends Comparable<K>,V> implements Dictionary<K,V>
{
 /* Duplicate keys handling by overwriting value. Null keys
 * unsupported. It is assumed they will not be passed in.
 * Duplicate and null values supported.
 */
 private Node root;
 public AVLTreeDictionary()
 {
 root = null;
 }
 public V insert(K key, V value)
 {
 /* Adds a new entry to the tree. If the key already exists
 * overwrites the value and returns the old value. Performs
 * AVL rebalancing afterwords.
 */
 Path path = getPath(key);
 if(path.child() != null)
 {
 V previous = path.child().value;
 path.child().value = value;
 return previous;
 }
 path.setChild(new Node(key, value));
 path.pop();
 balancePath(path);
 return null;
 }
 public V delete(K key)
 {
 /* Deletes an entry from the tree if it exists.
 * If 0 children: Deletes entry.
 * If 1 child: Replaces entry with child.
 * If 2 children: Randomly selected between successor/predecessor
 * and copies values then deletes succ/pred and replaces it with
 * its one child if it exists. Performs AVL rebalancing afterwords.
 */
 Path path = getPath(key);
 Node node = path.child();
 if(node == null)
 {
 return null;
 }
 if(node.right == null)
 {
 path.setChild(node.left);
 }
 else if(node.left == null)
 {
 path.setChild(node.right);
 }
 else
 {
 boolean direction = Math.random() >= 0.5;
 path.push(direction);
 while(path.grandChild(!direction) != null)
 {
 path.push(!direction);
 }
 node.key = path.child().key;
 node.value = path.child().value;
 path.setChild(path.grandChild(direction));
 }
 path.pop();
 balancePath(path);
 return null;
 }
 public V search(K key)
 {
 // Standard binary search.
 Node search = root;
 while(search != null)
 {
 int compare = key.compareTo(search.key);
 if(compare == 0)
 {
 return search.value;
 }
 search = search.child(compare > 0);
 }
 return null;
 }
 private Path getPath(K key)
 {
 /* Returns a path from the root to the key specified or the
 * position it would be added in if it does not exist. Includes
 * the root edge.
 */
 Path path = new Path(new Edge(null, false));
 while(true)
 {
 if(path.child() == null)
 {
 return path;
 }
 int compare = key.compareTo(path.child().key);
 if(compare == 0)
 {
 return path;
 }
 path.push(compare > 0);
 }
 }
 private void rotate(Edge edge, boolean direction)
 {
 /* Rotates the child of the edge with its child
 * in the direction specified. It is assumed both the child
 * and grandchild are not null.
 */
 Edge rotate = new Edge(edge.child(), direction);
 edge.setChild(rotate.child());
 rotate.setChild(rotate.grandChild(!direction));
 edge.child().setChild(rotate.parent, !direction);
 }
 private void balancePath(Path path)
 {
 /* Follows a path up the tree performing AVL rebalancing
 * and height updates as needed.
 */
 while(path.peek() != null)
 {
 if(Math.abs(path.child().balance()) > 1)
 {
 boolean direction = path.child().balance() > 0;
 if(path.child().balance() * path.grandChild(direction).balance() < 0)
 {
 path.push(direction);
 rotate(path.peek(), !direction);
 path.pop().grandChild(direction).updateHeight();
 }
 rotate(path.peek(), direction);
 path.grandChild(!direction).updateHeight();
 }
 path.pop().child().updateHeight();
 }
 }
 private class Node
 {
 /* This node class has get/set child functions that use a variable
 * to select which child. This allows us to avoid writing duplicate
 * code for the mirror image of operations. The balance of a node
 * refers to the difference in height between the right and left
 * subtrees. A positive balance is right-heavy, negative is left-heavy.
 * False = Left, True = Right.
 */
 public Node left;
 public Node right;
 public K key;
 public V value;
 public int height;
 public Node(K key, V value)
 {
 left = null;
 right = null;
 this.key = key;
 this.value = value;
 height = 0;
 }
 public Node child(boolean direction)
 {
 if(direction)
 {
 return right;
 }
 else
 {
 return left;
 }
 }
 public void setChild(Node child, boolean direction)
 {
 if(direction)
 {
 right = child;
 }
 else
 {
 left = child;
 }
 }
 public int balance()
 {
 return (right != null ? right.height : -1) - (left != null ? left.height : -1);
 }
 public void updateHeight()
 {
 height = Math.max((left != null ? left.height : -1), (right != null ? right.height : -1)) + 1;
 }
 }
 private class Edge
 {
 /* An edge is a connection between two nodes. It is represented by the parent
 * node and the directon to the child node. An edge may point to a null child.
 * There is also a special edge called the root edge which has the root as its
 * child, it is represented by a null parent. This representation allows us
 * to avoid writing duplicate code for handling operations involving the root.
 */
 public Node parent;
 public boolean direction;
 public Edge(Node parent, boolean direction)
 {
 this.parent = parent;
 this.direction = direction;
 }
 public Node child()
 {
 if(parent == null)
 {
 return root;
 }
 else
 {
 return parent.child(direction);
 }
 }
 public void setChild(Node child)
 {
 if(parent == null)
 {
 root = child;
 }
 else
 {
 parent.setChild(child, direction);
 }
 }
 public Node grandChild(boolean direction)
 {
 /* Returns the grandchild in the direction specified.
 * It is assumed this will not be called if the child
 * is null.
 */
 return child().child(direction);
 }
 }
 private class Path
 {
 /* A path is a list of adjacent edges going down the tree. All operations
 * are performed on the bottom-most edge of the path.
 */
 private Stack<Edge> stack;
 public Path(Edge edge)
 {
 stack = new LinkedListStack<Edge>();
 stack.push(edge);
 }
 public void push(boolean direction)
 {
 /* Extends the path downwards in the direction specified. It is
 * assumed this will not be called if the path points to a null
 * child.
 */
 stack.push(new Edge(child(), direction));
 }
 public Edge pop()
 {
 /* Retracts the bottom of the path upwards one edge and
 * returns the deleted edge.
 */
 return stack.pop();
 }
 public Edge peek()
 {
 return stack.peek();
 }
 public Node child()
 {
 return stack.peek().child();
 }
 public void setChild(Node child)
 {
 stack.peek().setChild(child);
 }
 public Node grandChild(boolean direction)
 {
 return stack.peek().grandChild(direction);
 }
 }
 public String toString()
 {
 return toString(root, "", false);
 }
 public String toString(Node node, String prefix, boolean direction)
 {
 String string = "";
 if(node != null)
 {
 string += toString(node.right, prefix + (direction ? " " : "│ "), true);
 string += prefix + (direction ? "┌─────" : "└─────") + String.format("(%s,%s)\n", node.key, node.value);
 string += toString(node.left, prefix + (direction ? "│ " : " "), false);
 }
 return string;
 }
}

public class AVLTreeDictionary<K extends Comparable<K>,V> implements Dictionary<K,V>
{
 /* Duplicate keys handling by overwriting value. Null keys
 * unsupported. It is assumed they will not be passed in.
 * Duplicate and null values supported.
 */
 private Node root;
 public AVLTreeDictionary()
 {
 root = null;
 }
 public V insert(K key, V value)
 {
 /* Adds a new entry to the tree. If the key already exists
 * overwrites the value and returns the old value. Performs
 * AVL rebalancing afterwords.
 */
 Path path = getPath(key);
 if(path.child() != null)
 {
 V previous = path.child().value;
 path.child().value = value;
 return previous;
 }
 path.setChild(new Node(key, value));
 path.pop();
 balancePath(path);
 return null;
 }
 public V delete(K key)
 {
 /* Deletes an entry from the tree if it exists.
 * If 0 children: Deletes entry.
 * If 1 child: Replaces entry with child.
 * If 2 children: Randomly selected between successor/predecessor
 * and copies values then deletes succ/pred and replaces it with
 * its one child if it exists. Performs AVL rebalancing afterwords.
 */
 Path path = getPath(key);
 Node node = path.child();
 if(node == null)
 {
 return null;
 }
 if(node.right == null)
 {
 path.setChild(node.left);
 }
 else if(node.left == null)
 {
 path.setChild(node.right);
 }
 else
 {
 boolean direction = Math.random() >= 0.5;
 path.push(direction);
 while(path.grandChild(!direction) != null)
 {
 path.push(!direction);
 }
 node.key = path.child().key;
 node.value = path.child().value;
 path.setChild(path.grandChild(direction));
 }
 path.pop();
 balancePath(path);
 return null;
 }
 public V search(K key)
 {
 // Standard binary search.
 Node search = root;
 while(search != null)
 {
 int compare = key.compareTo(search.key);
 if(compare == 0)
 {
 return search.value;
 }
 search = search.child(compare > 0);
 }
 return null;
 }
 private Path getPath(K key)
 {
 /* Returns a path from the root to the key specified or the
 * position it would be added in if it does not exist. Includes
 * the root edge.
 */
 Path path = new Path(new Edge(null, false));
 while(true)
 {
 if(path.child() == null)
 {
 return path;
 }
 int compare = key.compareTo(path.child().key);
 if(compare == 0)
 {
 return path;
 }
 path.push(compare > 0);
 }
 }
 private void rotate(Edge edge, boolean direction)
 {
 /* Rotates the child of the edge with its child
 * in the direction specified. It is assumed both the child
 * and grandchild are not null.
 */
 Edge rotate = new Edge(edge.child(), direction);
 edge.setChild(rotate.child());
 rotate.setChild(rotate.grandChild(!direction));
 edge.child().setChild(rotate.parent, !direction);
 }
 private void balancePath(Path path)
 {
 /* Follows a path up the tree performing AVL rebalancing
 * and height updates as needed.
 */
 while(path.peek() != null)
 {
 if(Math.abs(path.child().balance()) > 1)
 {
 boolean direction = path.child().balance() > 0;
 if(path.child().balance() * path.grandChild(direction).balance() < 0)
 {
 path.push(direction);
 rotate(path.peek(), !direction);
 path.pop().grandChild(direction).updateHeight();
 }
 rotate(path.peek(), direction);
 path.grandChild(!direction).updateHeight();
 }
 if(!path.pop().child().updateHeight())
 {
 break;
 }
 }
 }
 private class Node
 {
 /* This node class has get/set child functions that use a variable
 * to select which child. This allows us to avoid writing duplicate
 * code for the mirror image of operations. The balance of a node
 * refers to the difference in height between the right and left
 * subtrees. A positive balance is right-heavy, negative is left-heavy.
 * False = Left, True = Right.
 */
 public Node left;
 public Node right;
 public K key;
 public V value;
 public int height;
 public Node(K key, V value)
 {
 left = null;
 right = null;
 this.key = key;
 this.value = value;
 height = 0;
 }
 public Node child(boolean direction)
 {
 if(direction)
 {
 return right;
 }
 else
 {
 return left;
 }
 }
 public void setChild(Node child, boolean direction)
 {
 if(direction)
 {
 right = child;
 }
 else
 {
 left = child;
 }
 }
 public int balance()
 {
 return (right != null ? right.height : -1) - (left != null ? left.height : -1);
 }
 public boolean updateHeight()
 {
 // Returns true if the height changed.
 int previous = height;
 height = Math.max((left != null ? left.height : -1), (right != null ? right.height : -1)) + 1;
 return height != previous;
 }
 }
 private class Edge
 {
 /* An edge is a connection between two nodes. It is represented by the parent
 * node and the directon to the child node. An edge may point to a null child.
 * There is also a special edge called the root edge which has the root as its
 * child, it is represented by a null parent. This representation allows us
 * to avoid writing duplicate code for handling operations involving the root.
 */
 public Node parent;
 public boolean direction;
 public Edge(Node parent, boolean direction)
 {
 this.parent = parent;
 this.direction = direction;
 }
 public Node child()
 {
 if(parent == null)
 {
 return root;
 }
 else
 {
 return parent.child(direction);
 }
 }
 public void setChild(Node child)
 {
 if(parent == null)
 {
 root = child;
 }
 else
 {
 parent.setChild(child, direction);
 }
 }
 public Node grandChild(boolean direction)
 {
 /* Returns the grandchild in the direction specified.
 * It is assumed this will not be called if the child
 * is null.
 */
 return child().child(direction);
 }
 }
 private class Path
 {
 /* A path is a list of adjacent edges going down the tree. All operations
 * are performed on the bottom-most edge of the path.
 */
 private Stack<Edge> stack;
 public Path(Edge edge)
 {
 stack = new LinkedListStack<Edge>();
 stack.push(edge);
 }
 public void push(boolean direction)
 {
 /* Extends the path downwards in the direction specified. It is
 * assumed this will not be called if the path points to a null
 * child.
 */
 stack.push(new Edge(child(), direction));
 }
 public Edge pop()
 {
 /* Retracts the bottom of the path upwards one edge and
 * returns the deleted edge.
 */
 return stack.pop();
 }
 public Edge peek()
 {
 return stack.peek();
 }
 public Node child()
 {
 return stack.peek().child();
 }
 public void setChild(Node child)
 {
 stack.peek().setChild(child);
 }
 public Node grandChild(boolean direction)
 {
 return stack.peek().grandChild(direction);
 }
 }
 public String toString()
 {
 return toString(root, "", false);
 }
 public String toString(Node node, String prefix, boolean direction)
 {
 String string = "";
 if(node != null)
 {
 string += toString(node.right, prefix + (direction ? " " : "│ "), true);
 string += prefix + (direction ? "┌─────" : "└─────") + String.format("(%s,%s)\n", node.key, node.value);
 string += toString(node.left, prefix + (direction ? "│ " : " "), false);
 }
 return string;
 }
}