package tree;
/**
* @author: tianhaichao
* @date: 2022/9/22 15:38
* @description:平衡二叉树AVL
* 1、每个节点的左右子树的高度差不大于1 ---> |left.height-right.height|<=1
* 2、每个节点的左右子树也是平衡二叉树
*/
public class AVLTree {
static TreeNode root;
public static void main(String[] args) {
int[] array = new int[]{10, 3, 5, 2, 5, 6, 4, 12, 15, 16, 17, 18};
for (int i : array) {
AVLTree.insert(root, i);
preTraversal(root);
System.out.println("----" + i);
}
System.out.println("==========================");
//排序输出
midTraversal(root);
}
public static class TreeNode {
// 该节点为顶点的子树深度
int height;
int data;
TreeNode leftChild;
TreeNode rightChild;
TreeNode parent;
public TreeNode(int data) {
this.data = data;
}
}
/**
* @author: tianhaichao
* @date: 2022/9/23 09:55
* @description:实现算法使用到了递归
* 用来实现每次变化后，校验、调整树使其达到平衡
*/
public static void insert(TreeNode node, int data) {
if (root == null) {
root = new TreeNode(data);
root.height = 1;
return;
}
if (data >= node.data) {
if (node.rightChild == null) {
//新增叶子结点，没有子树，所以树深为1
TreeNode newNode = new TreeNode(data);
newNode.height = 1;
newNode.parent = node;
node.rightChild = newNode;
} else {
// 递归执行每一层
insert(node.rightChild, data);
}
} else {
if (node.leftChild == null) {
TreeNode newNode = new TreeNode(data);
newNode.height = 1;
newNode.parent = node;
node.leftChild = newNode;
} else {
insert(node.leftChild, data);
}
}
/**
递归 --插入返回后，每一层都执行下面代码校验当前节点是否满足平衡标准，并调整
*/
// 更新子树深度
node.height = calculateSonTreeDeep(node);
// 计算平衡因子，执行调整 左子树大
if (calculateBF(node) >= 2) {
// 判断是否为LR
if (calculateBF(node.leftChild) == 1) {
// LR 先执行左旋转成LL
leftRotate(node.leftChild);
}
// LL 执行右旋
rightRotate(node);
}
// 计算平衡因子，执行调整 右子树大
if (calculateBF(node) <= -2) {
// 判断类型，执行调整
if (calculateBF(node.rightChild) == 1) {
// LR 先执行左旋转成LL
rightRotate(node.rightChild);
}
// LL 执行右旋
leftRotate(node);
}
}
/**
* @author: tianhaichao
* @date: 2022/8/30 14:44
* @description: node 旋转节点 RR 、LR执行左旋
* 1、将右节点上提成为父节点
* 2、父节点转为右节点的左孩子
* 3、父节点的右孩子【替换成】右节点的左孩子，父节点的左孩子不变
* return 旋转完后的父节点，也就是右孩子【将右节点上提成为父节点】
*/
public static TreeNode leftRotate(TreeNode node) {
TreeNode right = node.rightChild;
TreeNode father = node;
// 如果右节点存在左孩子,父节点的右孩子【替换成】右节点的左孩子
father.rightChild = right.leftChild;
// 将右节点上提成为父节点 变成祖父的孩子
if (father.parent == null || father == root) {
root = right;
} else if (father.parent.leftChild == father) {
father.parent.leftChild = right;
} else {
// 如果旋转节点是父节点的右节点
father.parent.rightChild = right;
}
right.parent = father.parent;
// 父节点转为右节点的左孩子
right.leftChild = father;
father.parent = right;
// 调整节点子树高度
father.height = calculateSonTreeDeep(father);
right.height = calculateSonTreeDeep(right);
if (father.parent != null) {
father.parent.height = calculateSonTreeDeep(father.parent);
}
return right;
}
/**
* @return 旋转之后的父节点，也就是左孩子【将左节点上提成为父节点】
* @author: tianhaichao
* @date: 2022/9/20 18:31
* @description: LL或RL执行右旋
* 执行右旋，
* 1、将左节点上提成为父节点
* 2、父节点转为左节点的右孩子
* 3、父节点的左孩子【替换成】左节点的右孩子，父节点的右孩子不变
*/
public static TreeNode rightRotate(TreeNode node) {
TreeNode left = node.leftChild;
TreeNode father = node;
// 父节点的左孩子【替换成】左节点的右孩子，父节点的右孩子不变
father.leftChild = left.rightChild;
//将左节点上提成为父节点
if (father.parent == null || father == root) {
root = left;
} else if (father.parent.rightChild == father) {
father.parent.rightChild = left;
} else {
father.parent.leftChild = left;
}
left.parent = father.parent;
// 父节点转为左节点的右孩子
father.parent = left;
left.rightChild = father;
// 调整节点子树高度
father.height = calculateSonTreeDeep(father);
left.height = calculateSonTreeDeep(left);
if (father.parent != null) {
father.parent.height = calculateSonTreeDeep(father.parent);
}
return left;
}
/**
* @author: tianhaichao
* @date: 2022/9/22 16:34
* @description: 计算平衡因子
*/
public static int calculateBF(TreeNode node) {
if (node == null) {
return 0;
} else if (node.rightChild == null && node.leftChild == null) {
return 0;
} else if (node.leftChild == null) {
return -node.rightChild.height;
} else if (node.rightChild == null) {
return node.leftChild.height;
} else {
return node.leftChild.height - node.rightChild.height;
}
}
/**
* @author: tianhaichao
* @date: 2022/9/22 16:34
* @description: 计算子树深度，TreeNode的height值
*/
public static int calculateSonTreeDeep(TreeNode node) {
if (node == null) {
return 0;
} else if (node.rightChild == null && node.leftChild == null) {
return 1;
} else if (node.leftChild == null) {
return node.rightChild.height + 1;
} else if (node.rightChild == null) {
return node.leftChild.height + 1;
} else {
return Math.max(node.leftChild.height, node.rightChild.height) + 1;
}
}
/**
* @author: tianhaichao
* @date: 2022/9/20 15:10
* @description:中序遍历
*/
public static void midTraversal(TreeNode node) {
if (node == null) {
return;
}
midTraversal(node.leftChild);
System.out.print(node.data + " ");
midTraversal(node.rightChild);
}
/**
* @author: tianhaichao
* @date: 2022/9/20 15:10
* @description:中序遍历
*/
public static void preTraversal(TreeNode node) {
if (node == null) {
return;
}
int left = node.leftChild != null ? node.leftChild.data : 0;
int right = node.rightChild != null ? node.rightChild.data : 0;
System.out.print(node.data + "【" + node.height + " " + left + " " + right + "】" + " ");
preTraversal(node.leftChild);
preTraversal(node.rightChild);
}
}
标签：node,java,TreeNode,height,leftChild,二叉树,newNode,平衡,data From： https://www.cnblogs.com/tianhaichao/p/16721680.html