即:每个结点的左子树和右子树的高度最多差 1 的 二叉查找树。
1️⃣ key:关键字的值 2️⃣ value:关键字的存储信息 3️⃣ height:树的高度(只有一个结点的树的高度为 1) 4️⃣ left:左子树根结点的的引用 5️⃣ right:右子树根结点的引用
复制代码JAVAclass AVLNode<K extends Comparable<K>, V> { public K key; public V value; public int height; public AVLNode<K, V> left; public AVLNode<K, V> right; public AVLNode(K key, V value, int height) { this.key = key; this.value = value; this.height = height;
}
}
同二叉查找树的查找算法:【数据结构与算法】手撕二叉查找树
AVL 树是一种二叉查找树,故可以使用二叉查找树的插入方法插入结点,但插入一个新结点时,有可能破坏 AVL 树的平衡性。
如果发生这种情况,就需要在插入结点后对平衡树进行调整,恢复平衡的性质。实现这种调整的操作称为“旋转”。
在插入一个新结点 X 后,应调整失去平衡的最小子树,即从插入点到根的路径向上找第一个不平衡结点 A。
平衡因子:该结点的左子树高度和右子树高度的差值。如果差值的绝对值小于等于 1,则说明该结点平衡,如果差值的绝对值为 2(不会出现其他情况),则说明该结点不平衡,需要做平衡处理。
造成结点 A 不平衡的的原因以及调整方式有以下几种情况。
A 结点的平衡因子为 2,说明该结点是最小不平衡结点,需要对 A 结点进行调整。问题发生在 A 结点左子结点的左子结点,所以为 LL 型。
扁担原理:右旋
复制代码12345678JAVA private AVLNode<K, V> rightRotate(AVLNode<K, V> a) { AVLNode<K, V> b = a.left;
a.left = b.right;
b.right = a;
a.height = Math.max(getHeight(a.left), getHeight(a.right)) + ;
b.height = Math.max(getHeight(b.left), getHeight(b.left)) + ; return b;
}
A 结点的平衡因子为 2,说明该结点是最小不平衡结点,需要对 A 结点进行调整。问题发生在 A 结点右子结点的右子结点,所以为 RR 型。
扁担原理:左旋
复制代码12345678JAVA private AVLNode<K, V> leftRotate(AVLNode<K, V> a) { AVLNode<K, V> b = a.right;
a.right = b.left;
b.left = a;
a.height = Math.max(getHeight(a.left), getHeight(a.right)) + ;
b.height = Math.max(getHeight(b.left), getHeight(b.left)) + ; return b;
}
A 结点的平衡因子为 2,说明该结点是最小不平衡结点,需要对 A 结点进行调整。问题发生在 A 结点左子结点的右子结点,所以为 LR 型。
复制代码1234JAVA private AVLNode<K, V> leftRightRotate(AVLNode<K, V> a) {
a.left = leftRotate(a.left); // 对 B 左旋
return rightRotate(a); // 对 A 右旋
}
A 结点的平衡因子为 2,说明该结点是最小不平衡结点,需要对 A 结点进行调整。问题发生在 A 结点右子结点的左子结点,所以为 RL 型。
复制代码1234JAVA private AVLNode<K, V> rightLeftRotate(AVLNode<K, V> a) {
a.right = rightRotate(a.right); return leftRotate(a);
}
复制代码123456789101112131415161718192021222324252627282930313233JAVA public void insert(K key, V value) {
root = insert(root, key, value);
} private AVLNode<K, V> insert(AVLNode<K, V> t, K key, V value) { if (t == null) { return new AVLNode<>(key, value, );
} else if (key.compareTo(t.key) < ) {
t.left = insert(t.left, key, value);
t.height = Math.max(getHeight(t.left), getHeight(t.right)) + ; // 平衡因子判断
if (getHeight(t.left) - getHeight(t.right) == ) { if (key.compareTo(root.left.key) < ) // 左左:右旋
t = rightRotate(t); else // 左右:先左旋,再右旋
t = leftRightRotate(t);
}
} else if (key.compareTo(t.key) > ) {
t.right = insert(t.right, key, value);
t.height = Math.max(getHeight(t.left), getHeight(t.right)) + ; // 平衡因子判断
if (getHeight(t.left) - getHeight(t.right) == -) { if (key.compareTo(root.right.key) > ) // 右右:左旋
t = leftRotate(t); else // 右左:先右旋,再左旋
t = rightLeftRotate(t);
}
} else {
t.value = value;
} return t;
}
下面举个删除的例子:
删除以下平衡二叉树中的 16 结点
1️⃣ 16 为叶子,将其删除即可,如下图。
2️⃣ 指针 g 指向实际被删除节点 16 之父 25,检查是否失衡,25 节点失衡,用 g 、u 、v 记录失衡三代节点(从失衡节点沿着高度大的子树向下找三代),判断为 RL 型,进行 RL 旋转调整平衡,如下图所示。
3️⃣ 继续向上检查,指针 g 指向 g 的双亲 69,检查是否失衡,69 节点失衡,用 g 、u 、v 记录失衡三代节点,判断为 RR 型,进行 RR 旋转调整平衡,如下图所示。
代码描述:
复制代码1234567891011121314151617181920212223242526272829303132333435363738394041424344JAVA public void remove(K key) {
this.root = delete(root, key);
} public AVLNode<K, V> delete(AVLNode<K, V> t, K key) { if (t == null) return t; if (key.compareTo(t.key) < ) {
t.left = delete(t.left, key);
} else if (key.compareTo(t.key) > ) {
t.right = delete(t.right, key);
} else { if(t.left == null) return t.right; else if(t.right == null) return t.left; else { // t.left != null && t.right != null
AVLNode<K, V> pre = t.left; while (pre.right != null) {
pre = pre.right;
}
t.key = pre.key;
t.value = pre.value;
t.left = delete(t.left, t.key);
}
} if (t == null) return t;
t.height = Math.max(getHeight(t.left), getHeight(t.right)) + ; if(getHeight(t.left) - getHeight(t.right) >= ) { if(getHeight(t.left.left) > getHeight(t.left.right)) { return rightRotate(t);
} else { return leftRightRotate(t);
}
} else if(getHeight(t.left) - getHeight(t.right) <= -) { if(getHeight(t.right.left) > getHeight(t.right.right)) { return rightLeftRotate(t);
} else { return leftRotate(t);
}
} return t;
}
复制代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171JAVAclass AVLNode<K extends Comparable<K>, V> { public K key; public V value; public int height; public AVLNode<K, V> left; public AVLNode<K, V> right; public AVLNode(K key, V value, int height) {
this.key = key;
this.value = value;
this.height = height;
}
}class AVLTree<K extends Comparable<K>, V> { public AVLNode<K, V> root; public int getHeight(AVLNode<K, V> t) { return t == null ? : t.height;
} public void insert(K key, V value) {
root = insert(root, key, value);
} public void remove(K key) {
this.root = delete(root, key);
} public AVLNode<K, V> delete(AVLNode<K, V> t, K key) { if (t == null) return t; if (key.compareTo(t.key) < ) {
t.left = delete(t.left, key);
} else if (key.compareTo(t.key) > ) {
t.right = delete(t.right, key);
} else { if(t.left == null) return t.right; else if(t.right == null) return t.left; else { // t.left != null && t.right != null
AVLNode<K, V> pre = t.left; while (pre.right != null) {
pre = pre.right;
}
t.key = pre.key;
t.value = pre.value;
t.left = delete(t.left, t.key);
}
} if (t == null) return t;
t.height = Math.max(getHeight(t.left), getHeight(t.right)) + ; if(getHeight(t.left) - getHeight(t.right) >= ) { if(getHeight(t.left.left) > getHeight(t.left.right)) { return rightRotate(t);
} else { return leftRightRotate(t);
}
} else if(getHeight(t.left) - getHeight(t.right) <= -) { if(getHeight(t.right.left) > getHeight(t.right.right)) { return rightLeftRotate(t);
} else { return leftRotate(t);
}
} return t;
} private AVLNode<K, V> insert(AVLNode<K, V> t, K key, V value) { if (t == null) { return new AVLNode<>(key, value, );
} if (key.compareTo(t.key) < ) {
t.left = insert(t.left, key, value); // 平衡因子判断
if (getHeight(t.left) - getHeight(t.right) == ) { if (key.compareTo(t.left.key) < ) // 左左:右旋
t = rightRotate(t); else // 左右:先左旋,再右旋
t = leftRightRotate(t);
}
} else if (key.compareTo(t.key) > ) {
t.right = insert(t.right, key, value); // 平衡因子判断
if (getHeight(t.left) - getHeight(t.right) == -) { if (key.compareTo(t.right.key) > ) // 右右:左旋
t = leftRotate(t); else // 右左:先右旋,再左旋
t = rightLeftRotate(t);
}
} else {
t.value = value;
}
t.height = Math.max(getHeight(t.left), getHeight(t.right)) + ; return t;
} private AVLNode<K, V> rightLeftRotate(AVLNode<K, V> a) {
a.right = rightRotate(a.right); return leftRotate(a);
} private AVLNode<K, V> leftRightRotate(AVLNode<K, V> a) {
a.left = leftRotate(a.left); return rightRotate(a);
} private AVLNode<K, V> leftRotate(AVLNode<K, V> a) { AVLNode<K, V> b = a.right;
a.right = b.left;
b.left = a;
a.height = Math.max(getHeight(a.left), getHeight(a.right)) + ;
b.height = Math.max(getHeight(b.left), getHeight(b.right)) + ; return b;
} private AVLNode<K, V> rightRotate(AVLNode<K, V> a) { AVLNode<K, V> b = a.left;
a.left = b.right;
b.right = a;
a.height = Math.max(getHeight(a.left), getHeight(a.right)) + ;
b.height = Math.max(getHeight(b.left), getHeight(b.right)) + ; return b;
} private void inorder(AVLNode<K, V> root) { if (root != null) {
inorder(root.left); System.out.print("(key: " + root.key + " , value: " + root.value + " , height: " + root.height + ") ");
inorder(root.right);
}
} private void preorder(AVLNode<K, V> root) { if (root != null) { System.out.print("(key: " + root.key + " , value: " + root.value + " , height: " + root.height + ") ");
preorder(root.left);
preorder(root.right);
}
} private void postorder(AVLNode<K, V> root) { if (root != null) {
postorder(root.left);
postorder(root.right); System.out.print("(key: " + root.key + " , value: " + root.value + " , height: " + root.height + ") ");
}
} public void postorderTraverse() { System.out.print("后序遍历:");
postorder(root); System.out.println();
} public void preorderTraverse() { System.out.print("先序遍历:");
preorder(root); System.out.println();
} public void inorderTraverse() { System.out.print("中序遍历:");
inorder(root); System.out.println();
}
}
方法测试
复制代码JAVA public static void main(String[] args) {
AVLTree<Integer, Integer> tree = new AVLTree<>();
tree.insert(, );
tree.insert(, );
tree.insert(, );
tree.insert(, );
tree.insert(, );
tree.insert(, );
tree.insert(, );
tree.insert(, );
tree.insert(, );
tree.insert(, );
tree.insert(, );
tree.insert(, );
tree.remove();
tree.preorderTraverse();
tree.inorderTraverse();
tree.postorderTraverse();
}
输出
复制代码123JAVA先序遍历:(key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) 中序遍历:(key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) 后序遍历:(key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: ) (key: , value: , height: )
本文作者:gonghr 本文链接: https://www.cnblogs.com/gonghr/p/16064797.html
本文就是愿天堂没有BUG给大家分享的内容,大家有收获的话可以分享下,想学习更多的话可以到微信公众号里找我,我等你哦。