左旋转
image.png
右旋转
image.png
双旋转
image.png
左旋右旋规律
右旋右低，左旋左低，
左高右旋，右高左旋
左旋动左。
右旋动右。
新节点
代替当前根节点。
左旋，新节点右子树=右子树左子节点。
右旋，新节点左子树=左子树右子节点。
根节点
左旋，值=右子节点值，右子树=右子树右子节点，左子树=新节点
右旋，值=左子节点值，左子树=左子树左子节点，右子树=新节点。
最终版口诀：
左旋动右给左（新节点），根=右
右旋动左给右（新节点），根=左
code
Node
package com.pl.arithmetic.binaryTree.avl;
/**
* <p>
*
* @Description: TODO
* </p>
* @ClassName Node
* @Author pl
* @Date 2020/11/14
* @Version V1.0.0
*/
public class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
// AVLTree ---------------------------------------
public int leftHeight(){
if (left == null){
return 0;
}
return left.height();
}
public int rightHeight(){
if (right == null){
return 0;
}
return right.height();
}
/**
* 计算当前节点的树高度
*
* @param
* @return int
* @exception
* @author silenter
* @date 2020/11/20 7:28
*/
public int height(){
return Math.max(left == null ?0:left.height(),right == null?0:right.height())+1;
}
/**
* 左旋前提右子树高于左子树
* 左旋右旋
*
* 创建新节点，代替当前根节点，左子树和当前节点一样，右子树变成右子树的左子树
* 右子树等于当前节点右子树的右子节点，当前节点的值等于右子节点的值，当前节点左子树指向新节点，
*
* @param
* @return void
* @exception
* @author silenter
* @date 2020/11/20 8:13
*/
public void leftRoute(){
Node newNode = new Node(this.value);
newNode.left = this.left;
newNode.right = this.right.left;
this.value = right.value;
this.right = right.right;
this.left = newNode;
}
/**
* 右旋的前提，左子树高于右子树
*
* @param
* @return void
* @exception
* @author silenter
* @date 2020/11/20 8:14
*/
public void rightRoute(){
Node newNode = new Node(this.value);
newNode.left = left.right;
newNode.right = right;
value = left.value;
left = left.left;
right = newNode;
}
/**
* 添加节点 和bst相比，只有添加不同
*
* @param node
* @return void
* @exception
* @author silenter
* @date 2020/11/14 9:31
*/
public void addNode(Node node){
verifyNode(node);
if (node.value<this.value){
if (this.left!=null){
this.left.addNode(node);
}else if (this.left == null){
this.left = node;
}
}
if (node.value>this.value){
if (this.right!=null){
this.right.addNode(node);
}else if (this.right == null){
this.right = node;
}
}
//左高右旋
if (leftHeight()-rightHeight()>1){
if (right != null && left.rightHeight()>left.leftHeight()){
left.leftRoute();
rightRoute();
}else {
rightRoute();
}
}
//右高左旋
if (rightHeight()-leftHeight()>1){
if (right != null && right.leftHeight()>right.rightHeight()){
right.rightRoute();
leftRoute();
}else {
leftRoute();
}
}
}
// AVLTree ---------------------------------------
public Node searchRightMixNode(Node node){
Node tempNode = node;
while (tempNode.left!=null){
tempNode = tempNode.left;
}
return tempNode;
}
/**
* 查找指定节点
*
* @param value
* @return com.pl.arithmetic.binaryTree.binarySearchTree.Node
* @exception
* @author silenter
* @date 2020/11/14 10:18
*/
public Node searchNode(int value){
Node tempNode = null;
if (this.value == value){
tempNode = this;
System.out.println("找到指定节点");
return tempNode;
}
if (tempNode ==null){
if (value<this.value && this.left!=null){
tempNode = this.left.searchNode(value);
}
if (value>this.value&&this.right!=null){
tempNode = this.right.searchNode(value);
}
}
return tempNode;
}
/**
* 查找当前节点的父节点
*
* @param value
* @return com.pl.arithmetic.binaryTree.binarySearchTree.Node
* @exception
* @author silenter
* @date 2020/11/14 9:32
*/
public Node searchParentNode(int value){
if ((this.left !=null && this.left.value == value) || (this.right !=null && this.right.value == value)){
System.out.println("找到该父节点"+this);
return this;
}else{
if (value <this.value && this.left!=null){
return this.left.searchParentNode(value);
}else if (value>this.value && this.right!=null) {
return this.right.searchParentNode(value);
}
}
return null;
}
/**
* 前序遍历
*
* @param
* @return void
* @exception
* @author silenter
* @date 2020/11/14 9:19
*/
//中序遍历
public void infixOrder() {
if(this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if(this.right != null) {
this.right.infixOrder();
}
}
public void verifyNode(Node node){
if (node ==null){
throw new RuntimeException("node为空");
}
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}
AVLTree
package com.pl.arithmetic.binaryTree.avl;
/**
* <p>
*
* @Description: TODO
* </p>
* @ClassName AVLTree
* @Author pl
* @Date 2020/11/20
* @Version V1.0.0
*/
public class AVLTree {
private Node root;
public Node getRoot() {
return root;
}
// 添加结点的方法
public void add(Node node) {
if (root == null) {
root = node;// 如果root为空则直接让root指向node
} else {
root.addNode(node);
}
}
// 中序遍历
public void infixOrder() {
if (root != null) {
root.infixOrder();
} else {
System.out.println("二叉排序树为空，不能遍历");
}
}
}
AVLTreeDemo
package com.pl.arithmetic.binaryTree.avl;
/**
* <p>
*
* @Description: TODO
* </p>
* @ClassName AVLTreeDemo
* @Author pl
* @Date 2020/11/20
* @Version V1.0.0
*/
public class AVLTreeDemo {
public static void main(String[] args) {
//int[] arr = {4,3,6,5,7,8};
//int[] arr = { 10, 12, 8, 9, 7, 6 };
int[] arr = { 10, 11, 7, 6, 8, 9 };
//创建一个 AVLTree对象
AVLTree avlTree = new AVLTree();
//添加结点
for(int i=0; i < arr.length; i++) {
avlTree.add(new Node(arr[i]));
}
//遍历
System.out.println("中序遍历");
avlTree.infixOrder();
System.out.println("在平衡处理~~");
System.out.println("树的高度=" + avlTree.getRoot().height()); //3
System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight()); // 2
System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight()); // 2
System.out.println("当前的根结点=" + avlTree.getRoot());//8
}
}
网友评论