整合查找
) */ 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; } } // 根節(jié)點 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(tǒng) 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 //如果相等說明這個值已經(jīng)存在 return node; //更新高度 node.height = 1 + Math.max(Height(node.left), Height(node.right)); //更新平衡因子 int balance = Balance(node); /* * 情況 1：LL */ // 如果情況為LL，進行右旋轉(zhuǎn) if (balance > 1 && k < node.left.key) { return RighRotation(node); } /* * 情況 2：RR */ // 如果情況為RR，進行右旋轉(zhuǎn) if (balance < -1 && k > node.right.key) { return LeftRotation(node); } /* * 情況 3：LR */ // 如果情況為LR，先進行左旋轉(zhuǎn)再右旋轉(zhuǎn) if (balance > 1 && k > node.left.key) { node.left = LeftRotation(node.left); return RighRotation(node); } /* * 情況 4：RL */ // 如果情況為RL, 先進行右旋轉(zhuǎn)再左旋轉(zhuǎn) 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小于節(jié)點的key，繼續(xù)處理左子樹 if (node.key > key) { node.left = deleteNode(node.left, key); // 檢查平衡 return checkBalance(node); } // 如果key大于節(jié)點的key，繼續(xù)處理右子樹 else if (node.key < key) { node.right = deleteNode(node.right, key); // 檢查平衡 return checkBalance(node); } // 如果key等于節(jié)點的key，即找到要刪除的節(jié)點 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
