平衡查詢樹
AVL樹
在計算機科學中，
AVL樹
是最先發明的自平衡二叉查詢樹。在AVL樹中任何節點的兩個子樹的高度最大差別為1，所以它也被稱為
高度平衡樹
。增加和刪除可能需要透過一次或多次樹旋轉來重新平衡這個樹。
特點
AVL樹本質上還是一棵二叉搜尋樹，它的特點是： ［1］
1。本身首先是一棵二叉搜尋樹。
2。帶有平衡條件：每個結點的左右子樹的高度之差的絕對值（平衡因子）最多為1。
也就是說，AVL樹，本質上是帶了平衡功能的二叉查詢樹（二叉排序樹，二叉搜尋樹）。
單旋轉
右旋轉
思路分析：
1、回溯找到失去平衡的節點，以該節點為根，建立一個新節點
2、把新節點的右子樹設定為當前節點的右子樹
3、把新節點的左子樹設定為當前節點的左子樹的右子樹
4、把當前節點的值換為左子節點的值
5、把當前節點的左子樹設定為左子樹的左子樹
6、把當前節點的右子樹設定為新節點
程式碼實現：
/** * @Title： rotateRight * @Description：右旋操作 * 1、回溯找到失去平衡的節點，以該節點為根，建立一個新節點 * 2、把新節點的右子樹設定為當前節點的右子樹 * 3、把新節點的左子樹設定為當前節點的左子樹的右子樹 * 4、把當前節點的值換位左子節點的值 * 5、把當前節點的左子樹設定為左子樹的左子樹 * 6、把當前節點的右子樹設定為新節點 * @param： * @return： void * @throws */ private void rotateRight（） { //1、回溯找到失去平衡的節點，以該節點為根，建立一個新節點 Node tempNode = new Node（data）； //2、把新節點的右子樹設定為當前節點的右子樹 tempNode。right = right； //3、把新節點的左子樹設定為當前節點的左子樹的右子樹 tempNode。left = left。right； //4、把當前節點的值換位左子節點的值 data = left。data； //5、把當前節點的左子樹設定為左子樹的左子樹 left = left。left； //6、把當前節點的右子樹設定為新節點 right = tempNode； }
左旋轉
思路分析：
1、回溯找到失去平衡的節點，以該節點為根，建立一個新節點
2、把新節點的左子樹設定為當前節點的左子樹
3、把新節點的右子樹設定為當前節點的右子樹的左子樹
4、把當前節點的值替換為右子節點的值
5、把當前節點的右子樹設定為右子樹的右子樹
6、把當前節點的左子樹設定為新節點
程式碼實現：
/** * @Title： rotateLeft * @Description：左旋操作： * 1、回溯找到失去平衡的節點，以該節點為根，建立一個新節點 * 2、把新節點的左子樹設定為當前節點的左子樹 * 3、把新節點的右子樹設定為當前節點的右子樹的左子樹 * 4、把當前節點的值替換為右子節點的值 * 5、把當前節點的右子樹設定為右子樹的右子樹 * 6、把當前節點的左子樹設定為新節點 * @param： * @return： void * @throws */ private void rotateLeft（） { System。out。println（“旋轉程式碼中的 data = ” + data）； //以根節點為參考，建立新的節點 Node tempNode = new Node（data）； //把新節點的左子樹設定為當前節點的左子樹 tempNode。setLeft（left）； //把新節點的右子樹設定為當前節點的右子樹的左子樹 tempNode。setRight（right。left）； //把當前節點的值替換為右子樹的值 data = right。data； //把當前節點的右子樹設定為當前節點右子樹的右子樹 right = right。right； //把當前節點的左子樹設定為新節點 left = tempNode； }
雙旋轉
右-左雙旋轉
//先對當前節點的右孩子右旋
right。rotateRight（）；
//再進行左旋操作
rotateLeft（）；
左-右雙旋轉
//先對當前節點的左孩子進行左旋
left。rotateLeft（）；
//再進行右旋
rotateRight（）；
實現
平衡二叉樹實現增加旋轉功能完整程式碼如下：
/** * All rights Reserved， Designed By https：//www。tulingxueyuan。com/ * @Title： AVLTree。java * @Package com。tuling。tree * @Description： * @author： 小白 * @Date 2019年12月8日 下午10：09：37 * @version V1。0 * @Copyright： */ package com。tuling。tree；/** * @ClassName AVLTree * @Description * @Author 北京圖靈學院 * @Date 2019年12月8日 下午10：09：37 */public class AVLTree { private Node root； /** * * @Title： add * @Description： * @param： @param data * @return： void * @throws */ public void add（int data） { System。out。print（“當前新增資料：” + data + “ ”）； if（root == null） { root = new Node（data）； }else { root。add（data）； } } /** * @Title： rotateLeft * @Description：左旋操作 * @param： node * @return： void * @throws */ private Node rotateLeft（Node nodeN） { Node nodeC = nodeN。getRight（）； nodeN。setRight（nodeC。getLeft（））； nodeC。setLeft（nodeN）； return nodeC； } public void inFixOrder（） { if（root == null） { System。out。println（“樹為空！”）； }else { root。inFixOrder（）； } } public Node getRoot（） { return root； } public void setRoot（Node root） { this。root = root； } class Node{ private Node left，right； private int data； /** * @Title： Node * @Description： * @param： @param data * @throws */ public Node（int data） { this。data = data； } /** * @Title： add * @Description： * @param： data * @return： void * @throws */ public void add（int data） { if（this。data > data） { if（this。left == null） { this。left = new Node（data）； }else { this。left。add（data）； } }else if（this。data < data） { if（this。right == null） { this。right = new Node（data）； }else { this。right。add（data）； } } //TODO： //做完新增操作， if（leftHeight（） - rightHeight（） > 1） {//如果左子樹的高度大於右子樹的高度，需要右旋操作。 if（left！=null && this。left。rightHeight（）>left。leftHeight（）） { System。out。print（“左旋再右旋 —— ” + left。data）； //先對當前節點的左孩子進行左旋 left。rotateLeft（）； //再進行右旋 rotateRight（）； }else { System。out。print（“右旋” + data）； //直接右旋即可 rotateRight（）； } } if（rightHeight（） - leftHeight（） > 1） {//如果右子樹的高度大於左子樹的高度，需要左旋操作 if（right！=null && right。leftHeight（）>right。rightHeight（）） { System。out。print（“右旋再左旋 —— ” + right。data ）； //先物件當前節點的右孩子右旋 right。rotateRight（）； //再進行左旋操作 rotateLeft（）； }else { System。out。print（“左旋 —— ” + data）； //直接左旋節課 rotateLeft（）； } } } /** * @Title： rotateRight * @Description：右旋操作 * 1、回溯找到失去平衡的節點，以該節點為根，建立一個新節點 * 2、把新節點的右子樹設定為當前節點的右子樹 * 3、把新節點的左子樹設定為當前節點的左子樹的右子樹 * 4、把當前節點的值換位左子節點的值 * 5、把當前節點的左子樹設定為左子樹的左子樹 * 6、把當前節點的右子樹設定為新節點 * @param： * @return： void * @throws */ private void rotateRight（） { //1、回溯找到失去平衡的節點，以該節點為根，建立一個新節點 Node tempNode = new Node（data）； //2、把新節點的右子樹設定為當前節點的右子樹 tempNode。right = right； //3、把新節點的左子樹設定為當前節點的左子樹的右子樹 tempNode。left = left。right； //4、把當前節點的值換位左子節點的值 data = left。data； //5、把當前節點的左子樹設定為左子樹的左子樹 left = left。left； //6、把當前節點的右子樹設定為新節點 right = tempNode； } /** * @Title： rotateLeft * @Description：左旋操作： * 1、回溯找到失去平衡的節點，以該節點為根，建立一個新節點 * 2、把新節點的左子樹設定為當前節點的左子樹 * 3、把新節點的右子樹設定為當前節點的右子樹的左子樹 * 4、把當前節點的值替換為右子節點的值 * 5、把當前節點的右子樹設定為右子樹的右子樹 * 6、把當前節點的左子樹設定為新節點 * @param： * @return： void * @throws */ private void rotateLeft（） { System。out。println（“旋轉程式碼中的 data = ” + data）； //以根節點為參考，建立新的節點 Node tempNode = new Node（data）； //把新節點的左子樹設定為當前節點的左子樹 tempNode。setLeft（left）； //把新節點的右子樹設定為當前節點的右子樹的左子樹 tempNode。setRight（right。left）； //把當前節點的值替換為右子樹的值 data = right。data； //把當前節點的右子樹設定為當前節點右子樹的右子樹 right = right。right； //把當前節點的左子樹設定為新節點 left = tempNode； } /** * @Title： rightHeight * @Description： * @param： @return * @return： int * @throws */ private int rightHeight（） { if（right == null） { return 0； } return height（right）； } /** * @Title： height * @Description： * @param： * @return： int * @throws */ private int height（Node node） { if（node == null） return 0； return 1+Math。max（height（node。left）， height（node。right））； } /** * @Title： leftHeight * @Description： * @param： @return * @return： int * @throws */ private int leftHeight（） { if（left == null）return 0； return height（left）； } /** * @Title： inFixOrder * @Description： * @param： * @return： void * @throws */ public void inFixOrder（） { if（this。left！=null） { this。left。inFixOrder（）； } System。out。println（this。data）； if（this。right！=null） { this。right。inFixOrder（）； } } public Node getLeft（） { return left； } public void setLeft（Node left） { this。left = left； } public Node getRight（） { return right； } public void setRight（Node right） { this。right = right； } public int getData（） { return data； } public void setData（int data） { this。data = data； } }}
