本文是介绍AVL树及其插入操作。
1 AVL简介
AVL树是一种特殊的BST树，特殊的地方在于，左右子树高度的绝对值不超过一，所以在构建AVL树的时候，需要调整，以保证平衡。AVL树的作用与BST树是一样的，主要用于快速查找。
2 树的结构
class Tree<T extends Comparable<T>> {
private static final int MAX_HEIGHT_DIFFERENCE = 1;
private Node<T> root;
class Node<KT> {
KT key;
Node<KT> left;
Node<KT> right;
int height = 1;
public Node(KT key, Node<KT> left, Node<KT> right) {
this.key = key;
this.left = left;
this.right = right;
}
}
public Tree(T[] keys) {
if (keys == null || keys.length < 1) {
throw new NullPointerException();
}
root = new Node<>(keys[0], null, null);
for (int i = 1; i < keys.length && keys[i] != null; ++i) {
root = insert(root, keys[i]);
}
}
}首先定义一个常量，代表左右子树高度差的绝对值的最大值。然后定义一个根节点root,定义一个节点的内部类Node,最后是树的初始化操作，传入数组，进行树的构建。
3 节点的查找
public T find(T key) {
if (key == null || root == null) {
return null;
}
return find(root, key, key.compareTo(root.key));
}
private T find(Node<T> node, T key, int cmp) {
if (node == null) {
return null;
}
if (cmp == 0) {
return node.key;
}
return find((node = cmp > 0 ? node.right : node.left), key, node == null ? 0 : key.compareTo(node.key));
}比较简单，这里就不说了。
4 节点的插入
然后插入分为4种情况，也就对应了4种旋转方式。
LL单旋：
首先说一下为啥叫LL单旋，单代表只用旋转一次，LL代表不平衡节点的左子树的左子树上插入节点导致了不平衡。
LL单旋的步骤就是，将不平衡节点的左节点网上提，这样就会导致，不平衡节点的位置下降，于是B的右子树变为A,而A的左子树节点变为原B的右子树节点。
RR单旋：
RR单旋与LL单旋性质是一样的，只不过方向不一样。
LR双旋：
LR代表的是不平衡节点（10）的左子树的右子树上有节点插入导致了不平衡。双旋是指，先RR单旋，然后在LL单旋（如图所示）。
RL双旋：
与LR双旋相反。这里就不细说了。
代码：
public void insert(T key) {
if (key == null) {
throw new NullPointerException();
}
root = insert(root,key);
}
private Node<T> insert(Node<T> node, T key) {
if (node == null) {
return new Node<>(key, null, null);
}
int cmp = key.compareTo(node.key);
if (cmp == 0) {
return node;
}
if (cmp < 0) {
node.left = insert(node.left, key);
} else {
node.right = insert(node.right, key);
}
if (Math.abs(height(node.left) - height(node.right)) > MAX_HEIGHT_DIFFERENCE) {
node = balance(node);
}
refreshHeight(node);
return node;
}
private int height(Node<T> node) {
if (node == null) {
return 0;
}
return node.height;
}
private void refreshHeight(Node<T> node) {
node.height = Math.max(height(node.left), height(node.right)) + 1;
}
private Node<T> balance(Node<T> node) {
Node<T> node1, node2;
if (height(node.left) > height(node.right) && height(node.left.left) >= height(node.left.right)) {
node1 = node.left;
node.left = node1.right;
node1.right = node;
refreshHeight(node);
return node1;
}
if (height(node.left) > height(node.right) && height(node.left.left) < height(node.left.right)) {
node1 = node.left;
node2 = node.left.right;
node.left = node2.right;
node1.right = node2.left;
node2.left = node1;
node2.right = node;
refreshHeight(node);
refreshHeight(node1);
return node2;
}
if (height(node.right) > height(node.left) && height(node.right.right) >= height(node.right.left)) {
node1 = node.right;
node.right = node1.left;
node1.left = node;
refreshHeight(node);
return node1;
}
if (height(node.right) > height(node.left) && height(node.right.right) < height(node.right.left)) {
node1 = node.right;
node2 = node.right.left;
node.right = node2.left;
node1.left = node2.right;
node2.right = node1;
node2.left = node;
refreshHeight(node);
refreshHeight(node1);
return node2;
}
return node;
}5 节点的删除
节点的删除，我的老师告诉我们，因为AVL主要用于快速查找，插入和查找操作比较多，删除操作比较少，所以采用懒惰删除的方式，如果删除操作较多，就可以换一种数据结构。
懒惰删除：
也就是对每个节点添加一个标记，删除时标记一下，表示删除。这样需要对插入和查找操作进行一些适当的修改。
6 全部代码
class Tree<T extends Comparable<T>> {
private static final int MAX_HEIGHT_DIFFERENCE = 1;
private Node<T> root;
class Node<KT> {
KT key;
Node<KT> left;
Node<KT> right;
int height = 1;
public Node(KT key, Node<KT> left, Node<KT> right) {
this.key = key;
this.left = left;
this.right = right;
}
}
public Tree(T[] keys) {
if (keys == null || keys.length < 1) {
throw new NullPointerException();
}
root = new Node<>(keys[0], null, null);
for (int i = 1; i < keys.length && keys[i] != null; ++i) {
root = insert(root, keys[i]);
}
}
public T find(T key) {
if (key == null || root == null) {
return null;
}
return find(root, key, key.compareTo(root.key));
}
private T find(Node<T> node, T key, int cmp) {
if (node == null) {
return null;
}
if (cmp == 0) {
return node.key;
}
return find((node = cmp > 0 ? node.right : node.left), key, node == null ? 0 : key.compareTo(node.key));
}
public void insert(T key) {
if (key == null) {
throw new NullPointerException();
}
root = insert(root,key);
}
private Node<T> insert(Node<T> node, T key) {
if (node == null) {
return new Node<>(key, null, null);
}
int cmp = key.compareTo(node.key);
if (cmp == 0) {
return node;
}
if (cmp < 0) {
node.left = insert(node.left, key);
} else {
node.right = insert(node.right, key);
}
if (Math.abs(height(node.left) - height(node.right)) > MAX_HEIGHT_DIFFERENCE) {
node = balance(node);
}
refreshHeight(node);
return node;
}
private int height(Node<T> node) {
if (node == null) {
return 0;
}
return node.height;
}
private void refreshHeight(Node<T> node) {
node.height = Math.max(height(node.left), height(node.right)) + 1;
}
private Node<T> balance(Node<T> node) {
Node<T> node1, node2;
if (height(node.left) > height(node.right) && height(node.left.left) >= height(node.left.right)) {
node1 = node.left;
node.left = node1.right;
node1.right = node;
refreshHeight(node);
return node1;
}
if (height(node.left) > height(node.right) && height(node.left.left) < height(node.left.right)) {
node1 = node.left;
node2 = node.left.right;
node.left = node2.right;
node1.right = node2.left;
node2.left = node1;
node2.right = node;
refreshHeight(node);
refreshHeight(node1);
return node2;
}
if (height(node.right) > height(node.left) && height(node.right.right) >= height(node.right.left)) {
node1 = node.right;
node.right = node1.left;
node1.left = node;
refreshHeight(node);
return node1;
}
if (height(node.right) > height(node.left) && height(node.right.right) < height(node.right.left)) {
node1 = node.right;
node2 = node.right.left;
node.right = node2.left;
node1.left = node2.right;
node2.right = node1;
node2.left = node;
refreshHeight(node);
refreshHeight(node1);
return node2;
}
return node;
}
public void show1() {
if (root == null) {
System.out.println("是一颗空树");
}
show2(root);
}
private void show2(Node<T> node) {
if(node == null) {
return;
}
System.out.print(node.key + " ");
show2(node.left);
show2(node.right);
}
}
public class test2 {
public static void main(String[] args) {
Integer[] data = {3,2,1,4,5,6,7,10,9,8};
Tree<Integer> t = new Tree<>(data);
t.show1();
}
}到这里这篇文章就结束了。如果有错误，可以在下方评论，或者私聊我😉，我会及时改正的。
如果看了有收获，可以点赞加关注😉，看计算机小白的成长之路。
