package com.dy.xidian;
public class AVL {
private Node root;
static class Node{
int val;
//存储数据
int height;
//权重
Node LChild;
//右孩子
Node RChild;
//左孩子
public Node(
int k,
int _height){
this.val =
k;
this. height =
_height;
}
}
private void initAVL(
int[] arr){
for(
int i : arr)
root =
insert(root, i);
}
public AVL(
int[] arr){
initAVL(arr);
}
//右旋
private Node RRotate(Node node){
Node A =
node;
Node B =
node.LChild;
//旋转
Node tmp =
B.RChild;
B.RChild =
A;
A.LChild =
tmp;
//更新树的高度
A.height = Math.max(height(A.LChild), height(A.RChild))+1
;
B.height = Math.max(height(B.LChild), height(B.RChild))+1
;
return B;
}
//左旋
private Node LRotate(Node node){
Node A =
node;
Node B =
node.RChild;
//旋转
Node tmp =
B.LChild;
B.LChild =
A;
A.RChild =
tmp;
//更新树的高度
A.height = Math.max(height(A.LChild), height(A.RChild))+1
;
B.height = Math.max(height(B.LChild), height(B.RChild))+1
;
return B;
}
//先左后右旋转
private Node LRRotate(Node node){
//先进行左旋
LRotate(node.LChild);
//在进行右旋
return RRotate(node);
}
//先右后左旋转
private Node RLRotate(Node node){
//再进行右旋转
RRotate(node.RChild);
//再进行右旋
return LRotate(node);
}
//计算树的高度,主要解决空树高度的问题(空树的高度为0)
private int height(Node node){
return node ==
null ? 0
:node.height;
}
public Node insert(Node node,
int i){
//先将节点插入到树中
if(node ==
null)
return new Node(i, 1
);
//插入的值与当前节点值进行比较来确定插入的位置
if(i <
node.val){
node.LChild =
insert(node.LChild, i);
//判断是否进行调整
if(height(node.LChild) - height(node.RChild) == 2
){
if(i <
node.LChild.val)
//插入的节点在左孩子的左子树上，则需要进行右旋
node =
RRotate(node);
else
//插入的节点在左孩子的右子树上，则需要先进行左旋后进行右旋
node =
LRRotate(node);
}
}
else{
node.RChild =
insert(node.RChild, i);
if(height(node.LChild) - height(node.RChild) == -2
){
if(i >
node.RChild.val)
node =
LRotate(node);
else
node =
RLRotate(node);
}
}
node.height = Math.max(height(node.LChild), height(node.RChild))+1
;
return node;
}
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14
};
AVL avl =
new AVL(arr);
}
}
