平衡查找樹
AVL樹
在計算機(jī)科學(xué)中，AVL樹是最先發(fā)明的自平衡二叉查找樹。在AVL樹中任何節(jié)點的兩個子樹的高度最大差別為1，所以它也被稱為高度平衡樹。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個樹。
特點
AVL樹本質(zhì)上還是一棵二叉搜索樹，它的特點是： [1]
1.本身首先是一棵二叉搜索樹。
2.帶有平衡條件：每個結(jié)點的左右子樹的高度之差的絕對值（平衡因子）最多為1。
也就是說，AVL樹，本質(zhì)上是帶了平衡功能的二叉查找樹（二叉排序樹，二叉搜索樹）。
單旋轉(zhuǎn)
右旋轉(zhuǎn)
思路分析：
1、回溯找到失去平衡的節(jié)點，以該節(jié)點為根，創(chuàng)建一個新節(jié)點
2、把新節(jié)點的右子樹設(shè)置為當(dāng)前節(jié)點的右子樹
3、把新節(jié)點的左子樹設(shè)置為當(dāng)前節(jié)點的左子樹的右子樹
4、把當(dāng)前節(jié)點的值換為左子節(jié)點的值
5、把當(dāng)前節(jié)點的左子樹設(shè)置為左子樹的左子樹
6、把當(dāng)前節(jié)點的右子樹設(shè)置為新節(jié)點
代碼實現(xiàn)：
/**
* @Title: rotateRight
* @Description:右旋操作
* 1、回溯找到失去平衡的節(jié)點，以該節(jié)點為根，創(chuàng)建一個新節(jié)點
* 2、把新節(jié)點的右子樹設(shè)置為當(dāng)前節(jié)點的右子樹
* 3、把新節(jié)點的左子樹設(shè)置為當(dāng)前節(jié)點的左子樹的右子樹
* 4、把當(dāng)前節(jié)點的值換位左子節(jié)點的值
* 5、把當(dāng)前節(jié)點的左子樹設(shè)置為左子樹的左子樹
* 6、把當(dāng)前節(jié)點的右子樹設(shè)置為新節(jié)點
* @param:
* @return: void
* @throws
*/
private void rotateRight() {
//1、回溯找到失去平衡的節(jié)點，以該節(jié)點為根，創(chuàng)建一個新節(jié)點
Node tempNode = new Node(data);
//2、把新節(jié)點的右子樹設(shè)置為當(dāng)前節(jié)點的右子樹
tempNode.right = right;
//3、把新節(jié)點的左子樹設(shè)置為當(dāng)前節(jié)點的左子樹的右子樹
tempNode.left = left.right;
//4、把當(dāng)前節(jié)點的值換位左子節(jié)點的值
data = left.data;
//5、把當(dāng)前節(jié)點的左子樹設(shè)置為左子樹的左子樹
left = left.left;
//6、把當(dāng)前節(jié)點的右子樹設(shè)置為新節(jié)點
right = tempNode;
}
左旋轉(zhuǎn)
思路分析：
1、回溯找到失去平衡的節(jié)點，以該節(jié)點為根，創(chuàng)建一個新節(jié)點
2、把新節(jié)點的左子樹設(shè)置為當(dāng)前節(jié)點的左子樹
3、把新節(jié)點的右子樹設(shè)置為當(dāng)前節(jié)點的右子樹的左子樹
4、把當(dāng)前節(jié)點的值替換為右子節(jié)點的值
5、把當(dāng)前節(jié)點的右子樹設(shè)置為右子樹的右子樹
6、把當(dāng)前節(jié)點的左子樹設(shè)置為新節(jié)點
代碼實現(xiàn)：
/**
* @Title: rotateLeft
* @Description:左旋操作：
* 1、回溯找到失去平衡的節(jié)點，以該節(jié)點為根，創(chuàng)建一個新節(jié)點
* 2、把新節(jié)點的左子樹設(shè)置為當(dāng)前節(jié)點的左子樹
* 3、把新節(jié)點的右子樹設(shè)置為當(dāng)前節(jié)點的右子樹的左子樹
* 4、把當(dāng)前節(jié)點的值替換為右子節(jié)點的值
* 5、把當(dāng)前節(jié)點的右子樹設(shè)置為右子樹的右子樹
* 6、把當(dāng)前節(jié)點的左子樹設(shè)置為新節(jié)點
* @param:
* @return: void
* @throws
*/
private void rotateLeft() {
System.out.println("旋轉(zhuǎn)代碼中的 data = " + data);
//以根節(jié)點為參考，創(chuàng)建新的節(jié)點
Node tempNode = new Node(data);
//把新節(jié)點的左子樹設(shè)置為當(dāng)前節(jié)點的左子樹
tempNode.setLeft(left);
//把新節(jié)點的右子樹設(shè)置為當(dāng)前節(jié)點的右子樹的左子樹
tempNode.setRight(right.left);
//把當(dāng)前節(jié)點的值替換為右子樹的值
data = right.data;
//把當(dāng)前節(jié)點的右子樹設(shè)置為當(dāng)前節(jié)點右子樹的右子樹
right = right.right;
//把當(dāng)前節(jié)點的左子樹設(shè)置為新節(jié)點
left = tempNode;
}
雙旋轉(zhuǎn)
右-左雙旋轉(zhuǎn)
//先對當(dāng)前節(jié)點的右孩子右旋
right.rotateRight();
//再進(jìn)行左旋操作
rotateLeft();
左-右雙旋轉(zhuǎn)
//先對當(dāng)前節(jié)點的左孩子進(jìn)行左旋
left.rotateLeft();
//再進(jìn)行右旋
rotateRight();
實現(xiàn)
平衡二叉樹實現(xiàn)增加旋轉(zhuǎn)功能完整代碼如下：
/**
* 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 北京圖靈學(xué)院
* @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("當(dāng)前添加數(shù)據(jù)：" + 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);
//先對當(dāng)前節(jié)點的左孩子進(jìn)行左旋
left.rotateLeft();
//再進(jìn)行右旋
rotateRight();
}else {
System.out.print("右旋" + data);
//直接右旋即可
rotateRight();
}
}
if(rightHeight() - leftHeight() > 1) {//如果右子樹的高度大于左子樹的高度，需要左旋操作
if(right!=null && right.leftHeight()>right.rightHeight()) {
System.out.print("右旋再左旋 -- " + right.data );
//先對象當(dāng)前節(jié)點的右孩子右旋
right.rotateRight();
//再進(jìn)行左旋操作
rotateLeft();
}else {
System.out.print("左旋 -- " + data);
//直接左旋節(jié)課
rotateLeft();
}
}
}
/**
* @Title: rotateRight
* @Description:右旋操作
* 1、回溯找到失去平衡的節(jié)點，以該節(jié)點為根，創(chuàng)建一個新節(jié)點
* 2、把新節(jié)點的右子樹設(shè)置為當(dāng)前節(jié)點的右子樹
* 3、把新節(jié)點的左子樹設(shè)置為當(dāng)前節(jié)點的左子樹的右子樹
* 4、把當(dāng)前節(jié)點的值換位左子節(jié)點的值
* 5、把當(dāng)前節(jié)點的左子樹設(shè)置為左子樹的左子樹
* 6、把當(dāng)前節(jié)點的右子樹設(shè)置為新節(jié)點
* @param:
* @return: void
* @throws
*/
private void rotateRight() {
//1、回溯找到失去平衡的節(jié)點，以該節(jié)點為根，創(chuàng)建一個新節(jié)點
Node tempNode = new Node(data);
//2、把新節(jié)點的右子樹設(shè)置為當(dāng)前節(jié)點的右子樹
tempNode.right = right;
//3、把新節(jié)點的左子樹設(shè)置為當(dāng)前節(jié)點的左子樹的右子樹
tempNode.left = left.right;
//4、把當(dāng)前節(jié)點的值換位左子節(jié)點的值
data = left.data;
//5、把當(dāng)前節(jié)點的左子樹設(shè)置為左子樹的左子樹
left = left.left;
//6、把當(dāng)前節(jié)點的右子樹設(shè)置為新節(jié)點
right = tempNode;
}
/**
* @Title: rotateLeft
* @Description:左旋操作：
* 1、回溯找到失去平衡的節(jié)點，以該節(jié)點為根，創(chuàng)建一個新節(jié)點
* 2、把新節(jié)點的左子樹設(shè)置為當(dāng)前節(jié)點的左子樹
* 3、把新節(jié)點的右子樹設(shè)置為當(dāng)前節(jié)點的右子樹的左子樹
* 4、把當(dāng)前節(jié)點的值替換為右子節(jié)點的值
* 5、把當(dāng)前節(jié)點的右子樹設(shè)置為右子樹的右子樹
* 6、把當(dāng)前節(jié)點的左子樹設(shè)置為新節(jié)點
* @param:
* @return: void
* @throws
*/
private void rotateLeft() {
System.out.println("旋轉(zhuǎn)代碼中的 data = " + data);
//以根節(jié)點為參考，創(chuàng)建新的節(jié)點
Node tempNode = new Node(data);
//把新節(jié)點的左子樹設(shè)置為當(dāng)前節(jié)點的左子樹
tempNode.setLeft(left);
//把新節(jié)點的右子樹設(shè)置為當(dāng)前節(jié)點的右子樹的左子樹
tempNode.setRight(right.left);
//把當(dāng)前節(jié)點的值替換為右子樹的值
data = right.data;
//把當(dāng)前節(jié)點的右子樹設(shè)置為當(dāng)前節(jié)點右子樹的右子樹
right = right.right;
//把當(dāng)前節(jié)點的左子樹設(shè)置為新節(jié)點
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;
}
}
}
