|
一、什么是AVL树：二、AVL树有哪些操作：三、代码实现：
一、什么是AVL树：
在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是{\displaystyle O(\log {n})}O(\log{n})。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。 节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
二、AVL树有哪些操作：
AVL树的基本操作一般涉及运作同在不平衡的二叉查找树所运作的同样的算法。但是要进行预先或随后做一次或多次所谓的"AVL旋转"。 以下图表以四列表示四种情况，每行表示在该种情况下要进行的操作。在左左和右右的情况下，只需要进行一次旋转操作；在左右和右左的情况下，需要进行两次旋转操作。 
三、代码实现：
//二叉树类
class AVlTree {
private Node root;
//添加
public void add(Node node) {
if (root == null) root = node;
else root.add(node);
}
//中序遍历
public void infix() {
if (root == null) throw new RuntimeException("空树");
root.infix();
}
//删除节点
public void delNode(int value) {
if (root == null) throw new RuntimeException("空树");
//查找删除的节点--->返回为空，不存在 --->
//如果该树只有一个节点，将根节点至于空
Node node = root.search(value);
if (node == null) throw new RuntimeException("该节点不存在");
if (root.getLeft() == null && root.getRight() == null) {
root = null;
return;
}
Node parent = root.searchParent(value);
//1、如果该节点是叶子节点-->查找到他的父节点，查看他是父节点的左节点还是右节点，删除
if (node.getRight() == null && node.getLeft() == null) {
if (parent.getRight().getValue() == value) parent.setRight(null);
else parent.setLeft(null);
} else if (node.getRight() != null && node.getLeft() != null) {
//有两个子节点的节点-->找到该节点右子树的最小值进行替换
//找到该节点左子树的最大值进行替换
int parentMin = delParentMin(node.getRight());
node.setValue(parentMin);
} else {
//如果是根节点
if (parent == null) {
if (node.getRight() != null) {
node.setValue(node.getRight().getValue());
node.setRight(null);
} else {
node.setValue(node.getLeft().getValue());
node.setLeft(null);
}
return;
}
if (node.getLeft() != null) {//该节点有左子节点是父节点的左子节点
if (parent.getLeft().getValue() == value) parent.setLeft(node.getLeft());
else parent.setRight(node.getLeft());
} else {
if (parent.getRight().getValue() == value) parent.setRight(node.getRight());
else parent.setLeft(node.getRight());//该节点是父节点的左子节点
}
}
}
/**
* 查找该节点右子树的最小值
* 应该由父节点的右子节点调用
*
* @param node
* @return
*/
private int delParentMin(Node node) {
Node temp = node;
while (temp.getLeft() != null) temp = temp.getLeft();
delNode(temp.getValue());
return temp.getValue();
}
public Node getRoot() {
return root;
}
}
//节点类
class Node {
private int value;
private Node left;
private Node right;
public Node(int value) {
this.value = value;
}
//查找当前节点的父节点
public Node searchParent(int value) {
if ((this.getLeft() != null && this.getLeft().getValue() == value) || (this.getRight() != null && this.getRight().getValue() == value)) {
return this;
} else {
if (this.getValue() > value) {
if (this.getLeft() != null) return this.getLeft().searchParent(value);
} else {
if (this.getRight() == null) return null;
else return this.getRight().searchParent(value);
}
return null;
}
}
//查找当前节点
public Node search(int value) {
if (this.value == value) return this;
if (this.value > value) {
if (this.left != null) return this.left.search(value);
else return null;
} else {
if (this.right != null) return this.right.search(value);
else return null;
}
}
//添加
public void add(Node node) {
if (node == null) return;
if (this.value > node.value) {
if (this.left == null) this.setLeft(node);
else this.left.add(node);
} else {
if (this.right == null) this.setRight(node);
else this.right.add(node);
}
if (rightHight() - leftHight() > 1) {
if (right != null && this.getRight().leftHight() > this.getRight().rightHight()) {
rightRotate();
}
leftRotate();
return;//必须加
}
if (leftHight() - rightHight() > 1) {//右旋转
//当符合右旋转的条件时如果当前节点的左子树的右子树大于他的左子树的高度
//先进性左旋转
if (left != null && this.left.rightHight() > this.left.leftHight()) {
this.left.leftRotate();
}
rightRotate();
}
}
//左旋转
public void leftRotate() {
Node newNode = new Node(this.getValue());
newNode.setLeft(this.getLeft());
newNode.setRight(this.getRight().getLeft());
this.setValue(this.getRight().getValue());
this.setRight(this.getRight().getRight());
this.setLeft(newNode);
}
//右旋转
public void rightRotate() {
Node newNode = new Node(this.getValue());
newNode.setRight(this.getRight());
newNode.setLeft(this.getLeft().getRight());
this.setValue(this.getLeft().getValue());
this.setLeft(this.getLeft().getLeft());
this.setRight(newNode);
}
//中序遍历
public void infix() {
if (this.left != null) this.left.infix();
System.out.println(this);
if (this.right != null) this.right.infix();
}
//求数的高度
public int hight() {
return Math.max(this.right == null ? 0 : this.right.hight(), this.left == null ? 0 : this.left.hight()) + 1;
}
//右子树的高度
public int rightHight() {
if (this.getRight() == null) return 0;
else return this.right.hight();
}
//左子树
public int leftHight() {
if (this.getLeft() == null) return 0;
else return this.left.hight();
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
@Override
public String toString() {
return new StringJoiner(", ", Node.class.getSimpleName() + "[", "]")
.add("value=" + value)
.toString();
}
}
|