AVL樹

AVL樹具有最嚴苛的平衡性，（增、刪、改、查）時間復雜度為O（logN），AVL樹任何一個節(jié)點，左樹的高度和右樹的高度差不超過1（<2）
和SB樹，紅黑樹時間復雜度一樣，只是不同的人搞出了不同的平衡性。
AVL樹就是一顆搜索二叉樹和搜索二叉樹的區(qū)別主要是做完屬于搜索二叉樹的調整之后有專屬于自己平衡性的補丁。
搜索二叉樹加節(jié)點，則小于根節(jié)點的掛左邊，大于根節(jié)點的掛右邊
搜索二叉樹刪除節(jié)點分情況：
1、當找到了要刪除的節(jié)點X之后，X既沒有左子樹也沒有右子樹，則直接刪除
2、找到了要刪除的節(jié)點X之后，X有左但無右，那么直接讓這個刪除節(jié)點的X的左子樹完全替代X
3、如果要刪除的節(jié)點X，X無左有右，那么直接讓右子樹替代X
4、如果要刪除的X既有左又有右，可以找左樹的最右節(jié)點（最大節(jié)點）或者右樹的最左節(jié)點（最小節(jié)點）代替X

AVL樹平衡性

破壞平衡性操作：
LL：

需要調整為如下：

LR：

同理還有RR和RL型違規(guī)破壞平衡性。

如下圖（LR型違規(guī)：只要是LR型違規(guī)。則讓那個孫節(jié)點跑上去保持平衡）：

可知樹的不平衡原因為：B的右子樹導致的整棵樹不平衡，則需要讓C來到A節(jié)點的位置，那么需要在BC這棵樹上對B來一個左旋，得到下圖結果：

然后再對A來一個右旋C就上去了：

RL型違規(guī)：

則讓它的孫子節(jié)點頂上來就完事了，先在B上面執(zhí)行一個右旋，讓C頂上來，再在整棵樹上執(zhí)行一個A的左旋那么最后的C就上來了。

有一個細節(jié)：
有沒有可能既是LL型違規(guī)又是LR型違規(guī)：
一棵樹的左子樹對應的左子樹高度和這棵樹的右子樹對應的右子樹高度一樣所造成的不平衡是LL和LR型違規(guī)

如上圖假設平衡二叉樹左樹高度為7右樹高度為6，在某個時間右樹刪除一個數(shù)導致右樹高度為5了，B的左樹和右樹高度都是6，我的失誤既來自LL型又來自LR型

此時一定要按照LL型來調整，直接右旋(總能保證有效)。

如果用LR的方式來調整，則可能不對：有如下圖

A的左樹高度是7A的右樹高度為5，如果這個例子按照LL型調整：會發(fā)現(xiàn)這棵樹的高度是異常平衡的

如果按照LR方式來調整：如果將S的高度調整成4的話
這樣調整出來的K，S則不平了

再來一個不平衡的：

按照LR方式進行調整，z替代y的位置

y接受了z的左空子樹，y的右邊是沒有東西的，最后調整成這樣：

綜上：
總結：LL型違規(guī)只用進行一次右旋，LR型違規(guī)則需要進行一次小范圍的左旋，再執(zhí)行整棵樹的右旋，RL型違規(guī)則需要先進行小范圍上的右旋，再進行整棵樹的左旋，RR型只需要進行一次左旋，時間復雜度均為O（1）

AVL樹加入節(jié)點

加入一個節(jié)點之后需要依次查詢加入的節(jié)點中了哪種類型的違規(guī)，如果未找到違規(guī)則找其對應的父節(jié)點，如果父節(jié)點未違規(guī)則繼續(xù)找父節(jié)點對應的父節(jié)點，一直找到根節(jié)點未違規(guī)為止。
所以AVL樹調整不是只對一個節(jié)點查是沿途所有節(jié)點都需要查（防止旋轉一次后其上的節(jié)點還需要旋轉），整體時間復雜度為O（logN）的調整代價，

如下圖加入一個節(jié)點X首先看當前X節(jié)點是平的，再看X對應的父節(jié)點也是平的，最終找到方框標記的節(jié)點發(fā)現(xiàn)不再平衡了，左樹高度為1，右樹高度為3，而且是RR型違規(guī)

則需要進行左旋

AVL刪除節(jié)點

分為以下情況：
1、X節(jié)點既沒有左也沒有右子樹，這種情況只需要從刪除節(jié)點開始算上面每一個父都要全查一遍。
2、X節(jié)點有右無左，直接拿右孩子替換原來的X，然后從右孩子來到的位置往上查詢一遍
3、X節(jié)點既有左又有右孩子，看如下例子

如果此處要刪掉7，則需要找到7對應右孩子的最小值8去替換7的位置，調整成如下圖的樣子，此時只需要從9開始查它的父節(jié)點依次調整即可，

AVL樹代碼

右旋步驟：

1、當前樹的左邊去接管左孩子的右

2、左孩子的右會接管cur

參照代碼：

	//右旋private AVLNode<K, V> rightRotate(AVLNode<K, V> cur) {//記錄左孩子AVLNode<K, V> left = cur.l;//左孩子的右樹掛載當前樹的左邊cur.l = left.r;//左孩子的右接管curleft.r = cur;//高度也得接管（現(xiàn)在左孩子和右孩子的高度最大的那個再加1）cur.h = Math.max((cur.l != null ? cur.l.h : 0), (cur.r != null ? cur.r.h : 0)) + 1;left.h = Math.max((left.l != null ? left.l.h : 0), (left.r != null ? left.r.h : 0)) + 1;//右旋以left做頭節(jié)點返回return left;}

再看AVL樹add節(jié)點：
當前來到cur節(jié)點，要加的key是啥要加的value是啥，搜索二叉樹潛臺詞為加入的key都不一樣

public class Code_AVLTreeMap {public static class AVLNode<K extends Comparable<K>, V> {public K k;public V v;//左孩子及右孩子public AVLNode<K, V> l;public AVLNode<K, V> r;//高度public int h;public AVLNode(K key, V value) {k = key;v = value;h = 1;}}public static class AVLTreeMap<K extends Comparable<K>, V> {//根節(jié)點private AVLNode<K, V> root;//一共加入多少個節(jié)點private int size;public AVLTreeMap() {root = null;size = 0;}//右旋private AVLNode<K, V> rightRotate(AVLNode<K, V> cur) {//記錄左孩子AVLNode<K, V> left = cur.l;//左孩子的右樹掛載當前樹的左邊cur.l = left.r;//左孩子的右接管curleft.r = cur;//高度也得接管（現(xiàn)在左孩子和右孩子的高度最大的那個再加1）cur.h = Math.max((cur.l != null ? cur.l.h : 0), (cur.r != null ? cur.r.h : 0)) + 1;left.h = Math.max((left.l != null ? left.l.h : 0), (left.r != null ? left.r.h : 0)) + 1;//右旋以left做頭節(jié)點返回return left;}//左旋private AVLNode<K, V> leftRotate(AVLNode<K, V> cur) {AVLNode<K, V> right = cur.r;cur.r = right.l;right.l = cur;cur.h = Math.max((cur.l != null ? cur.l.h : 0), (cur.r != null ? cur.r.h : 0)) + 1;right.h = Math.max((right.l != null ? right.l.h : 0), (right.r != null ? right.r.h : 0)) + 1;return right;}//平衡性調整private AVLNode<K, V> maintain(AVLNode<K, V> cur) {if (cur == null) {return null;}int leftHeight = cur.l != null ? cur.l.h : 0;int rightHeight = cur.r != null ? cur.r.h : 0;//此時左右樹高度差大于1不平衡了if (Math.abs(leftHeight - rightHeight) > 1) {//左樹高還是右樹高if (leftHeight > rightHeight) {//左樹高int leftLeftHeight = cur.l != null && cur.l.l != null ? cur.l.l.h : 0;int leftRightHeight = cur.l != null && cur.l.r != null ? cur.l.r.h : 0;//左樹的左樹高度大于等于右樹的右樹高度則LL型if (leftLeftHeight >= leftRightHeight) {//LL型違規(guī)cur = rightRotate(cur);} else {//LR型違規(guī)cur.l = leftRotate(cur.l);cur = rightRotate(cur);}} else {int rightLeftHeight = cur.r != null && cur.r.l != null ? cur.r.l.h : 0;int rightRightHeight = cur.r != null && cur.r.r != null ? cur.r.r.h : 0;if (rightRightHeight >= rightLeftHeight) {//RRcur = leftRotate(cur);} else {//RLcur.r = rightRotate(cur.r);cur = leftRotate(cur);}}}return cur;}private AVLNode<K, V> findLastIndex(K key) {AVLNode<K, V> pre = root;AVLNode<K, V> cur = root;while (cur != null) {pre = cur;if (key.compareTo(cur.k) == 0) {break;} else if (key.compareTo(cur.k) < 0) {cur = cur.l;} else {cur = cur.r;}}return pre;}private AVLNode<K, V> findLastNoSmallIndex(K key) {AVLNode<K, V> ans = null;AVLNode<K, V> cur = root;while (cur != null) {if (key.compareTo(cur.k) == 0) {ans = cur;break;} else if (key.compareTo(cur.k) < 0) {ans = cur;cur = cur.l;} else {cur = cur.r;}}return ans;}private AVLNode<K, V> findLastNoBigIndex(K key) {AVLNode<K, V> ans = null;AVLNode<K, V> cur = root;while (cur != null) {if (key.compareTo(cur.k) == 0) {ans = cur;break;} else if (key.compareTo(cur.k) < 0) {cur = cur.l;} else {ans = cur;cur = cur.r;}}return ans;}//AVL樹加節(jié)點private AVLNode<K, V> add(AVLNode<K, V> cur, K key, V value) {if (cur == null) {//如果當前樹為null，則新建節(jié)點return new AVLNode<K, V>(key, value);} else {//如果key小于當前樹的kif (key.compareTo(cur.k) < 0) {//我去左樹上面找，頭部調整為當前節(jié)點的左樹//之所以用cur.l = xxx 是因為這條記錄掛在左樹上是可能換頭的//需要將返回值由我的頭指針的左子樹重新指一下接住cur.l = add(cur.l, key, value);} else {//右樹上掛cur.r = add(cur.r, key, value);}//我自己的高度調整對cur.h = Math.max(cur.l != null ? cur.l.h : 0, cur.r != null ? cur.r.h : 0) + 1;//做平衡調整return maintain(cur);}}// 在cur這棵樹上，刪掉key所代表的節(jié)點// 返回cur這棵樹的新頭部private AVLNode<K, V> delete(AVLNode<K, V> cur, K key) {if (key.compareTo(cur.k) > 0) {cur.r = delete(cur.r, key);} else if (key.compareTo(cur.k) < 0) {cur.l = delete(cur.l, key);} else {if (cur.l == null && cur.r == null) {cur = null;} else if (cur.l == null && cur.r != null) {cur = cur.r;} else if (cur.l != null && cur.r == null) {cur = cur.l;} else {AVLNode<K, V> des = cur.r;while (des.l != null) {des = des.l;}//調用右樹刪除整個k，同時調整了平衡cur.r = delete(cur.r, des.k);des.l = cur.l;des.r = cur.r;cur = des;}}if (cur != null) {cur.h = Math.max(cur.l != null ? cur.l.h : 0, cur.r != null ? cur.r.h : 0) + 1;}return maintain(cur);}public int size() {return size;}public boolean containsKey(K key) {if (key == null) {return false;}AVLNode<K, V> lastNode = findLastIndex(key);return lastNode != null && key.compareTo(lastNode.k) == 0 ? true : false;}public void put(K key, V value) {if (key == null) {return;}AVLNode<K, V> lastNode = findLastIndex(key);if (lastNode != null && key.compareTo(lastNode.k) == 0) {lastNode.v = value;} else {size++;root = add(root, key, value);}}public void remove(K key) {if (key == null) {return;}if (containsKey(key)) {size--;root = delete(root, key);}}public V get(K key) {if (key == null) {return null;}AVLNode<K, V> lastNode = findLastIndex(key);if (lastNode != null && key.compareTo(lastNode.k) == 0) {return lastNode.v;}return null;}public K firstKey() {if (root == null) {return null;}AVLNode<K, V> cur = root;while (cur.l != null) {cur = cur.l;}return cur.k;}public K lastKey() {if (root == null) {return null;}AVLNode<K, V> cur = root;while (cur.r != null) {cur = cur.r;}return cur.k;}public K floorKey(K key) {if (key == null) {return null;}AVLNode<K, V> lastNoBigNode = findLastNoBigIndex(key);return lastNoBigNode == null ? null : lastNoBigNode.k;}public K ceilingKey(K key) {if (key == null) {return null;}AVLNode<K, V> lastNoSmallNode = findLastNoSmallIndex(key);return lastNoSmallNode == null ? null : lastNoSmallNode.k;}}}