整合查找
整理自网络ChatGPT产生之内容，文本内容不具备参考意义，程序内容及代码片段有且仅有借鉴意义。
)
*/
public class AVL_Tree {
private static class Node {
int key;
int balance;// 平衡因子
int height;// 高度
Node left;
Node right;
Node(int k) {
key = k;
balance = 0;
height = 1;
left = right = null;
}
}
// 根节点
private Node root;
public AVL_Tree() {
root = null;
}
public Node GetRoot() {
return root;
}
public static int Height(Node node) {
if (node == null)
return 0;
else
return node.height;
}
public static int Balance(Node node) {
if (node == null)
return 0;
return Height(node.left) - Height(node.right);
}
// 前序遍历
public void PreOrderTraversal(Node node) {
if (node == null)
return;
System.out.print(node.key + " ");
PreOrderTraversal(node.left);
PreOrderTraversal(node.right);
}
// 中序遍历
public void InOrderTraversal(Node node) {
if (node == null)
return;
InOrderTraversal(node.left);
System.out.print(node.key + " ");
InOrderTraversal(node.right);
}
// 后序遍历
public void PostOrderTraversal(Node node) {
if (node == null)
return;
PostOrderTraversal(node.left);
PostOrderTraversal(node.right);
System.out.print(node.key + " ");
}
// 左旋
public Node LeftRotation(Node x) {
Node y = x.right; //得到y
Node T2 = y.left;
x.right = T2;
y.left = x;
//更新高度
x.height = Math.max(Height(x.left), Height(x.right)) + 1;
y.height = Math.max(Height(y.left), Height(y.right)) + 1;
return y;
}
// 右旋
public Node RighRotation(Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
// 更新高度
y.height = Math.max(Height(y.left), Height(y.right)) + 1;
x.height = Math.max(Height(x.left), Height(x.right)) + 1;
return x;
}
// 插入
public void Insert(int x) {
root = Insert(root, x);
}
public Node Insert(Node node, int k) {
if (node == null) {
node = new Node(k);
return node;
}
if (node.key > k) {
node.left = Insert(node.left, k); //递归插入左子树
} else if (node.key < k) {
node.right = Insert(node.right, k); //递归插入右子树
} else //如果相等说明这个值已经存在
return node;
//更新高度
node.height = 1 + Math.max(Height(node.left), Height(node.right));
//更新平衡因子
int balance = Balance(node);
/*
* 情况 1：LL
*/
// 如果情况为LL，进行右旋转
if (balance > 1 && k < node.left.key) {
return RighRotation(node);
}
/*
* 情况 2：RR
*/
// 如果情况为RR，进行右旋转
if (balance < -1 && k > node.right.key) {
return LeftRotation(node);
}
/*
* 情况 3：LR
*/
// 如果情况为LR，先进行左旋转再右旋转
if (balance > 1 && k > node.left.key) {
node.left = LeftRotation(node.left);
return RighRotation(node);
}
/*
* 情况 4：RL
*/
// 如果情况为RL, 先进行右旋转再左旋转
if (balance < -1 && k < node.right.key) {
node.right = RighRotation(node.right);
return LeftRotation(node);
}
return node;
}
//删除
public void Delete(int key) {
root = deleteNode(root, key);
}
private Node deleteNode(Node node, int key) {
if (node == null)
return null;
// 如果key小于节点的key，继续处理左子树
if (node.key > key) {
node.left = deleteNode(node.left, key);
// 检查平衡
return checkBalance(node);
}
// 如果key大于节点的key，继续处理右子树
else if (node.key < key) {
node.right = deleteNode(node.right, key);
// 检查平衡
return checkBalance(node);
}
// 如果key等于节点的key，即找到要删除的节点
else {
if (node.left == null)
return node.right;
else if (node.right == null)
return node.left;
else {
if (Height(node.left) > Height(node.right)) {
// 如果node的左子树比右子树矮，就找到node的左子树中的最大值
int min = maxNodeValue(node.left); // 找到node的左子树中的最大值
node.key = min; // 用node的左子树中的最大值替换node的key
node.left = deleteNode(node.left,min); // 删除node的左子树中的最大值
} else {
// 如果node的左子树比右子树高，就找到node的右子树中的最小值
int max = minNode
Public @ 2023-02-24 05:48:02 整理自网络ChatGPT产生之内容，文本内容不具备参考意义，程序内容有且仅有借鉴意义。
