文章目录
- AVL（平衡二叉树）树
- 性质
- AVL树的操作（Java）
- 节点的创建
- AVL树的插入
- 1.判断平衡
- 2.保持树的平衡
- 3.判断是否AVL树
- 4.删除节点
- 全部代码
AVL（平衡二叉树）树
平衡二叉树是一种特殊的二叉搜索树，他的左子树与右子树的高度差不超过1。并且左右两个子树都是一颗平衡二叉树。保持平衡的特性使得平衡二叉树的查询、插入和删除操作在平均和最坏情况下的时间复杂度都是
O(logn)，其中n是树中节点的数量。 相比于普通的二叉搜索树，平衡二叉树更加适合处理动态变化的数据集。 常见的平衡二叉树有AVL树、红黑树以及B树等。这些树结构通过在插入或删除节点时进行特定的平衡操作来保持树的平衡。
性质
- 它的左右子树都是AVL树
- 左右子树高度差不超过1
- 完全二叉树是AVL树，如果一棵树是AVL树，那么其高度可保持在
O(log2n)，搜索时间复杂度为O(log2n)
AVL树的操作（Java）
首先创建节点用来保存树中的节点的数据，其次和二叉搜索树不同的是，AVL树需要平衡因子来控制二叉树的平衡。
节点的创建
private class Node {
int val;
Node left;
Node right;
int height;
public Node(int val) {
this.val = val;
this.left = this.right = null;
this.height = 1;
}
}
AVL树的插入
插入操作和二叉搜索树是相同的，但是在插入结束时会判断AVL树是否平衡。
// 向树中添加节点
public void add(int val) {
if (contains(val)) {
return;
}
this.root = add(this.root, val);
this.size++;
}
// 向AVL树中添加节点
private Node add(Node node, int val) {
// 递归到底的情况
if (node == null) {
return new Node(val);
}
if (node.val > val) {
node.left = add(node.left, val);
} else {
node.right = add(node.right, val);
}
// 更新节点高度
node.height = Math.max(getNodeHeight(node.left), getNodeHeight(node.right)) + 1;
// 维护平衡
int balance = getBalance(node);
if (balance > 1 && getBalance(node.left) >= 0) {
// 右旋
return rightRotate(node);
} else if (balance > 1 && getBalance(node.left) <= 0) {
// 左旋右旋
node.left = leftRotate(node.left);
return rightRotate(node);
} else if (balance < -1 && getBalance(node.right) >= 0) {
// 右旋左旋
node.right = rightRotate(node.right);
return leftRotate(node);
} else if (balance < -1 && getBalance(node.right) <= 0) {
// 左旋
return leftRotate(node);
}
return node;
}
1.判断平衡
一个二叉树是否是平衡的，根绝二叉树的性质可以知道，当其左右子树节点的高度差的绝对值不超过1时，这个二叉树就是平衡二叉树，当其高度差绝对值超过1时，那么就是不平衡的二叉树，就需要对二叉树进行平衡调整。
// 获取当前节点的平衡因子（左右子树高度差）
private int getBalance(Node node) {
if (node == null) {
return 0;
}
return getNodeHeight(node.left) - getNodeHeight(node.right);
}
2.保持树的平衡
当判断出一棵树不平衡时，需要进行平衡调整。
二叉树一般出现不平衡的时候有四种状态：
1. 左旋
根据上图，我们可以直到，当二叉树的右树的高度超过平衡时需要进行左旋，左旋的方式是先将x节点的左子树单独定义出来为t2，然后将y节点连接到x的左子树，将t2连接到y的右子树上，这时就完成了左旋。
// 左旋转
private Node leftRotate(Node y) {
Node x = y.right;
Node leftX = x.left;
x.left = y;
y.right = leftX;
y.height = 1 + Math.max(getNodeHeight(y.left), getNodeHeight(y.right));
x.height = 1 + Math.max(getNodeHeight(x.left), getNodeHeight(x.right));
return x;
}
2. 右旋
右旋转和左旋转类似，右旋的方式是先将x节点的右子树单独定义出来为t2，然后将y节点连接到x的右子树，将t2连接到y的左子树上，这时就完成了右旋。
// 右旋转
private Node rightRotate(Node y) {
Node x = y.left;
Node rightX = x.right;
x.right = y;
y.left = rightX;
y.height = 1 + Math.max(getNodeHeight(y.left), getNodeHeight(y.right));
x.height = 1 + Math.max(getNodeHeight(x.left), getNodeHeight(x.right));
return x;
}
3. 右旋+左旋
所谓右旋+左旋就是将右旋和左旋进行连接，将这类不平衡的树进行平衡
4. 左旋+右旋
3.判断是否AVL树
判断是否AVL树就是判断二叉树的各个节点的平衡因子是否都是小于等于1或者大于等于-1。
// 判断是否为平衡二叉树
public boolean isBalanceTree() {
return isBalanceTree(this.root);
}
private boolean isBalanceTree(Node node) {
if (node == null) {
return true;
}
if (Math.abs(getBalance(node)) > 1) {
return false;
}
return isBalanceTree(node.left) && isBalanceTree(node.right);
}
// 获取当前节点的平衡因子（左右子树高度差）
private int getBalance(Node node) {
if (node == null) {
return 0;
}
return getNodeHeight(node.left) - getNodeHeight(node.right);
}
4.删除节点
// 删除任意节点
public void remove(int val) {
boolean isExist = contains(val);
if (isExist) {
this.root = remove(this.root, val);
}
}
// 从以node为根的二分搜索树中删除值为val的结点
private Node remove(Node node, int val) {
Node resultNode = null;
if (node.val == val) {
// 叶子节点
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
this.size--;
resultNode = rightNode;
} else if (node.right == null) {
Node leftNode = node.left;
node.left = null;
this.size--;
resultNode = leftNode;
} else {
// 找出删除节点的后继
Node nextNode = getMinNode(node.right);
// 从右树中删除最小节点
nextNode.right = removeMinNode(node.right);
// 开始连接
nextNode.left = node.left;
// 让node失去关联关系
node.left = node.right = null;
resultNode = nextNode;
}
} else if (node.val > val) {
node.left = remove(node.left, val);
resultNode = node;
} else {
node.right = remove(node.right, val);
resultNode = node;
}
// 删除的是叶子节点
if (resultNode == null) {
return null;
}
// 删除之后，可能改变了树的平衡，因此需要进行调整
resultNode.height = Math.max(getNodeHeight(resultNode.left), getNodeHeight(resultNode.right)) + 1;
Node result = resultNode;
if (getBalance(resultNode) > 1 && getBalance(resultNode.left) >= 0) {
result = rightRotate(resultNode);
} else if (getBalance(resultNode) < -1 && getBalance(resultNode.right) <= 0) {
result = leftRotate(resultNode);
} else if (getBalance(resultNode) > 1 && getBalance(resultNode.left) < 0) {
resultNode.left = leftRotate(resultNode.left);
result = rightRotate(resultNode);
} else if (getBalance(resultNode) < -1 && getBalance(resultNode.right) > 0) {
resultNode.right = rightRotate(resultNode.right);
result = leftRotate(resultNode);
}
return result;
}
全部代码
import java.util.*;
public class AVLTree {
private Node root;
private int size;
public AVLTree() {
this.root = null;
this.size = 0;
}
// 判断是否为空
public boolean isEmpty() {
return this.size == 0;
}
// 获取树中节点个数
public int getSize() {
return this.size;
}
// 获取节点高度
public int getNodeHeight(Node node) {
if (node == null) {
return 0;
}
return node.height;
}
// 获取当前节点的平衡因子（左右子树高度差）
private int getBalance(Node node) {
if (node == null) {
return 0;
}
return getNodeHeight(node.left) - getNodeHeight(node.right);
}
// 查找最小节点
public Node getMinNode() {
if (this.root == null) {
return null;
}
return getMinNode(this.root);
}
private Node getMinNode(Node node) {
if (node.left == null) {
return node;
}
return getMinNode(node.left);
}
// 判断是否重复
public boolean contains(int val) {
return contains(this.root, val);
}
private boolean contains(Node node, int val) {
if (node == null) {
return false;
}
if (node.val == val) {
return true;
} else if (node.val > val) {
return contains(node.left, val);
} else {
return contains(node.right, val);
}
}
// 向树中添加节点
public void add(int val) {
if (contains(val)) {
return;
}
this.root = add(this.root, val);
this.size++;
}
// 向AVL树中添加节点
private Node add(Node node, int val) {
// 递归到底的情况
if (node == null) {
return new Node(val);
}
if (node.val > val) {
node.left = add(node.left, val);
} else {
node.right = add(node.right, val);
}
// 更新节点高度
node.height = Math.max(getNodeHeight(node.left), getNodeHeight(node.right)) + 1;
// 维护平衡
int balance = getBalance(node);
if (balance > 1 && getBalance(node.left) >= 0) {
// 右旋
return rightRotate(node);
} else if (balance > 1 && getBalance(node.left) <= 0) {
// 左旋右旋
node.left = leftRotate(node.left);
return rightRotate(node);
} else if (balance < -1 && getBalance(node.right) >= 0) {
// 右旋左旋
node.right = rightRotate(node.right);
return leftRotate(node);
} else if (balance < -1 && getBalance(node.right) <= 0) {
// 左旋
return leftRotate(node);
}
return node;
}
// 从二分搜索树中删除最小节点
public Node removeMinNode() {
if (this.root == null) {
return null;
}
Node result = getMinNode();
if (result != null) {
this.root = removeMinNode(this.root);
this.size--;
}
return result;
}
private Node removeMinNode(Node node) {
if (node.left == null) {
return node.right;
}
node.left = removeMinNode(node.left);
return node;
}
// 删除任意节点
public void remove(int val) {
boolean isExist = contains(val);
if (isExist) {
this.root = remove(this.root, val);
}
}
// 从以node为根的二分搜索树中删除值为val的结点
private Node remove(Node node, int val) {
Node resultNode = null;
if (node.val == val) {
// 叶子节点
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
this.size--;
resultNode = rightNode;
} else if (node.right == null) {
Node leftNode = node.left;
node.left = null;
this.size--;
resultNode = leftNode;
} else {
// 找出删除节点的后继
Node nextNode = getMinNode(node.right);
// 从右树中删除最小节点
nextNode.right = removeMinNode(node.right);
// 开始连接
nextNode.left = node.left;
// 让node失去关联关系
node.left = node.right = null;
resultNode = nextNode;
}
} else if (node.val > val) {
node.left = remove(node.left, val);
resultNode = node;
} else {
node.right = remove(node.right, val);
resultNode = node;
}
// 删除的是叶子节点
if (resultNode == null) {
return null;
}
// 删除之后，可能改变了树的平衡，因此需要进行调整
resultNode.height = Math.max(getNodeHeight(resultNode.left), getNodeHeight(resultNode.right)) + 1;
Node result = resultNode;
if (getBalance(resultNode) > 1 && getBalance(resultNode.left) >= 0) {
result = rightRotate(resultNode);
} else if (getBalance(resultNode) < -1 && getBalance(resultNode.right) <= 0) {
result = leftRotate(resultNode);
} else if (getBalance(resultNode) > 1 && getBalance(resultNode.left) < 0) {
resultNode.left = leftRotate(resultNode.left);
result = rightRotate(resultNode);
} else if (getBalance(resultNode) < -1 && getBalance(resultNode.right) > 0) {
resultNode.right = rightRotate(resultNode.right);
result = leftRotate(resultNode);
}
return result;
}
// 中序遍历
public List<Integer> middleTravel() {
List<Integer> list = new ArrayList<>();
middleTravel(this.root, list);
return list;
}
private void middleTravel(Node node, List<Integer> list) {
if (node == null) {
return;
}
middleTravel(node.left, list);
list.add(node.val);
middleTravel(node.right, list);
}
// 层序遍历
private List<Node> levelTravel() {
List<Node> list = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
if (this.root == null) {
return list;
}
queue.offer(this.root);
while (!queue.isEmpty()) {
Node node = queue.poll();
list.add(node);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return list;
}
// 判断是否是二分搜索树
public boolean isBinearySearchTree() {
List<Integer> list = middleTravel();
for (int i = 1; i < list.size(); i++) {
if (list.get(i - 1) > list.get(i)) {
return false;
}
}
return true;
}
// 判断是否为平衡二叉树
public boolean isBalanceTree() {
return isBalanceTree(this.root);
}
private boolean isBalanceTree(Node node) {
if (node == null) {
return true;
}
if (Math.abs(getBalance(node)) > 1) {
return false;
}
return isBalanceTree(node.left) && isBalanceTree(node.right);
}
// 右旋转
private Node rightRotate(Node y) {
Node x = y.left;
Node rightX = x.right;
x.right = y;
y.left = rightX;
y.height = 1 + Math.max(getNodeHeight(y.left), getNodeHeight(y.right));
x.height = 1 + Math.max(getNodeHeight(x.left), getNodeHeight(x.right));
return x;
}
// 左旋转
private Node leftRotate(Node y) {
Node x = y.right;
Node leftX = x.left;
x.left = y;
y.right = leftX;
y.height = 1 + Math.max(getNodeHeight(y.left), getNodeHeight(y.right));
x.height = 1 + Math.max(getNodeHeight(x.left), getNodeHeight(x.right));
return x;
}
public String show() {
// 按层遍历树
List<Node> list = levelTravel();
String s = "";
for (int i = 0; i < list.size(); i++) {
s += "size = " + list.get(i).val + ", height = " + list.get(i).height + ", balance = " + getBalance(list.get(i)) + ";\n";
}
return s;
}
@Override
public String toString() {
// 按层遍历树
List<Node> list = levelTravel();
String s = "["+list.get(0).val;
for (int i = 1; i < list.size(); i++) {
s += "," + list.get(i).val;
}
s += "]";
return s;
}
private class Node {
int val;
Node left;
Node right;
int height;
public Node(int val) {
this.val = val;
this.left = this.right = null;
this.height = 1;
}
}
public static void main(String[] args) {
AVLTree avlTree = new AVLTree();
Random random = new Random();
for (int i = 0; i < 10; i++) {
avlTree.add(i);
avlTree.add(random.nextInt(100));
}
System.out.println(avlTree.toString());
// 判断是否为平衡二叉树
System.out.println(avlTree.isBalanceTree());
avlTree.removeMinNode();
System.out.println(avlTree.toString());
avlTree.remove(9);
System.out.println(avlTree.toString());
}
}
