整合查找
) */ 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