package com.xd.leetcode.shu;
/**
* created by lianzhen on 2020-03-10 10:27. describe:平衡二叉树的构建
*
* LL：插入的结点在左子树的左边导致失衡：右旋（顺时针旋转）
* RR: 插入的结点在右子树的右边导致失衡：左旋(逆时针方向)
* LR：插入的结点在左子树的右边导致失衡：先按照根节点的左子树左旋再按照根节点进行右旋
* RL：插入的结点在右子树的左边导致失衡：先按照根结点的右子树右旋再按照根节点进行左旋
*/
public class AVLTree {
class Node {
int data; //数据
int height;//高度
Node leftNode;//左节点
Node rightNode;//右节点
public Node(int data, Node leftNode, Node rightNode) {
this.data = data;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
}
//计算每个根节点的高度
private int getHeight(Node tagNode) {
if (tagNode == null) {
return -1;
}
return tagNode.height;
}
//右旋转
private Node rightRotation(Node tagNode) {
//找到这个目标节点的左子树的根节点
Node leftChild = tagNode.leftNode;
if (leftChild.rightNode != null) {
//把自己的右子树作为目标节点的左子树
tagNode.leftNode = leftChild.rightNode;
}
//让目标节点成为自己的右子树
leftChild.rightNode = tagNode;
//重新设置高度
tagNode.height = Math.max(getHeight(tagNode.leftNode), getHeight(tagNode.rightNode)) + 1;
leftChild.height = Math.max(getHeight(leftChild.leftNode), getHeight(leftChild.rightNode) + 1);
return leftChild;
}
//左旋转
private Node leftRotation(Node tagNode) {
//找到这个目标节点的右子树的根节点
Node rightNode = tagNode.rightNode;
if (rightNode.leftNode != null) {
//把自己的左子树作为目标节点的右子树
tagNode.leftNode = rightNode.leftNode;
}
//让目标节点成为自己的左子树
rightNode.leftNode = tagNode;
tagNode.height = Math.max(getHeight(tagNode.leftNode), getHeight(tagNode.rightNode)) + 1;
rightNode.height = Math.max(getHeight(rightNode.leftNode), getHeight(rightNode.rightNode)) + 1;
return rightNode;
}
//左右旋转LR
private Node rightLeftRatation(Node tagNode) {
//先按照目标节点的左子树的根节点进行右旋转
Node leftChild = tagNode.leftNode;
leftRotation(leftChild);
//再按照目标节点进行左旋转
return rightRotation(tagNode);
}
//右左旋转
private Node leftRightRatation(Node tagNode) {
//先按照目标节点的右子树的根节点进行左旋转
Node rightChild = tagNode.rightNode;
rightRotation(rightChild);
//再按照目标节点进行右旋转
return leftRotation(tagNode);
}
/**
* 朝根的节点下方插入新的节点 不需要要考虑那么多 只考虑当前的节点再上一个节点的左边或者右边就行
*
* @param root 根节点
* @param data 需要插入节点的数据
*/
private Node insertNode(Node root, int data) {
if (root == null) {
root = new Node(data, null, null);
}else {
if (data <= root.data) {
//把新的节点放在这个节点的左边
root.leftNode = insertNode(root.leftNode, data);
//判断左右子树的高度
if(getHeight(root.leftNode)-getHeight(root.rightNode)>1){
if(data<=root.leftNode.data){
//插入的位置是左子树的左边 ---进行右旋转
root= rightRotation(root);
}else {
//插入的位置是左子树的右边LR 先左后右旋
root=leftRightRatation(root);
}
}
} else {
//把新的节点放在这个节点的右边
root.rightNode = insertNode(root.rightNode, data);
//判断左右子树的高度
if(getHeight(root.rightNode)-getHeight(root.leftNode)>1){
if(data<=root.leftNode.data){
//进行右左旋转
root= rightLeftRatation(root);
}else {
//进行右旋转
root=rightRotation(root);
}
}
}
}
//对节点的高度进行更新(有可能不变)
root.height=Math.max(getHeight(root.leftNode),getHeight(root.rightNode))+1;
return root;
}
}
AVL树的构建的相关教程结束。
