AVl should be the most classic balanced binary search tree. The definition of balance in AVl is as follows: it means that the height difference between the left and right subtrees of any node is not more than 1; The AVL name is composed of the first letters of two people;
1, Node Node class and constructor
In order to facilitate the implementation of AVLTree mapping maps, we set the generic to the form of K V key-value pairs;
Node Node classes include key, value, left and right nodes, and Node height. The node height variable is used to maintain balance;
The root node attribute represents the root node. The size attribute represents the number of elements in AVL.
GetSize returns the number of elements; IsEmpty returns whether AVl isEmpty;
public class AVLTree<K extends Comparable<K>, V> { private class Node{ public K key; public V value; public Node left, right; public int height; public Node(K key, V value){ this.key = key; this.value = value; left = null; right = null; height = 1; } } private Node root; private int size; public AVLTree(){ root = null; size = 0; } public int getSize(){ return size; } public boolean isEmpty(){ return size == 0; },,}Copy the code2. Judge whether binary tree is binary search tree and balanced binary tree
The way to determine whether a binary search tree is a binary search tree is to use middle-order traversal. We know that middle-order traversal of a binary search tree is in order, so we can add elements to the ArrayList by middle-order traversal, and then compare the two adjacent elements in turn.
To judge whether it is a balanced binary tree, we use the height attribute value of the node; We use recursion to judge. We call the height difference between the left and right subtrees of the node as the balance factor. Therefore, if the balance factor is greater than 1, it means that it is not a balanced binary tree, false is returned. Otherwise, continue to look at the balance factor of the left and right subtrees until the recursion ends;
Public Boolean isBST(){ArrayList<K> keys = new ArrayList<>(); inOrder(root, keys); for(int i = 1 ; i < keys.size() ; i ++) if(keys.get(i - 1).compareTo(keys.get(i)) > 0) return false; return true; } private void inOrder(Node node, ArrayList<K> keys){ if(node == null) return; inOrder(node.left, keys); keys.add(node.key); inOrder(node.right, keys); } public Boolean isBalanced(){return isBalanced(root);} // check whether the binary tree isBalanced. } private Boolean isBalanced(Node Node){if(Node == null) return true; int balanceFactor = getBalanceFactor(node); if(Math.abs(balanceFactor) > 1) return false; return isBalanced(node.left) && isBalanced(node.right); } private int getHeight(node node){if(node == null) return 0; return node.height; } private int getBalanceFactor(node node){if(node == null) return 0; return getHeight(node.left) - getHeight(node.right); }Copy the code3, right rotation and left rotation operation
When the three nodes x, Y and Z degenerate into a positive and oblique linked list style, the right rotation operation is required. At this time, the right rotation of y node is performed and the new root node X is returned after rotation.
When the three nodes x, Y and Z degenerate into an antiskew linked list style, the sitting rotation operation is required. At this time, the y node is rotated left and the new root node X is returned after rotation.
// Rotate y to the right, Return to rotate after the new root node x/x/y / / /, /, / / x T4 spin to the right (y) z y / / / \ -- -- -- -- -- -- -- -- > /, /, / / z T3 T1 T2, T3, T4 / / / / / / T1 T2 private Node rightRotate(Node y) { Node x = y.left; Node T3 = x.right; // right rotation process x.light = y; y.left = T3; // Update height y.eight = math.max (getHeight(y.ft), getHeight(y.ft)) + 1; x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1; return x; } // Rotate y to the left, Return to rotate after the new root node x/x/y / / /, /, / / T1 left rotation (y) x y z / / / \ -- -- -- -- -- -- -- -- > / \ \ / T1 / T2 z T2, T3, T4 / / / / / / T3, T4 private Node leftRotate(Node y) { Node x = y.right; Node T2 = x.left; // rotate to the left x.left = y; y.right = T2; // Update height y.eight = math.max (getHeight(y.ft), getHeight(y.ft)) + 1; x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1; return x; }Copy the code4. Add elements to AVL tree
Adding elements to an AVL tree is the same as adding elements to a binary search tree by recursion;
After adding elements, we need to maintain balance, first updating the height of the node, then calculating the balance factor, and finally maintaining balance by rotating left or right according to the four cases of imbalance, which we have discussed above.
// Add a new element to AVL (key, value) public void add(K key, V value){root = add(root, key, value); } // Insert the element (key, value) into the binary search tree with node as the root. Private Node add(Node Node, K key, V value){if(Node == null){size ++; return new Node(key, value); } if(key.compareTo(node.key) < 0) node.left = add(node.left, key, value); else if(key.compareTo(node.key) > 0) node.right = add(node.right, key, value); else // key.compareTo(node.key) == 0 node.value = value; // Update height node.height = 1 + math. Max (getHeight(node.left), getHeight(node.right)); Int balanceFactor = getBalanceFactor(node); If (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) return rightRotate(node); // RR if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) return leftRotate(node); // LR if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) { node.left = leftRotate(node.left); return rightRotate(node); } // RL if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) { node.right = rightRotate(node.right); return leftRotate(node); } return node; }Copy the codeFind and modify elements from the AVL tree
Searching and modifying elements in AVL tree does not involve the maintenance of balance, so it is exactly the same as binary search tree, which can be directly recursed to the left and right subtrees to search for modifications.
Public Boolean contains(K key){return getNode(root, key)! = null; } public V get(K key){Node Node = getNode(root, key); return node == null ? null : node.value; } public void set(K key, V newValue){Node Node = getNode(root, key); if(node == null) throw new IllegalArgumentException(key + " doesn't exist!" ); node.value = newValue; } private node getNode(node node, K key){if(node == null) return null; if(key.equals(node.key)) return node; else if(key.compareTo(node.key) < 0) return getNode(node.left, key); else // if(key.compareTo(node.key) > 0) return getNode(node.right, key); }Copy the code6. Delete elements from AVL tree
The minimum function is used to return the node with the minimum value at the root. This subfunction is used when deleting elements.
Remove Remove element function, first look for the element, if found, call recursive function delete, if not directly return null;
In the recursive function, the beginning is the same as binary search tree, recursively delete the left and right subtrees. When the value of the node is equal to the value of the element to be deleted, it means that the node is the node to be deleted. At this time, the left subtree of the node to be deleted is empty, the right subtree of the node to be deleted is empty, and the left and right subtrees of the node to be deleted are not empty.
After removing elements, we still need to maintain the balance, which is basically the same process as adding elements.
Private node minimum(node node){if(node. Left == null) return node; return minimum(node.left); } // Remove the key from the binary search tree public V remove(K key){Node Node = getNode(root, key); if(node ! = null){ root = remove(root, key); return node.value; } return null; } private Node remove(Node node, K key){ if( node == null ) return null; Node retNode; if( key.compareTo(node.key) < 0 ){ node.left = remove(node.left , key); // return node; retNode = node; } else if(key.compareTo(node.key) > 0 ){ node.right = remove(node.right, key); // return node; retNode = node; } else{// key.compareTo(node.key) == 0 // If (node.left == null){node rightNode = node.right; node.right = null; size --; // return rightNode; retNode = rightNode; Else if(node.right == null){node leftNode = node.left; node.left = null; size --; // return leftNode; retNode = leftNode; } // If the left and right subtrees of the Node to be deleted are not empty else{// Find the smallest Node larger than the one to be deleted, that is, the smallest Node in the right subtree of the Node to be deleted // Use this Node to replace the positions of the nodes to be deleted. //successor.right = removeMin(node.right); successor.right = remove(node.right, successor.key); successor.left = node.left; node.left = node.right = null; // return successor; retNode = successor; } } if(retNode == null) return null; // Update height retnode. height = 1 + math. Max (getHeight(retnode. left), getHeight(retnode. right)); Int balanceFactor = getBalanceFactor(retNode); If (balanceFactor > 1 && getBalanceFactor(retNode. Left) >= 0) return rightRotate(retNode); // RR if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) return leftRotate(retNode); // LR if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) { retNode.left = leftRotate(retNode.left); return rightRotate(retNode); } // RL if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) { retNode.right = rightRotate(retNode.right); return leftRotate(retNode); } return retNode; }Copy the code7. All AVLTree codes
import java.util.ArrayList;
public class AVLTree<K extends Comparable<K>, V> {
private class Node{
public K key;
public V value;
public Node left, right;
public int height;
public Node(K key, V value){
this.key = key;
this.value = value;
left = null;
right = null;
height = 1;
}
}
private Node root;
private int size;
public AVLTree(){
root = null;
size = 0;
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
// 判断该二叉树是否是一棵二分搜索树
public boolean isBST(){
ArrayList<K> keys = new ArrayList<>();
inOrder(root, keys);
for(int i = 1 ; i < keys.size() ; i ++)
if(keys.get(i - 1).compareTo(keys.get(i)) > 0)
return false;
return true;
}
private void inOrder(Node node, ArrayList<K> keys){
if(node == null)
return;
inOrder(node.left, keys);
keys.add(node.key);
inOrder(node.right, keys);
}
// 判断该二叉树是否是一棵平衡二叉树
public boolean isBalanced(){
return isBalanced(root);
}
// 判断以Node为根的二叉树是否是一棵平衡二叉树，递归算法
private boolean isBalanced(Node node){
if(node == null)
return true;
int balanceFactor = getBalanceFactor(node);
if(Math.abs(balanceFactor) > 1)
return false;
return isBalanced(node.left) && isBalanced(node.right);
}
// 获得节点node的高度
private int getHeight(Node node){
if(node == null)
return 0;
return node.height;
}
// 获得节点node的平衡因子
private int getBalanceFactor(Node node){
if(node == null)
return 0;
return getHeight(node.left) - getHeight(node.right);
}
// 对节点y进行向右旋转操作，返回旋转后新的根节点x
// y x
// / \ / \
// x T4 向右旋转 (y) z y
// / \ - - - - - - - -> / \ / \
// z T3 T1 T2 T3 T4
// / \
// T1 T2
private Node rightRotate(Node y) {
Node x = y.left;
Node T3 = x.right;
// 向右旋转过程
x.right = y;
y.left = T3;
// 更新height
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
// 对节点y进行向左旋转操作，返回旋转后新的根节点x
// y x
// / \ / \
// T1 x 向左旋转 (y) y z
// / \ - - - - - - - -> / \ / \
// T2 z T1 T2 T3 T4
// / \
// T3 T4
private Node leftRotate(Node y) {
Node x = y.right;
Node T2 = x.left;
// 向左旋转过程
x.left = y;
y.right = T2;
// 更新height
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
// 向AVL中添加新的元素(key, value)
public void add(K key, V value){
root = add(root, key, value);
}
// 向以node为根的二分搜索树中插入元素(key, value)，递归算法
// 返回插入新节点后二分搜索树的根
private Node add(Node node, K key, V value){
if(node == null){
size ++;
return new Node(key, value);
}
if(key.compareTo(node.key) < 0)
node.left = add(node.left, key, value);
else if(key.compareTo(node.key) > 0)
node.right = add(node.right, key, value);
else // key.compareTo(node.key) == 0
node.value = value;
// 更新height
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
// 计算平衡因子
int balanceFactor = getBalanceFactor(node);
// 平衡维护
// LL
if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
return rightRotate(node);
// RR
if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0)
return leftRotate(node);
// LR
if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// RL
if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
//查找元素
public boolean contains(K key){
return getNode(root, key) != null;
}
//查找元素并返回对应的value
public V get(K key){
Node node = getNode(root, key);
return node == null ? null : node.value;
}
//修改元素的value值
public void set(K key, V newValue){
Node node = getNode(root, key);
if(node == null)
throw new IllegalArgumentException(key + " doesn't exist!");
node.value = newValue;
}
// 返回以node为根节点的二分搜索树中，key所在的节点
private Node getNode(Node node, K key){
if(node == null)
return null;
if(key.equals(node.key))
return node;
else if(key.compareTo(node.key) < 0)
return getNode(node.left, key);
else // if(key.compareTo(node.key) > 0)
return getNode(node.right, key);
}
// 返回以node为根的二分搜索树的最小值所在的节点
private Node minimum(Node node){
if(node.left == null)
return node;
return minimum(node.left);
}
// 从二分搜索树中删除键为key的节点
public V remove(K key){
Node node = getNode(root, key);
if(node != null){
root = remove(root, key);
return node.value;
}
return null;
}
private Node remove(Node node, K key){
if( node == null )
return null;
Node retNode;
if( key.compareTo(node.key) < 0 ){
node.left = remove(node.left , key);
// return node;
retNode = node;
}
else if(key.compareTo(node.key) > 0 ){
node.right = remove(node.right, key);
// return node;
retNode = node;
}
else{ // key.compareTo(node.key) == 0
// 待删除节点左子树为空的情况
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
// return rightNode;
retNode = rightNode;
}
// 待删除节点右子树为空的情况
else if(node.right == null){
Node leftNode = node.left;
node.left = null;
size --;
// return leftNode;
retNode = leftNode;
}
// 待删除节点左右子树均不为空的情况
else{
// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
// 用这个节点顶替待删除节点的位置
Node successor = minimum(node.right);
//successor.right = removeMin(node.right);
successor.right = remove(node.right, successor.key);
successor.left = node.left;
node.left = node.right = null;
// return successor;
retNode = successor;
}
}
if(retNode == null)
return null;
// 更新height
retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));
// 计算平衡因子
int balanceFactor = getBalanceFactor(retNode);
// 平衡维护
// LL
if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0)
return rightRotate(retNode);
// RR
if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0)
return leftRotate(retNode);
// LR
if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
retNode.left = leftRotate(retNode.left);
return rightRotate(retNode);
}
// RL
if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
retNode.right = rightRotate(retNode.right);
return leftRotate(retNode);
}
return retNode;
}
}
Copy the code