在JAVA中实现AVL树
我想用Java实现一个AVL树，这是我到目前为止所拥有的：
public class AVLNode { private int size; /** The size of the tree. */ private int height; /** The height of the tree. */ private Object key;/** The key of the current node. */ private Object data;/** The data of the current node. */ private Comparator comp;/** The {@link Comparator} used by the node. */ /* All the nodes pointed by the current node.*/ private AVLNode left,right,parent,succ,pred; /* Instantiates a new AVL node. * * @param key the key of the node * @param data the data that the node should keep * @param comp the comparator to be used in the tree */ public AVLNode(Object key, Object data, Comparator comp) { this(key,data,comp,null); } /* Instantiates a new AVL node. * * @param key the key of the node * @param data the data that the node should keep * @param comp the comparator to be used in the tree * @param parent the parent of the created node */ public AVLNode(Object key, Object data, Comparator comp, AVLNode parent) { this.data = data; this.key = key; this.comp = comp; this.parent = parent; this.left = null; this.right = null; this.succ = null; this.pred = null; this.size = 1; this.height = 0; } /* Adds the given data to the tree. * * @param key the key * @param data the data * @return the root of the tree after insertion and rotations * @author students */ public AVLNode add(Object key,Object data) { return null; } /* Removes a Node which key is equal * (by {@link Comparator}) to the given argument. * * @param key the key * @return the root after deletion and rotations * @author students */ public AVLNode remove(Object key) { return null; } 我需要实现添加和删除function。 这是我到目前为止，两者都应该在O(log(n))时间运行。 两者都应该返回整棵树的根：
/* Adds a new Node into the tree. * @param key the key of the new node * @param data the data of the new node */ public void add(Object key,Object data){ if (isEmpty()){ this.root = new AVLNode(key,data,comp); } else{ root = this.root.add(key,data); } } /** * Removes a node n from the tree where * n.key is equal (by {@link Comparator}) to the given key. * * @param key the key */ public void remove(Object key){ if (isEmpty()){ return; } else root = this.root.remove(key); }
我需要有关添加和删除function的帮助。
是否有任何指南来描述添加和删除操作的工作原理？ 要复制的库还是我可以弄清楚AVL Trees如何工作的原因？
你可以试试我在这里链接的AVL树。 如果您有任何其他问题，请与我们联系。
链接断开时的来源
package com.jwetherell.algorithms.data_structures; import java.util.ArrayList; import java.util.List; /** * An AVL tree is a self-balancing binary search tree, and it was the first such * data structure to be invented. In an AVL tree, the heights of the two child * subtrees of any node differ by at most one. AVL trees are often compared with * red-black trees because they support the same set of operations and because * red-black trees also take O(log n) time for the basic operations. Because AVL * trees are more rigidly balanced, they are faster than red-black trees for * lookup intensive applications. However, red-black trees are faster for * insertion and removal. * * http://en.wikipedia.org/wiki/AVL_tree * * @author Justin Wetherell */ public class AVLTree> extends BinarySearchTree implements BinarySearchTree.INodeCreator { private enum Balance { LEFT_LEFT, LEFT_RIGHT, RIGHT_LEFT, RIGHT_RIGHT }; /** * Default constructor. */ public AVLTree() { this.creator = this; } /** * Constructor with external Node creator. */ public AVLTree(INodeCreator creator) { super(creator); } /** * {@inheritDoc} */ @Override protected Node addValue(T id) { Node nodeToReturn = super.addValue(id); AVLNode nodeAdded = (AVLNode ) nodeToReturn; while (nodeAdded != null) { nodeAdded.updateHeight(); balanceAfterInsert(nodeAdded); nodeAdded = (AVLNode ) nodeAdded.parent; } return nodeToReturn; } /** * Balance the tree according to the AVL post-insert algorithm. * * @param node * Root of tree to balance. */ private void balanceAfterInsert(AVLNode node) { int balanceFactor = node.getBalanceFactor(); if (balanceFactor > 1 || balanceFactor < -1) { AVLNode parent = null; AVLNode child = null; Balance balance = null; if (balanceFactor < 0) { parent = (AVLNode ) node.lesser; balanceFactor = parent.getBalanceFactor(); if (balanceFactor < 0) { child = (AVLNode ) parent.lesser; balance = Balance.LEFT_LEFT; } else { child = (AVLNode ) parent.greater; balance = Balance.LEFT_RIGHT; } } else { parent = (AVLNode ) node.greater; balanceFactor = parent.getBalanceFactor(); if (balanceFactor < 0) { child = (AVLNode ) parent.lesser; balance = Balance.RIGHT_LEFT; } else { child = (AVLNode ) parent.greater; balance = Balance.RIGHT_RIGHT; } } if (balance == Balance.LEFT_RIGHT) { // Left-Right (Left rotation, right rotation) rotateLeft(parent); rotateRight(node); } else if (balance == Balance.RIGHT_LEFT) { // Right-Left (Right rotation, left rotation) rotateRight(parent); rotateLeft(node); } else if (balance == Balance.LEFT_LEFT) { // Left-Left (Right rotation) rotateRight(node); } else { // Right-Right (Left rotation) rotateLeft(node); } node.updateHeight(); // New child node child.updateHeight(); // New child node parent.updateHeight(); // New Parent node } } /** * {@inheritDoc} */ @Override protected Node removeValue(T value) { // Find node to remove Node nodeToRemoved = this.getNode(value); if (nodeToRemoved != null) { // Find the replacement node Node replacementNode = this.getReplacementNode(nodeToRemoved); // Find the parent of the replacement node to re-factor the // height/balance of the tree AVLNode nodeToRefactor = null; if (replacementNode != null) nodeToRefactor = (AVLNode ) replacementNode.parent; if (nodeToRefactor == null) nodeToRefactor = (AVLNode ) nodeToRemoved.parent; if (nodeToRefactor != null && nodeToRefactor.equals(nodeToRemoved)) nodeToRefactor = (AVLNode ) replacementNode; // Replace the node replaceNodeWithNode(nodeToRemoved, replacementNode); // Re-balance the tree all the way up the tree if (nodeToRefactor != null) { while (nodeToRefactor != null) { nodeToRefactor.updateHeight(); balanceAfterDelete(nodeToRefactor); nodeToRefactor = (AVLNode ) nodeToRefactor.parent; } } } return nodeToRemoved; } /** * Balance the tree according to the AVL post-delete algorithm. * * @param node * Root of tree to balance. */ private void balanceAfterDelete(AVLNode node) { int balanceFactor = node.getBalanceFactor(); if (balanceFactor == -2 || balanceFactor == 2) { if (balanceFactor == -2) { AVLNode ll = (AVLNode ) node.lesser.lesser; int lesser = (ll != null) ? ll.height : 0; AVLNode lr = (AVLNode ) node.lesser.greater; int greater = (lr != null) ? lr.height : 0; if (lesser >= greater) { rotateRight(node); node.updateHeight(); if (node.parent != null) ((AVLNode ) node.parent).updateHeight(); } else { rotateLeft(node.lesser); rotateRight(node); AVLNode p = (AVLNode ) node.parent; if (p.lesser != null) ((AVLNode ) p.lesser).updateHeight(); if (p.greater != null) ((AVLNode ) p.greater).updateHeight(); p.updateHeight(); } } else if (balanceFactor == 2) { AVLNode rr = (AVLNode ) node.greater.greater; int greater = (rr != null) ? rr.height : 0; AVLNode rl = (AVLNode ) node.greater.lesser; int lesser = (rl != null) ? rl.height : 0; if (greater >= lesser) { rotateLeft(node); node.updateHeight(); if (node.parent != null) ((AVLNode ) node.parent).updateHeight(); } else { rotateRight(node.greater); rotateLeft(node); AVLNode p = (AVLNode ) node.parent; if (p.lesser != null) ((AVLNode ) p.lesser).updateHeight(); if (p.greater != null) ((AVLNode ) p.greater).updateHeight(); p.updateHeight(); } } } } /** * {@inheritDoc} */ @Override protected boolean validateNode(Node node) { boolean bst = super.validateNode(node); if (!bst) return false; AVLNode avlNode = (AVLNode ) node; int balanceFactor = avlNode.getBalanceFactor(); if (balanceFactor > 1 || balanceFactor < -1) { return false; } if (avlNode.isLeaf()) { if (avlNode.height != 1) return false; } else { AVLNode avlNodeLesser = (AVLNode ) avlNode.lesser; int lesserHeight = 1; if (avlNodeLesser != null) lesserHeight = avlNodeLesser.height; AVLNode avlNodeGreater = (AVLNode ) avlNode.greater; int greaterHeight = 1; if (avlNodeGreater != null) greaterHeight = avlNodeGreater.height; if (avlNode.height == (lesserHeight + 1) || avlNode.height == (greaterHeight + 1)) { return true; } else { return false; } } return true; } /** * {@inheritDoc} */ @Override public String toString() { return AVLTreePrinter.getString(this); } /** * {@inheritDoc} */ @Override public Node createNewNode(Node parent, T id) { return (new AVLNode (parent, id)); } protected static class AVLNode > extends Node { protected int height = 1; /** * Constructor for an AVL node * * @param parent * Parent of the node in the tree, can be NULL. * @param value * Value of the node in the tree. */ protected AVLNode(Node parent, T value) { super(parent, value); } /** * Determines is this node is a leaf (has no children). * * @return True if this node is a leaf. */ protected boolean isLeaf() { return ((lesser == null) && (greater == null)); } /** * Updates the height of this node based on it's children. */ protected void updateHeight() { int lesserHeight = 0; int greaterHeight = 0; if (lesser != null) { AVLNode lesserAVLNode = (AVLNode ) lesser; lesserHeight = lesserAVLNode.height; } if (greater != null) { AVLNode greaterAVLNode = (AVLNode ) greater; greaterHeight = greaterAVLNode.height; } if (lesserHeight > greaterHeight) { height = lesserHeight + 1; } else { height = greaterHeight + 1; } } /** * Get the balance factor for this node. * * @return An integer representing the balance factor for this node. It * will be negative if the lesser branch is longer than the * greater branch. */ protected int getBalanceFactor() { int lesserHeight = 0; int greaterHeight = 0; if (lesser != null) { AVLNode lesserAVLNode = (AVLNode ) lesser; lesserHeight = lesserAVLNode.height; } if (greater != null) { AVLNode greaterAVLNode = (AVLNode ) greater; greaterHeight = greaterAVLNode.height; } return greaterHeight - lesserHeight; } /** * {@inheritDoc} */ @Override public String toString() { return "value=" + id + " height=" + height + " parent=" + ((parent != null) ? parent.id : "NULL") + " lesser=" + ((lesser != null) ? lesser.id : "NULL") + " greater=" + ((greater != null) ? greater.id : "NULL"); } } protected static class AVLTreePrinter { public static > String getString(AVLTree tree) { if (tree.root == null) return "Tree has no nodes."; return getString((AVLNode ) tree.root, "", true); } public static > String getString(AVLNode node) { if (node == null) return "Sub-tree has no nodes."; return getString(node, "", true); } private static > String getString(AVLNode node, String prefix, boolean isTail) { StringBuilder builder = new StringBuilder(); builder.append(prefix + (isTail ? "└── " : "├── ") + "(" + node.height + ") " + node.id + "\n"); List> children = null; if (node.lesser != null || node.greater != null) { children = new ArrayList>(2); if (node.lesser != null) children.add(node.lesser); if (node.greater != null) children.add(node.greater); } if (children != null) { for (int i = 0; i < children.size() - 1; i++) { builder.append(getString((AVLNode ) children.get(i), prefix + (isTail ? " " : "│ "), false)); } if (children.size() >= 1) { builder.append(getString((AVLNode ) children.get(children.size() - 1), prefix + (isTail ? " " : "│ "), true)); } } return builder.toString(); } } }
另一种AVL的Java实现，包括插入，搜索和删除。
当您执行有序遍历时，它还会打印出每个节点的父名称和高度，这样可以轻松查看操作的效果。
开箱即用的可运行代码应该对CS学生在家庭作业中苦苦挣扎:-)
public class AVLTree { private static class Node { Node left, right; Node parent; int value ; int height = 0; public Node(int data, Node parent) { this.value = data; this.parent = parent; } @Override public String toString() { return value + " height " + height + " parent " + (parent == null ? "NULL" : parent.value) + " | "; } void setLeftChild(Node child) { if (child != null) { child.parent = this; } this.left = child; } void setRightChild(Node child) { if (child != null) { child.parent = this; } this.right = child; } } private Node root = null; public void insert(int data) { insert(root, data); } private int height(Node node) { return node == null ? -1 : node.height; } private void insert(Node node, int value) { if (root == null) { root = new Node(value, null); return; } if (value < node.value) { if (node.left != null) { insert(node.left, value); } else { node.left = new Node(value, node); } if (height(node.left) - height(node.right) == 2) { //left heavier if (value < node.left.value) { rotateRight(node); } else { rotateLeftThenRight(node); } } } else if (value > node.value) { if (node.right != null) { insert(node.right, value); } else { node.right = new Node(value, node); } if (height(node.right) - height(node.left) == 2) { //right heavier if (value > node.right.value) rotateLeft(node); else { rotateRightThenLeft(node); } } } reHeight(node); } private void rotateRight(Node pivot) { Node parent = pivot.parent; Node leftChild = pivot.left; Node rightChildOfLeftChild = leftChild.right; pivot.setLeftChild(rightChildOfLeftChild); leftChild.setRightChild(pivot); if (parent == null) { this.root = leftChild; leftChild.parent = null; return; } if (parent.left == pivot) { parent.setLeftChild(leftChild); } else { parent.setRightChild(leftChild); } reHeight(pivot); reHeight(leftChild); } private void rotateLeft(Node pivot) { Node parent = pivot.parent; Node rightChild = pivot.right; Node leftChildOfRightChild = rightChild.left; pivot.setRightChild(leftChildOfRightChild); rightChild.setLeftChild(pivot); if (parent == null) { this.root = rightChild; rightChild.parent = null; return; } if (parent.left == pivot) { parent.setLeftChild(rightChild); } else { parent.setRightChild(rightChild); } reHeight(pivot); reHeight(rightChild); } private void reHeight(Node node) { node.height = Math.max(height(node.left), height(node.right)) + 1; } private void rotateLeftThenRight(Node node) { rotateLeft(node.left); rotateRight(node); } private void rotateRightThenLeft(Node node) { rotateRight(node.right); rotateLeft(node); } public boolean delete(int key) { Node target = search(key); if (target == null) return false; target = deleteNode(target); balanceTree(target.parent); return true; } private Node deleteNode(Node target) { if (isLeaf(target)) { //leaf if (isLeftChild(target)) { target.parent.left = null; } else { target.parent.right = null; } } else if (target.left == null ^ target.right == null) { //exact 1 child Node nonNullChild = target.left == null ? target.right : target.left; if (isLeftChild(target)) { target.parent.setLeftChild(nonNullChild); } else { target.parent.setRightChild(nonNullChild); } } else {//2 children Node immediatePredInOrder = immediatePredInOrder(target); target.value = immediatePredInOrder.value; target = deleteNode(immediatePredInOrder); } reHeight(target.parent); return target; } private Node immediatePredInOrder(Node node) { Node current = node.left; while (current.right != null) { current = current.right; } return current; } private boolean isLeftChild(Node child) { return (child.parent.left == child); } private boolean isLeaf(Node node) { return node.left == null && node.right == null; } private int calDifference(Node node) { int rightHeight = height(node.right); int leftHeight = height(node.left); return rightHeight - leftHeight; } private void balanceTree(Node node) { int difference = calDifference(node); Node parent = node.parent; if (difference == -2) { if (height(node.left.left) >= height(node.left.right)) { rotateRight(node); } else { rotateLeftThenRight(node); } } else if (difference == 2) { if (height(node.right.right) >= height(node.right.left)) { rotateLeft(node); } else { rotateRightThenLeft(node); } } if (parent != null) { balanceTree(parent); } reHeight(node); } public Node search(int key) { return binarySearch(root, key); } private Node binarySearch(Node node, int key) { if (node == null) return null; if (key == node.value) { return node; } if (key < node.value && node.left != null) { return binarySearch(node.left, key); } if (key > node.value && node.right != null) { return binarySearch(node.right, key); } return null; } public void traverseInOrder() { System.out.println("ROOT " + root.toString()); inorder(root); System.out.println(); } private void inorder(Node node) { if (node != null) { inorder(node.left); System.out.print(node.toString()); inorder(node.right); } } public static void main(String[] args) { AVLTree avl = new AVLTree(); avl.insert(1); avl.traverseInOrder(); avl.insert(2); avl.traverseInOrder(); avl.insert(3); avl.traverseInOrder(); avl.insert(4); avl.traverseInOrder(); avl.delete(1); avl.traverseInOrder(); avl.insert(5); avl.traverseInOrder(); avl.insert(6); avl.traverseInOrder(); avl.delete(3); avl.traverseInOrder(); avl.delete(5); avl.traverseInOrder(); } }
好吧，这个java代码可以帮助你，它扩展了Michael Goodrich的BST：
要查看完整的数据结构，请访问 AVLTree.java （链接不再可用）
import java.util.Comparator; /** * AVLTree class - implements an AVL Tree by extending a binary * search tree. * * @author Michael Goodrich, Roberto Tamassia, Eric Zamore */ //begin#fragment AVLTree public class AVLTree extends BinarySearchTree implements Dictionary { public AVLTree(Comparator c) { super(c); } public AVLTree() { super(); } /** Nested class for the nodes of an AVL tree. */ protected static class AVLNode extends BTNode { protected int height; // we add a height field to a BTNode AVLNode() {/* default constructor */} /** Preferred constructor */ AVLNode(Object element, BTPosition parent, BTPosition left, BTPosition right) { super(element, parent, left, right); height = 0; if (left != null) height = Math.max(height, 1 + ((AVLNode) left).getHeight()); if (right != null) height = Math.max(height, 1 + ((AVLNode) right).getHeight()); } // we assume that the parent will revise its height if needed public void setHeight(int h) { height = h; } public int getHeight() { return height; } } /** Creates a new binary search tree node (overrides super's version). */ protected BTPosition createNode(Object element, BTPosition parent, BTPosition left, BTPosition right) { return new AVLNode(element,parent,left,right); // now use AVL nodes } /** Returns the height of a node (call back to an AVLNode). */ protected int height(Position p) { return ((AVLNode) p).getHeight(); } /** Sets the height of an internal node (call back to an AVLNode). */ protected void setHeight(Position p) { // called only if p is internal ((AVLNode) p).setHeight(1+Math.max(height(left(p)), height(right(p)))); } /** Returns whether a node has balance factor between -1 and 1. */ protected boolean isBalanced(Position p) { int bf = height(left(p)) - height(right(p)); return ((-1 <= bf) && (bf <= 1)); } //end#fragment AVLTree //begin#fragment AVLTree2 /** Returns a child of p with height no smaller than that of the other child */ //end#fragment AVLTree2 /** * Return a child of p with height no smaller than that of the * other child. */ //begin#fragment AVLTree2 protected Position tallerChild(Position p) { if (height(left(p)) > height(right(p))) return left(p); else if (height(left(p)) < height(right(p))) return right(p); // equal height children - break tie using parent's type if (isRoot(p)) return left(p); if (p == left(parent(p))) return left(p); else return right(p); } /** * Rebalance method called by insert and remove. Traverses the path from * zPos to the root. For each node encountered, we recompute its height * and perform a trinode restructuring if it's unbalanced. */ protected void rebalance(Position zPos) { if(isInternal(zPos)) setHeight(zPos); while (!isRoot(zPos)) { // traverse up the tree towards the root zPos = parent(zPos); setHeight(zPos); if (!isBalanced(zPos)) { // perform a trinode restructuring at zPos's tallest grandchild Position xPos = tallerChild(tallerChild(zPos)); zPos = restructure(xPos); // tri-node restructure (from parent class) setHeight(left(zPos)); // recompute heights setHeight(right(zPos)); setHeight(zPos); } } } // overridden methods of the dictionary ADT //end#fragment AVLTree2 /** * Inserts an item into the dictionary and returns the newly created * entry. */ //begin#fragment AVLTree2 public Entry insert(Object k, Object v) throws InvalidKeyException { Entry toReturn = super.insert(k, v); // calls our new createNode method rebalance(actionPos); // rebalance up from the insertion position return toReturn; } //end#fragment AVLTree2 /** Removes and returns an entry from the dictionary. */ //begin#fragment AVLTree2 public Entry remove(Entry ent) throws InvalidEntryException { Entry toReturn = super.remove(ent); if (toReturn != null) // we actually removed something rebalance(actionPos); // rebalance up the tree return toReturn; } } // end of AVLTree class //end#fragment AVLTree2
BTNode.java
public class BTNode implements BTPosition { private Object element; // element stored at this node private BTPosition left, right, parent; // adjacent nodes //end#fragment BTNode /** Default constructor */ public BTNode() { } //begin#fragment BTNode /** Main constructor */ public BTNode(Object element, BTPosition parent, BTPosition left, BTPosition right) { setElement(element); setParent(parent); setLeft(left); setRight(right); } public Object element() { return element; } public void setElement(Object o) { element=o; } public BTPosition getLeft() { return left; } public void setLeft(BTPosition v) { left=v; } public BTPosition getRight() { return right; } public void setRight(BTPosition v) { right=v; } public BTPosition getParent() { return parent; } public void setParent(BTPosition v) { parent=v; } }
BTPosition.java
public interface BTPosition extends Position { // inherits element() public void setElement(Object o); public BTPosition getLeft(); public void setLeft(BTPosition v); public BTPosition getRight(); public void setRight(BTPosition v); public BTPosition getParent(); public void setParent(BTPosition v); }
我有一个video播放列表，解释了我推荐的AVL树是如何工作的。
这是一个AVL树的工作实现，有很好的文档记录。 添加/删除操作就像常规二进制搜索树一样，期望您需要随时更新平衡因子值 。
请注意，这是一个递归实现，它更易于理解，但可能比其迭代对应物慢。
这个数据结构来自我的github repo
/** * This file contains an implementation of an AVL tree. An AVL tree * is a special type of binary tree which self balances itself to keep * operations logarithmic. * * @author William Fiset, william.alexandre.fiset@gmail.com **/ public class AVLTreeRecursive > implements Iterable { class Node { // 'bf' is short for Balance Factor int bf; // The value/data contained within the node. T value; // The height of this node in the tree. int height; // The left and the right children of this node. Node left, right; public Node(T value) { this.value = value; } } // The root node of the AVL tree. Node root; // Tracks the number of nodes inside the tree. private int nodeCount = 0; // The height of a rooted tree is the number of edges between the tree's // root and its furthest leaf. This means that a tree containing a single // node has a height of 0. public int height() { if (root == null) return 0; return root.height; } // Returns the number of nodes in the tree. public int size() { return nodeCount; } // Returns whether or not the tree is empty. public boolean isEmpty() { return size() == 0; } // Return true/false depending on whether a value exists in the tree. public boolean contains(T value) { return contains(root, value); } // Recursive contains helper method. private boolean contains(Node node, T value) { if (node == null) return false; // Compare current value to the value in the node. int cmp = value.compareTo(node.value); // Dig into left subtree. if (cmp < 0) return contains(node.left, value); // Dig into right subtree. if (cmp > 0) return contains(node.right, value); // Found value in tree. return true; } // Insert/add a value to the AVL tree. The value must not be null, O(log(n)) public boolean insert(T value) { if (value == null) return false; if (!contains(root, value)) { root = insert(root, value); nodeCount++; return true; } return false; } // Inserts a value inside the AVL tree. private Node insert(Node node, T value) { // Base case. if (node == null) return new Node(value); // Compare current value to the value in the node. int cmp = value.compareTo(node.value); // Insert node in left subtree. if (cmp < 0) { node.left = insert(node.left, value);; // Insert node in right subtree. } else { node.right = insert(node.right, value); } // Update balance factor and height values. update(node); // Re-balance tree. return balance(node); } // Update a node's height and balance factor. private void update(Node node) { int leftNodeHeight = (node.left == null) ? -1 : node.left.height; int rightNodeHeight = (node.right == null) ? -1 : node.right.height; // Update this node's height. node.height = 1 + Math.max(leftNodeHeight, rightNodeHeight); // Update balance factor. node.bf = rightNodeHeight - leftNodeHeight; } // Re-balance a node if its balance factor is +2 or -2. private Node balance(Node node) { // Left heavy subtree. if (node.bf == -2) { // Left-Left case. if (node.left.bf <= 0) { return leftLeftCase(node); // Left-Right case. } else { return leftRightCase(node); } // Right heavy subtree needs balancing. } else if (node.bf == +2) { // Right-Right case. if (node.right.bf >= 0) { return rightRightCase(node); // Right-Left case. } else { return rightLeftCase(node); } } // Node either has a balance factor of 0, +1 or -1 which is fine. return node; } private Node leftLeftCase(Node node) { return rightRotation(node); } private Node leftRightCase(Node node) { node.left = leftRotation(node.left); return leftLeftCase(node); } private Node rightRightCase(Node node) { return leftRotation(node); } private Node rightLeftCase(Node node) { node.right = rightRotation(node.right); return rightRightCase(node); } private Node leftRotation(Node node) { Node newParent = node.right; node.right = newParent.left; newParent.left = node; update(node); update(newParent); return newParent; } private Node rightRotation(Node node) { Node newParent = node.left; node.left = newParent.right; newParent.right = node; update(node); update(newParent); return newParent; } // Remove a value from this binary tree if it exists, O(log(n)) public boolean remove(T elem) { if (elem == null) return false; if (contains(root, elem)) { root = remove(root, elem); nodeCount--; return true; } return false; } // Removes a value from the AVL tree. private Node remove(Node node, T elem) { if (node == null) return null; int cmp = elem.compareTo(node.value); // Dig into left subtree, the value we're looking // for is smaller than the current value. if (cmp < 0) { node.left = remove(node.left, elem); // Dig into right subtree, the value we're looking // for is greater than the current value. } else if (cmp > 0) { node.right = remove(node.right, elem); // Found the node we wish to remove. } else { // This is the case with only a right subtree or no subtree at all. // In this situation just swap the node we wish to remove // with its right child. if (node.left == null) { return node.right; // This is the case with only a left subtree or // no subtree at all. In this situation just // swap the node we wish to remove with its left child. } else if (node.right == null) { return node.left; // When removing a node from a binary tree with two links the // successor of the node being removed can either be the largest // value in the left subtree or the smallest value in the right // subtree. As a heuristic, I will remove from the subtree with // the most nodes in hopes that this may help with balancing. } else { // Choose to remove from left subtree if (node.left.height > node.right.height) { // Swap the value of the successor into the node. T successorValue = findMax(node.left); node.value = successorValue; // Find the largest node in the left subtree. node.left = remove(node.left, successorValue); } else { // Swap the value of the successor into the node. T successorValue = findMin(node.right); node.value = successorValue; // Go into the right subtree and remove the leftmost node we // found and swapped data with. This prevents us from having // two nodes in our tree with the same value. node.right = remove(node.right, successorValue); } } } // Update balance factor and height values. update(node); // Re-balance tree. return balance(node); } // Helper method to find the leftmost node (which has the smallest value) private T findMin(Node node) { while(node.left != null) node = node.left; return node.value; } // Helper method to find the rightmost node (which has the largest value) private T findMax(Node node) { while(node.right != null) node = node.right; return node.value; } // Returns as iterator to traverse the tree in order. public java.util.Iterator iterator () { final int expectedNodeCount = nodeCount; final java.util.Stack stack = new java.util.Stack<>(); stack.push(root); return new java.util.Iterator () { Node trav = root; @Override public boolean hasNext() { if (expectedNodeCount != nodeCount) throw new java.util.ConcurrentModificationException(); return root != null && !stack.isEmpty(); } @Override public T next () { if (expectedNodeCount != nodeCount) throw new java.util.ConcurrentModificationException(); while(trav != null && trav.left != null) { stack.push(trav.left); trav = trav.left; } Node node = stack.pop(); if (node.right != null) { stack.push(node.right); trav = node.right; } return node.value; } @Override public void remove() { throw new UnsupportedOperationException(); } }; } // Make sure all left child nodes are smaller in value than their parent and // make sure all right child nodes are greater in value than their parent. // (Used only for testing) boolean validateBstInvarient(Node node) { if (node == null) return true; T val = node.value; boolean isValid = true; if (node.left != null) isValid = isValid && node.left.value.compareTo(val) < 0; if (node.right != null) isValid = isValid && node.right.value.compareTo(val) > 0; return isValid && validateBstInvarient(node.left) && validateBstInvarient(node.right); } // Example usage of AVL tree. public static void main(String[] args) { AVLTreeRecursive tree = new AVLTreeRecursive<>(); tree.insert(7); tree.insert(16); tree.insert(-2); tree.insert(10); tree.insert(12); // Prints: -2 7 10 12 16 for(Integer value : tree) System.out.print(value + " "); System.out.println(); tree.remove(12); tree.remove(-5); tree.remove(10); // Prints: -2 7 16 for(Integer value : tree) System.out.print(value + " "); System.out.println(); System.out.println(tree.contains(10)); // false System.out.println(tree.contains(16)); // true } }