AVLTree

你以为爱就是被爱

/*** @Classname AVL* @Description* @Date 2020/1/19 15:02* @Author SonnSei*/
public class AVLTree<K extends Comparable<K>, V> {private Node root;private int size;public AVLTree() {root = null;size = 0;}public int getSize() {return size;}public boolean isEmpty() {return size == 0;}  public boolean isBalanced() {return isBalanced(root);}private boolean isBalanced(Node node) {if (node == null) return true;int balanceFactor = getBalanceFactor(node);if (Math.abs(balanceFactor) > 1) return false;return isBalanced(node.left) && isBalanced(node.right);}private int getBalanceFactor(Node node) {if (node == null) return 0;return getHeight(node.left) - getHeight(node.right);}private int getHeight(Node node) {if (node == null) return 0;return node.height;}// 对节点y进行向右旋转操作，返回旋转后新的根节点x// node x// / \ / \// x T4 向右旋转 (y) z node// / \ - - - - - - - -> / \ / \// z T3 T1 T2 T3 T4// / \// T1 T2private Node rightRotate(Node node) {Node x = node.left;node.left = x.right;x.right = node;node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;return x;}// 对节点y进行向左旋转操作，返回旋转后新的根节点x// node x// / \ / \// T1 x 向左旋转 (y) node z// / \ - - - - - - - -> / \ / \// T2 z T1 T2 T3 T4// / \// T3 T4private Node leftRotate(Node node) {Node x = node.right;node.right = x.left;x.left = node;node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;return x;}public void add(K key, V value) {root = add(root, key, value);}private Node add(Node node, K key, V value) {if (node == null) {size++;return new Node(key, value);}if (key.compareTo(node.key) < 0)node.left = add(node.left, key, value);else if (key.compareTo(node.key) > 0)node.right = add(node.right, key, value);elsenode.value = value;// 更新heightnode.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));int balanceFactor = getBalanceFactor(node);//LLif (balanceFactor > 1 && getBalanceFactor(node.left) > 0)return rightRotate(node);//RRif (balanceFactor < -1 && getBalanceFactor(node.right) < 0)return leftRotate(node);//LRif (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {node.left = leftRotate(node.left);return rightRotate(node);}//RLif (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {node.right = rightRotate(node.right);return leftRotate(node);}return node;}public boolean contains(K key) {return getNode(root, key) != null;}private Node getNode(Node node, K key) {if (node == null) return null;if (key.equals(node.key)) return node;if (key.compareTo(node.key) < 0) return getNode(node.left, key);return getNode(node.right, key);}public void set(K key, V newValue) {Node node = getNode(root, key);if (node != null) node.value = newValue;}public V get(K key) {Node node = getNode(root, key);return node == null ? null : node.value;}public V remove(K key) {Node node = getNode(root, key);if (node != null) {root = remove(root, key);return node.value;}return null;}private Node remove(Node node, K key) {if (node == null)return null;Node retNode;if (key.compareTo(node.key) < 0) {node.left = remove(node.left, key);retNode = node;} else if (key.compareTo(node.key) > 0) {node.right = remove(node.right, key);retNode = node;} else {if (node.left == null) {Node rightNode = node.right;node.right = null;size--;retNode = rightNode;} else if (node.right == null) {Node leftNode = node.left;node.left = null;size--;retNode = leftNode;}// 待删除节点左右子树均不为空的情况else {Node successor = minimum(node.right);successor.right = remove(node.right, successor.key);successor.left = node.left;node.left = node.right = null;retNode = successor;}}if (retNode == null)return null;retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));int balanceFactor = getBalanceFactor(retNode);// 平衡维护// LLif (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0)return rightRotate(retNode);// RRif (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0)return leftRotate(retNode);// LRif (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {retNode.left = leftRotate(retNode.left);return rightRotate(retNode);}// RLif (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {retNode.right = rightRotate(retNode.right);return leftRotate(retNode);}return retNode;}private Node minimum(Node node) {if (node.left == null)return node;return minimum(node.left);}private class Node {K key;V value;Node left, right;int height;public Node(K key, V value) {this.key = key;this.value = value;left = null;right = null;height = 1;}}
}