AVL树的Java实现
时间: 2023-04-04 19:02:40 浏览: 96
AVL树是一种自平衡二叉搜索树,它可以保证在插入或删除节点时,树的高度始终保持在 O(log n) 的级别。在Java中,可以使用Node类来实现AVL树,其中包含节点的值、左右子节点和平衡因子等信息。在插入或删除节点时,需要对树进行旋转操作,以保持平衡。具体实现可以参考Java标准库中的TreeMap类。
相关问题
用Java写程序:实现用AVL树存储身份信息类,同时AVL树的值是字符串身份证号码
好的,下面是用Java实现AVL树存储身份信息类的示例代码:
```java
public class IdentityInfo {
private String name;
private String idNumber;
public IdentityInfo(String name, String idNumber) {
this.name = name;
this.idNumber = idNumber;
}
public String getName() {
return name;
}
public String getIdNumber() {
return idNumber;
}
}
public class AVLTreeNode {
private IdentityInfo identityInfo;
private AVLTreeNode left;
private AVLTreeNode right;
private int height;
public AVLTreeNode(IdentityInfo identityInfo) {
this.identityInfo = identityInfo;
this.left = null;
this.right = null;
this.height = 1;
}
public IdentityInfo getIdentityInfo() {
return identityInfo;
}
public AVLTreeNode getLeft() {
return left;
}
public void setLeft(AVLTreeNode left) {
this.left = left;
}
public AVLTreeNode getRight() {
return right;
}
public void setRight(AVLTreeNode right) {
this.right = right;
}
public int getHeight() {
return height;
}
public void setHeight(int height) {
this.height = height;
}
}
public class AVLTree {
private AVLTreeNode root;
public AVLTree() {
this.root = null;
}
private int getHeight(AVLTreeNode node) {
if (node == null) {
return 0;
}
return node.getHeight();
}
private int getBalanceFactor(AVLTreeNode node) {
if (node == null) {
return 0;
}
return getHeight(node.getLeft()) - getHeight(node.getRight());
}
private AVLTreeNode rotateLeft(AVLTreeNode node) {
AVLTreeNode rightNode = node.getRight();
AVLTreeNode leftRightNode = rightNode.getLeft();
rightNode.setLeft(node);
node.setRight(leftRightNode);
node.setHeight(Math.max(getHeight(node.getLeft()), getHeight(node.getRight())) + 1);
rightNode.setHeight(Math.max(getHeight(rightNode.getLeft()), getHeight(rightNode.getRight())) + 1);
return rightNode;
}
private AVLTreeNode rotateRight(AVLTreeNode node) {
AVLTreeNode leftNode = node.getLeft();
AVLTreeNode rightLeftNode = leftNode.getRight();
leftNode.setRight(node);
node.setLeft(rightLeftNode);
node.setHeight(Math.max(getHeight(node.getLeft()), getHeight(node.getRight())) + 1);
leftNode.setHeight(Math.max(getHeight(leftNode.getLeft()), getHeight(leftNode.getRight())) + 1);
return leftNode;
}
public void insert(IdentityInfo identityInfo) {
this.root = insert(this.root, identityInfo);
}
private AVLTreeNode insert(AVLTreeNode node, IdentityInfo identityInfo) {
if (node == null) {
return new AVLTreeNode(identityInfo);
}
if (identityInfo.getIdNumber().compareTo(node.getIdentityInfo().getIdNumber()) < 0) {
node.setLeft(insert(node.getLeft(), identityInfo));
} else if (identityInfo.getIdNumber().compareTo(node.getIdentityInfo().getIdNumber()) > 0) {
node.setRight(insert(node.getRight(), identityInfo));
} else {
return node;
}
node.setHeight(Math.max(getHeight(node.getLeft()), getHeight(node.getRight())) + 1);
int balanceFactor = getBalanceFactor(node);
if (balanceFactor > 1 && identityInfo.getIdNumber().compareTo(node.getLeft().getIdentityInfo().getIdNumber()) < 0) {
return rotateRight(node);
}
if (balanceFactor < -1 && identityInfo.getIdNumber().compareTo(node.getRight().getIdentityInfo().getIdNumber()) > 0) {
return rotateLeft(node);
}
if (balanceFactor > 1 && identityInfo.getIdNumber().compareTo(node.getLeft().getIdentityInfo().getIdNumber()) > 0) {
node.setLeft(rotateLeft(node.getLeft()));
return rotateRight(node);
}
if (balanceFactor < -1 && identityInfo.getIdNumber().compareTo(node.getRight().getIdentityInfo().getIdNumber()) < 0) {
node.setRight(rotateRight(node.getRight()));
return rotateLeft(node);
}
return node;
}
public IdentityInfo search(String idNumber) {
AVLTreeNode node = search(this.root, idNumber);
if (node == null) {
return null;
}
return node.getIdentityInfo();
}
private AVLTreeNode search(AVLTreeNode node, String idNumber) {
if (node == null || node.getIdentityInfo().getIdNumber().equals(idNumber)) {
return node;
}
if (idNumber.compareTo(node.getIdentityInfo().getIdNumber()) < 0) {
return search(node.getLeft(), idNumber);
} else {
return search(node.getRight(), idNumber);
}
}
}
```
在这个示例代码中,`IdentityInfo`类表示身份信息,包含`name`和`idNumber`字段。`AVLTreeNode`类表示AVL树中的节点,包含`identityInfo`、`left`、`right`和`height`字段。`AVLTree`类表示AVL树,包含`root`字段和`insert()`、`search()`等方法来操作AVL树。在`insert()`方法中,我们使用字符串身份证号码来比较节点大小,从而将新的身份信息插入到AVL树中。在`search()`方法中,我们也使用字符串身份证号码来搜索身份信息。
平衡二叉树 java实现
平衡二叉树的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
}
}
```