AVL
均衡二叉树
均衡二叉查找树：简称均衡二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度均衡的二叉树，依据科学家的英文名也称为 AVL 树。它具备如下几个性质：
- 能够是空树。
- 如果不是空树，任何一个结点的左子树与右子树都是均衡二叉树，并且高度之差的绝对值不超过 1。
二叉搜寻树肯定水平上能够进步搜寻效率，然而当原序列有序时，例如序列 {1，2，3，4，5，6}，结构二叉搜寻树。根据此序列结构的二叉搜寻树为右斜树，同时二叉树进化成单链表，搜寻效率升高为 O(n)。
在此二叉搜寻树中查找元素 6 须要查找 6 次。
二叉搜寻树的查找效率取决于树的高度，因而放弃树的高度最小，即可保障树的查找效率。同样的序列 A，将其改为图中的形式存储，查找元素 6 时只需比拟 3 次，查找效率晋升一倍。
能够看出当节点数目肯定，放弃树的左右两端保持平衡，树的查找效率最高。
这种左右子树的高度相差不超过 1 的树为均衡二叉树。
均衡因子
某节点的左子树与右子树的高度(深度)差即为该节点的均衡因子（BF：Balance Factor）。
节点为2的深度为1，因为没有子节点所有均衡因子是0，节点为4的深度为2，均衡因子是左孩子减去右孩子所以是1-0 = 1 ，均衡因子为1。顺次类推，当有节点大于1的时候就阐明不是均衡二叉树。
public class AVLTree<K extends Comparable<K>, V> { private class Node{ public K key; public V value; public Node left, right; public int height; public Node(K key, V value){ this.key = key; this.value = value; left = null; right = null; height = 1; } } private Node root; private int size; public AVLTree(){ root = null; size = 0; } public int getSize(){ return size; } public boolean isEmpty(){ return size == 0; } // 取得节点node的高度 private int getHeight(Node node){ if(node == null) { return 0; } return node.height; } // 取得节点node的均衡因子 private int getBalanceFactor(Node node){ if(node == null) { return 0; } return getHeight(node.left) - getHeight(node.right); } // 向二分搜寻树中增加新的元素(key, value) public void add(K key, V value){ root = add(root, key, value); } // 向以node为根的二分搜寻树中插入元素(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); } else // key.compareTo(node.key) == 0 { node.value = value; } // 更新height node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right)); // 计算均衡因子 int balanceFactor = getBalanceFactor(node); if(Math.abs(balanceFactor) > 1) { System.out.println("unbalanced : " + balanceFactor); } return node; } // 返回以node为根节点的二分搜寻树中，key所在的节点 private Node getNode(Node node, K key){ if(node == null) { return null; } if(key.equals(node.key)) { return node; } else if(key.compareTo(node.key) < 0) { return getNode(node.left, key); } else // if(key.compareTo(node.key) > 0) { return getNode(node.right, key); } } public boolean contains(K key){ return getNode(root, key) != null; } public V get(K key){ Node node = getNode(root, key); return node == null ? null : node.value; } public void set(K key, V newValue){ Node node = getNode(root, key); if(node == null) { throw new IllegalArgumentException(key + " doesn't exist!"); } node.value = newValue; } // 返回以node为根的二分搜寻树的最小值所在的节点 private Node minimum(Node node){ if(node.left == null) { return node; } return minimum(node.left); } // 删除掉以node为根的二分搜寻树中的最小节点 // 返回删除节点后新的二分搜寻树的根 private Node removeMin(Node node){ if(node.left == null){ Node rightNode = node.right; node.right = null; size --; return rightNode; } node.left = removeMin(node.left); return node; } // 从二分搜寻树中删除键为key的节点 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; } if( key.compareTo(node.key) < 0 ){ node.left = remove(node.left , key); return node; } else if(key.compareTo(node.key) > 0 ){ node.right = remove(node.right, key); return node; } else{ // key.compareTo(node.key) == 0 // 待删除节点左子树为空的状况 if(node.left == null){ Node rightNode = node.right; node.right = null; size --; return rightNode; } // 待删除节点右子树为空的状况 if(node.right == null){ Node leftNode = node.left; node.left = null; size --; return leftNode; } // 待删除节点左右子树均不为空的状况 // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点 // 用这个节点顶替待删除节点的地位 Node successor = minimum(node.right); successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; } }}二分搜寻树性质和平衡性
判断该树是否是一颗二分搜寻树
所谓的二分搜寻树，就是任意一个节点满足，大于左孩子，小于右孩子。所以二分搜寻树满足这样的一个性质：中序遍历之后的二叉树是程序的。所以咱们这里实现的思路是，改写二叉树的非递归版本的，来校验以后值和前一个值的大小关系。
//判断该二叉树是否是一颗二分搜寻树 public boolean isBST() { List<K> keys = new ArrayList<>(); inOrder(root, keys); for (int i = 0; i < keys.size(); i++) { if (keys.get(i - 1).compareTo(keys.get(i)) > 0) { return false; } } return true; } private void inOrder(Node node, List<K> keys) { if (node == null) { return; } inOrder(node.left, keys); keys.add(node.key); inOrder(node.right, keys); }判断该树是否是一颗均衡二叉树
- 1.判断以根结点的树是否为均衡二叉树。求出左右子树的高度，判断它们的高度差是否超过了1。
- 2.递归判断根的左子树是否为均衡二叉树
- 3.递归判断根的右子树是否为均衡二叉树
留神：空树也是均衡二叉树
//判断该二叉树是否是一颗均衡二叉树 public boolean isBalanced() { return isBalanced(root); } //判断以Node为根的二叉树是否是一颗均衡二叉树，递归算法 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); }旋转操作的基本原理
咱们在插入数据的时候可能会突破平衡性，所以咱们须要沿着节点向上保护平衡性。
在什么时候保护均衡？
在一开始，咱们增加一个节点12，均衡因子是0。
而后增加一个节点8，这时候均衡因子是0，而12的均衡因子是1。
而后增加一个节点5，这时候均衡因子是0，而8的均衡因子是1，12的均衡因子就变为了2。
这时候就不再是均衡二叉树。
右旋（LL）
- 根节点（Y）的左孩子代表根节点
- （X）节点的右子树变为（Y）的左子树
- 将此节点（Y）变为（X）根节点的右子树
代码逻辑为：
x.right = yy.left = T3动图援用于此
具体动画演示如下：
当旋转之后，咱们这棵树仍旧放弃二分搜寻树和均衡二叉树的性质。
// 向以node为根的二分搜寻树中插入元素(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); } else // key.compareTo(node.key) == 0 { node.value = value; } // 更新height node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right)); // 计算均衡因子 int balanceFactor = getBalanceFactor(node); if (Math.abs(balanceFactor) > 1) { System.out.println("unbalanced : " + balanceFactor); } //均衡保护 if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) { return rightRotate(node); } return node; } // 对节点y进行向右旋转操作，返回旋转后新的根节点x // y x // / \ / \ // x T4 向右旋转 (y) z y // / \ - - - - - - - -> / \ / \ // z T3 T1 T2 T3 T4 // / \ // T1 T2 private Node rightRotate(Node y) { Node x = y.left; Node t3 = x.right; x.right = y; y.left = t3; //更新x和y的高度 y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1; x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1; return x; }左旋（RR）
- 根节点（Y）的右孩子代替根节点地位
- （X）的左子树变为（Y）的右子树
- （Y）自身变为（X）的左子树
代码逻辑为：
x.left = y;y.right = t3;动图如下：
LR和RL
LR的状况
如下图这样的状况，咱们插入一个节点10，这个时候10和12都比8大，咱们不论是应用LL还是RR都无奈达到成果。
咱们首先能够对x节点进行左旋，失去如下图所示，这样我就会发现以后树结构曾经变成了LL的状况，咱们进行右旋即可。
动图演示：
RL的状况
RL和LR其实是对称的关系。
咱们首先将x进行右旋，而后转换为RR的状况，再进行左旋即可。
// 向以node为根的二分搜寻树中插入元素(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); } else // key.compareTo(node.key) == 0 { node.value = value; } // 更新height node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right)); // 计算均衡因子 int balanceFactor = getBalanceFactor(node); if (Math.abs(balanceFactor) > 1) { System.out.println("unbalanced : " + balanceFactor); } //均衡保护 LL if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) { return rightRotate(node); } //均衡保护 RR if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) { return leftRotate(node); } //均衡保护 LR if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) { node.left = leftRotate(node.left); return rightRotate(node); } //均衡保护 RL if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) { node.right = rightRotate(node.right); return leftRotate(node); } return node; }从AVL中删除元素
删除和增加代码相似，具体也是删除元素后进行均衡保护。
// 从二分搜寻树中删除键为key的节点 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 { // key.compareTo(node.key) == 0 // 待删除节点左子树为空的状况 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; } // 更新height retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right)); // 计算均衡因子 int balanceFactor = getBalanceFactor(retNode); if (Math.abs(balanceFactor) > 1) { System.out.println("unbalanced : " + balanceFactor); } //均衡保护 LL if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) { return rightRotate(retNode); } //均衡保护 RR if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) { return leftRotate(retNode); } //均衡保护 LR if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) { node.left = leftRotate(retNode.left); return rightRotate(retNode); } //均衡保护 RL if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) { node.right = rightRotate(retNode.right); return leftRotate(retNode); } return retNode; }