- 首页 > it技术 > >
public class AvlTree {
//平衡二叉树不平衡有四种情况（去除对称其实只有两种）
//即左左，右右，左右，右左（可自行画图脑补）
//对应解决办法为 左旋 右旋 先左旋后右旋先右旋后左旋
//这里写的是最直观最简单也是效率比较低的写法
class TreeNode{
int val;
int height;
TreeNode left;
TreeNode right;
public TreeNode(int val){
this.val=val;
}
}
//获取树的高度
public int height(TreeNode t){
if(t==null){
return -1;
}else{
return t.height;
}
}
//leet获取高度
public int height2(TreeNode t){
if(t==null){
return 0;
}
return 1+Math.max(height(t.left),height(t.right));
}
//插入节点
public TreeNode insert(int val,TreeNode t){
if(t==null){
return new TreeNode(val);
}
if(valt.val){
//插入右子树
t.right=insert(val,t.right);
}else{
//不考虑重复节点情况，所以啥都不做
}
//是树成为平衡二叉树
returnbalance(t);
}private TreeNode balance(TreeNode t) {
if(t==null){
return t;
}
if(height(t.left)-height(t.right)>1){
if(height(t.left.left)>=height(t.left.right)){
//左左情况,单旋
t=rotateWithLeftChild(t);
}else{
//左右情况，双旋
t=doubleWithRightChild(t);
}
}
if(height(t.right)-height(t.left)>1){
if(height(t.right.right)>=height(t.right.left)){
//右右情况，单旋
t=rotateWithRightChild(t);
}else{
//右左情况，双旋
t=doubleWithLeftChild(t);
}
}
t.height=Math.max(height(t.left),height(t.right))+1;
return t;
}
//左右
private TreeNode doubleWithRightChild(TreeNode t) {
t.left=rotateWithLeftChild(t.left);
return rotateWithRightChild(t);
}
//右左
private TreeNode doubleWithLeftChild(TreeNode t) {
t.right=rotateWithRightChild(t.right);
return rotateWithLeftChild(t);
}
//右右
private TreeNode rotateWithRightChild(TreeNode t) {
TreeNode t1=t.right;
TreeNode t2=t1.right;
TreeNode t3=t1.left;
t.right=t3;
t1.left=t;
return t1;
}
//左左
private TreeNode rotateWithLeftChild(TreeNode t) {
TreeNode t1=t.left;
TreeNode t2=t1.left;
TreeNode t3=t1.right;
t.left=t3;
t1.right=t;
return t1;
}
}
推荐阅读
