平衡查找樹
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;
}
}
}
