模拟平衡二叉查找树底层实现（AVL）

冷不防 2024-02-18 21:12 149阅读 0赞

GitHub源码地址：（https://github.com/BradenLei/AVL）

1、基本概念及操作：

1）平衡二叉查找树：在二叉查找树的基础上满足平衡因子为-1,0,1的树结构

2）平衡因子：右子树的高度减去左子树的高度；-1表示左偏重，+1表示右偏重

3）重新平衡数：从AVL树中插入或者删除一个元素后，如果树变得不平衡了，执行一次旋转操作来重新平衡该树，有四种方式：

LL旋转、RR旋转、LR旋转、RL旋转

以 LL说明：两个L表示两次左偏重

4）AVL树的设计：由于AVL树是二叉查找树，AVLTree设计为BST的子类（BST实现在上一篇博文中，这里不再累述）

5）重写insert、delete方法：AVL树中的这两操作基本一致，不同之处在于树可能需要重新平衡。

6）AVL树的高度为O(logn)，所以其search、insert以及delete方法的时间复杂度为O(logn)

![70][]

![70 1][]

![70 2][]

![70 3][]

AVL实现：

package binary;
    
    import java.util.ArrayList;
    
    public class AVLTree<E extends Comparable<E>> extends BST<E> {
        public AVLTree() {
        	
        }
        
        public AVLTree(E[] objects) {
        	super(objects);
        }
        
        @Override
        protected AVLTreeNode<E> createNewNode(E e){
        	return new AVLTreeNode<E>(e);
        }
        
        /**Insert an element and rebalance if necessary*/
        @Override
        public boolean insert(E e) {
        	boolean successful = super.insert(e);
        	if(!successful)
        		return false;
        	else {
        		balancePath(e);  //Balance from e to the root if necessary
        	}
        	
        	return true;
        }
        
        /**Update the height of a specified node*/
        private void updateHeight(AVLTreeNode<E> node) {
        	if(node.left == null && node.right == null) //node is a leaf
        		node.height = 0;
        	else if(node.left == null) {
        		node.height = 1 + ((AVLTreeNode<E>)(node.right)).height;
        	}
        	else if(node.right == null) {
        		node.height = 1 + ((AVLTreeNode<E>)(node.left)).height;
        	}
        	else {
        		node.height = 1 + Math.max(((AVLTreeNode<E>)(node.left)).height,((AVLTreeNode<E>)(node.right)).height);
        	}
        }
        
        /**Balance the nodes in the path from the specified
         * node to the root if necessary 
         */
        private void balancePath(E e) {
            ArrayList<TreeNode<E>> path = path(e);
            for(int i = path.size() - 1; i >= 0; i--) {
            	AVLTreeNode<E> A = (AVLTreeNode<E>)path.get(i);
            	updateHeight(A);
            	AVLTreeNode<E> parentOfA = (A == root) ? null : (AVLTreeNode<E>)(path.get(i - 1));
            	
            	switch (balanceFactor(A)) {
    			  case -2:
    				if(balanceFactor((AVLTreeNode<E>)A.left) <= 0) {
    					balanceLL(A, parentOfA);
    				}else {
    					balanceLR(A, parentOfA);
    				}
    				break;
    			  case 2:
    				  if(balanceFactor((AVLTreeNode<E>)A.right) >= 0){
    					  balanceRR(A, parentOfA);
    				  }else {
    					  balanceRL(A, parentOfA);
    				  }
    			default:
    				break;
    			}
            }
        }
        
        /**Return the balance factor of the node*/
        private int balanceFactor(AVLTreeNode<E> node) {
        	if(node.right == null) {
        		return -node.height;
        	}
        	else if(node.left == null) {
        		return + node.height;
        	}
        	else 
        		return ((AVLTreeNode<E>)node.right).height -
        				((AVLTreeNode<E>)node.left).height;
        }
        
        /**LL旋转维持平衡*/
        private void balanceLL(TreeNode<E> A,TreeNode<E> parentOfA) {
        	TreeNode<E> B = A.left;
        	
        	if(A == root) {
        		root = B;
        	}
        	else {
    			if(parentOfA.left == A) {
    				parentOfA.left = B;
    			}else {
    				parentOfA.right = B;
    			}
    		}
        	
        	A.left = B.right; //Make T2 the left subtree of A
        	B.right = A; //Make A the left child of B
        	updateHeight((AVLTreeNode<E>)A);
        	updateHeight((AVLTreeNode<E>)B);
        }
        
        /**LR旋转维持平衡*/
        private void balanceLR(TreeNode<E> A,TreeNode<E> parentOfA) {
        	TreeNode<E> B = A.left;  //A is left-heavy(左偏重)
        	TreeNode<E> C = B.right; //B is right-heavy
        	
        	if(A == root) {
        		root = C;
        	}
        	else {
        		if(parentOfA.left == A) {
        			parentOfA.left = C;
        		}else {
        			parentOfA.right = C;
        		}
        	}
        	
        	A.left = C.right;  //Make T3 the left subtree of A
        	B.right = C.left;  //Make T2 the right subtree of B
        	C.left = B;
        	C.right = A;
        	
        	updateHeight((AVLTreeNode<E>)A);
        	updateHeight((AVLTreeNode<E>)B);
        	updateHeight((AVLTreeNode<E>)C);
        }
        
        /**RR旋转维持平衡*/
        private void balanceRR(TreeNode<E> A,TreeNode<E> parentOfA) {
        	TreeNode<E> B = A.right;
        	
        	if(A == root) {
        		root = B;
        	}else {
        		if(parentOfA.left == A) {
        			parentOfA.left = B;
        		}
        		else {
        			parentOfA.right = B;
        		}
        	}
        	
        	A.right = B.left;
        	B.left = A;
        	updateHeight((AVLTreeNode<E>)A);
        	updateHeight((AVLTreeNode<E>)B);
        }
        
        
        /**RL旋转维持平衡*/
        private void balanceRL(TreeNode<E> A,TreeNode<E> parentOfA) {
        	TreeNode<E> B = A.right;
        	TreeNode<E> C = B.left;
        	
        	if(A == root) {
        		root = C;
        	}else {
        		if(parentOfA.left == A) {
        			parentOfA.left = C;
        		}else {
        			parentOfA.right = C;
        		}
        	}
        	
        	A.right = C.left;   //Make T2 the right subtree of A
        	B.left = C.right;   //Make T3 the left subtree of B
        	C.left = A;
        	C.right = B;
        	
        	updateHeight((AVLTreeNode<E>)A);
        	updateHeight((AVLTreeNode<E>)B);
        	updateHeight((AVLTreeNode<E>)C);
        }
        
        
        /**Delete an element from the AVL tree*/
        @Override
        public boolean delete(E element) {
        	if(root == null) {
        		return false;  //Element is not in the tree
        	}
        	
        	//Locate the node to be deleted and alse locate its parent node
        	TreeNode<E> parent = null;
        	TreeNode<E> current = root;
        	while(current != null) {
        		if(element.compareTo(current.element) < 0) {
        			parent = current;
        			current = current.left;
        		}
        		else if(element.compareTo(current.element) > 0){
    				parent = current;
    				current =current.right;
    			}else
    				break;
        	}
        	
        	if(current == null)
        		return false;
        	
        	//Case 1 : current has no left children
    		if(current.left == null) {
    			//父结点连接当前删除结点的右结点
    			if(parent == null) {
    				root = current.right;
    			}else {
    				if(element.compareTo(parent.element) < 0)
    					parent.left = current.right;
    				else 
    					parent.right = current.right;
    			}
    			
    			//Balance the tree if necessary
    			balancePath(parent.element);
    		}
    		else {//Case 2: 定位当前删除结点的左子树的最大值(rightmost)以及其父结点，用rightmost替换删除结点值，同时删除rightmost
    			TreeNode<E> parentOfRightMost = current;
    			TreeNode<E> rightmost = current.left;
    			
    			while(rightmost.right != null) {
    				parentOfRightMost = rightmost;
    				rightmost = rightmost.right;
    			}
    			//Replace the element in current by the element in rightmost
    			current.element = rightmost.element;
    			
    			if(parentOfRightMost.right == rightmost)
    				parentOfRightMost.right = rightmost.left;
    			else //Special case : parentRightMost == current ， 必须考虑这种情况
    				parentOfRightMost.left = rightmost.left;
    			
    			//Balance the tree if necessary
    			balancePath(parentOfRightMost.element);
    		}
    		
    		size--;
    		return true;
        }
        
        
        /**定义AVLTreeNode结点*/
        protected static class AVLTreeNode<E extends Comparable<E>> extends BST.TreeNode<E>{
            protected int height = 0;
            
    		public AVLTreeNode(E e) {
    			super(e);
    		}
        }
    }

测试分析：

package binary;
    
    public class TestAVLTree {
    
    	public static void main(String[] args) {
              AVLTree<Integer> tree = new AVLTree<>(new Integer[] {
            		  25,20,5
              });
              
              System.out.println("After inserting 25 20 5:");
              printTree(tree);
              
              tree.insert(34);
              tree.insert(50);
              System.out.println("\nAfter inserting 34,50:");
              printTree(tree);
              
              tree.insert(30);
              System.out.println("\nAfter inserting 30:");
              printTree(tree);
              
              tree.insert(10);
              System.out.println("\nAfter inserting 10:");
              printTree(tree);
              
              tree.delete(34);
              tree.delete(30);
              tree.delete(50);
              System.out.println("\nAfter removing 34,30,50:");
              printTree(tree);
              
              tree.delete(5);
              System.out.println("\nAfter removing 5:");
              printTree(tree);
              
              System.out.println("\nTraverse the elements in the tree:");
              for (int e : tree) {
    			System.out.print(e + " ");
    		}
    	}
    
    	public static void printTree(BST tree) {
    		System.out.print("Inorder:(Sorted) " );
    		tree.inorder();
    		System.out.print("\nPostorder: ");
    		tree.postorder();
    		System.out.print("\nPreorder: ");
    		tree.preorder();
    		System.out.print("\nThe number of nodes is " + tree.getSize());
    		System.out.println();		
    	}	
    }
    
    
    /**
    After inserting 25 20 5:
    Inorder:(Sorted) 5 20 25 
    Postorder: 5 25 20 
    Preorder: 20 5 25 
    The number of nodes is 3
    
    After inserting 34,50:
    Inorder:(Sorted) 5 20 25 34 50 
    Postorder: 5 25 50 34 20 
    Preorder: 20 5 34 25 50 
    The number of nodes is 5
    
    After inserting 30:
    Inorder:(Sorted) 5 20 25 30 34 50 
    Postorder: 5 20 30 50 34 25 
    Preorder: 25 20 5 34 30 50 
    The number of nodes is 6
    
    After inserting 10:
    Inorder:(Sorted) 5 10 20 25 30 34 50 
    Postorder: 5 20 10 30 50 34 25 
    Preorder: 25 10 5 20 34 30 50 
    The number of nodes is 7
    
    After removing 34,30,50:
    Inorder:(Sorted) 5 10 20 25 
    Postorder: 5 20 25 10 
    Preorder: 10 5 25 20 
    The number of nodes is 4
    
    After removing 5:
    Inorder:(Sorted) 10 20 25 
    Postorder: 10 25 20 
    Preorder: 20 10 25 
    The number of nodes is 3
    
    Traverse the elements in the tree:
    10 20 25 
    */

[70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/700881bab790479da88d00ea0db0cf9e.png
[70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/5e812340473b45dfa69addfe8b441e53.png
[70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/a4da1162a9eb4f64b8a0cb4c45061716.png
[70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/d09390d9981144febe649b00a246364f.png