整合查找
整理自網絡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產生之內容，文本內容不具備參考意義，程序內容有且僅有借鑒意義。
