package com.xiejianjun.day11;
import com.xiejianjun.day10.BinarySortTree;
public class AVLTree {
public static void main(String[] args) {
int[] tree = {4, 3, 6, 5, 7, 8};
for (int i = 0; i < tree.length; i++) {
if (root == null) {
root = new Node(tree[i]);
continue;
}
root.add(new Node(tree[i]));
}
AVLTree sortTree = new AVLTree();
System.out.println("========================== 中序遍历二叉平衡树 =================================="); // 3 4 5 6 7 8
sortTree.inOrder(root);
System.out.println("n======================= 平衡二叉树之后的左子树高度为 " + root.leftHeight() + " ==========================="); // 1
System.out.println("======================= 平衡二叉树之后的右子树高度为 " + root.rightHeight() + " ==========================="); // 3
}
public static Node root;
public void inOrder(Node root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.print("t" + root.value + "t");
inOrder(root.right);
}
int delRightTreeMin(Node node) {
int result = 0;
if (node != null) {
while (node.left != null) {
node = node.left;
}
result = node.value;
deleteNode(node.value);
}
return result;
}
public void deleteNode(int value) {
if (root == null) return;
Node target = root.search(value);
if (target == null) return;
// 1、删除结点正好为根节点,其此时根节点左右子树为空:
if (root.left == null && root.right == null) {
root = null;
return;
}
// 2、删除结点不为根节点的情况:
Node parent = root.searchParent(value);
// 2.1、删除结点为叶子结点
if (target.left == null && target.right == null) {
if (parent.left != null && parent.left.value == value) {
parent.left = null;
} else if (parent.right != null && parent.right.value == value) {
parent.right = null;
}
// 2.2、删除结点为带两个子节点的结点
} else if (target.left != null && target.right != null) {
// 删除被删除结点的左子树的最小值的结点，并将最小值放入被删除结点处
target.value = delRightTreeMin(target.right);
}
// 2.3、删除结点为带一个子节点的结点
else {
if (target.left != null) {
if (parent != null) {
if (parent.left != null && parent.left.value == target.value) {
parent.left = target.left;
} else if (parent.right != null && parent.right.value == target.value) {
parent.right = target.left;
}
} else {
root = target.left;
}
} else {
if (parent != null) {
if (parent.left != null && parent.left.value == target.value) {
parent.left = target.right;
} else if (parent.right != null && parent.right.value == target.value) {
parent.right = target.right;
}
} else {
root = target.right;
}
}
}
}
static class Node {
int value;
Node left;
Node right;
Node(int value) {
this.value = value;
}
void add(Node node) {
if (this.value > node.value) {
if (this.left == null) this.left = node;
else this.left.add(node);
} else {
if (this.right == null) this.right = node;
else this.right.add(node);
}
if (rightHeight() - leftHeight() > 1) {
if (right.leftHeight() - right.rightHeight() > 1) {
right.rightRotate();
leftRotate();
} else {
leftRotate();
}
}
if (leftHeight() - rightHeight() > 1) {
// 如果右旋时发现当前结点的左节点的右子树大于左子树的高度,则做双旋转，把高度大的子树放到左边
// 这样做是避免右旋后新节点连接的左结点的右子树高度过大导致当前结点的树结构不平衡
if (left.rightHeight() > left.leftHeight()) {
left.leftRotate();
rightRotate();
}else {
rightRotate();
}
}
}
Node search(int value) {
if (this.value == value) {
return this;
}
if (this.left != null && value < this.value) return this.left.search(value);
else if (this.right != null) return this.right.search(value);
return null;
}
int height() {
// 说实话,这递归挺逆天,这是怎么想出来的
return Math.max((left == null) ? 0 : left.height(), (right == null) ? 0 : right.height()) + 1;
}
int leftHeight() {
if (left != null) return left.height();
return 0;
}
int rightHeight() {
if (right != null) return right.height();
return 0;
}
Node searchParent(int value) {
if (this.left != null && this.left.value == value) {
return this;
} else if (this.right != null && this.right.value == value) {
return this;
}
if (this.left != null && value < this.value) {
return this.left.searchParent(value);
} else if (this.right != null && value > this.value) {
return this.right.searchParent(value);
}
return null;
}
// 左旋
void leftRotate() {
// 创建一个新的结点
Node newNode = new Node(value);
// 让新节点的左指针指向当前结点的左节点
newNode.left = left;
// 让新节点的右指针指向当前节点的右节点的左孩子
newNode.right = right.left;
// 让当前值替换为右节点的值
value = right.value;
// 让当前节点的左指针指向新节点
left = newNode;
// 让当前节点的右指针指向右指针的右指针
right = right.right;
}
// 右旋
void rightRotate() {
// 创建一个新的结点
Node newNode = new Node(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
right = newNode;
left = left.left;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}
}
