平衡二叉树 java实现
时间: 2024-02-10 09:08:43 浏览: 25
平衡二叉树的Java实现可以通过定义一个`TreeNode`类来表示树的节点,并在该类中实现插入、删除和查找等操作。下面是一个简单的平衡二叉树的Java实现示例:
```java
class TreeNode {
int val;
int height;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
1;
}
}
class AVLTree {
private TreeNode root;
private int getHeight(TreeNode node) if (node == null) {
return 0;
}
return node.height;
}
private int getBalanceFactor(TreeNode node) {
if (node == null) {
return 0;
}
return getHeight(node.left) - getHeight(node.right);
}
private TreeNode rotateLeft(TreeNode node) {
TreeNode newRoot = node.right;
node.right = newRoot.left;
newRoot.left = node;
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1;
return newRoot;
}
private TreeNode rotateRight(TreeNode node) {
TreeNode newRoot = node.left;
node.left = newRoot.right; newRoot.right = node;
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1;
return newRoot;
}
public void insert(int val) {
root = insertNode(root, val);
}
private TreeNode insertNode(TreeNode node, int val) {
if (node == null) {
return new TreeNode(val);
}
if (val < node.val) {
node.left = insertNode(node.left, val);
} else if (val > node.val) {
node.right = insertNode(node.right, val);
} else {
return node;
}
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
int balanceFactor = getBalanceFactor(node);
if (balanceFactor > 1 && val < node.left.val) {
return rotateRight(node);
}
if (balanceFactor < -1 && val > node.right.val) {
return rotateLeft(node);
}
if (balanceFactor > 1 && val > node.left.val) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
if (balanceFactor < -1 && val < node.right.val) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}
public void delete(int val) {
root = deleteNode(root, val);
}
private TreeNode deleteNode(TreeNode node, int val) {
if (node == null) {
return null;
}
if (val < node.val) {
node.left = deleteNode(node.left, val);
} else if (val > node.val) {
node.right = deleteNode(node.right, val);
} else {
if (node.left == null || node.right == null) {
node = (node.left != null) ? node.left : node.right;
} else {
TreeNode minNode = findMinNode(node.right);
node.val = minNode.val;
node.right = deleteNode(node.right, minNode.val);
}
}
if (node == null) {
return null;
}
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
int balanceFactor = getBalanceFactor(node);
if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
return rotateRight(node);
}
if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
return rotateLeft(node);
}
if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}
private TreeNode findMinNode(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}
public boolean search(int val) {
return searchNode(root, val);
}
private boolean searchNode(TreeNode node, int val) {
if (node == null) {
return false;
}
if (val < node.val) {
return searchNode(node.left, val);
} else if (val > node.val) {
return searchNode(node.right, val);
} else {
return true;
}
}
}
```
使用示例:
```java
public class Main {
public static void main(String[] args) {
AVLTree tree = new AVLTree();
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(40);
tree.insert(50);
tree.insert(25);
System.out.println("Search 30: " + tree.search(30)); // 输出:true
System.out.println("Search 35: " + tree.search(35)); // 输出:false
tree.delete(30);
System.out.println("Search 30: " + tree.search(30)); // 输出:false
}
}
```