Java实现平衡二叉排序树

素颜马尾好姑娘i 2023-07-20 13:55 3阅读 0赞

**目录：**

1.  前序：[开头：数据结构和算法][Link 1]的平衡二叉排序树部分已经介绍平衡二叉排序树了
2.  平衡二叉排序树的概念
3.  平衡二叉排序树四种不平衡的类型及解决方法
4.  算法
    
    1.  插入
    2.  删除
    3.  查找

## ##

### 一.平衡二叉排序树的概念 ###

如果树T既是平衡二叉树（树中每个结点的左右子树的高度差不超过1），又是二叉排序树，那么它就是平衡二叉排序树。

## ##

### 二.平衡二叉排序树四种不平衡的类型及解决方法 ###

在此文已经分析过：[开头：数据结构和算法][Link 1]的平衡二叉排序树部分

### 三.算法 ###

**1.插入**  
（注意：平衡因子bf=右子结点的高度-左子结点的高度）

在一个平衡的二叉排序树上插入一个关键字a的新节点的递归方法的步骤为：

1.  若平衡二叉排序树是一棵空树，则插入一个关键字为a的新节点作为这棵树的根结点，根结点的平衡因子bf为0。
2.  若a与根结点的关键字相等，则插入操作失败，返回。
3.  若a小于根结点的关键字，则递归调用插入算法，将在左子树中插入一个关键字a的新结点；并对根结点的平衡因子bf按下列规则修改：
    
    1.  若根结点的bf为1，则改为0。（注意， 因为递归调用了插入算法，所以根结点不是开始的根结点了，下面同此）
    2.  若根结点的bf为0，则改为-1。
    3.  若根结点的bf为-1，则分两种情况处理。
        
        1.  若根结点的左子结点的bf为-1，则进行“右旋”处理，并使根结点和其右子结点的bf均改为0.
        2.  若根结点的左子结点的bf为1，则进行先“左旋”后“右旋”处理，并修改根结点和左、右子结点的bf。
4.  若a大于根结点的关键字，则递归调用插入算法，将在右子树中插入一个关键字为a的新结点；并对根结点的平衡因子bf按下列规则修改：
    
    1.  若根结点的bf为-1，则改为0。
    2.  若根结点的bf为0，则改为1。
    3.  若根结点的bf为1，则分为两种情况处理：
        
        1.  若根结点的右子结点的bf为1，则进行“左旋”处理，并使根结点和其右子结点的bf均改为0。
        2.  若根结点的右子结点的bf为-1，则进行先“右旋”后“左旋”处理，并修改根结点和左、右结点的bf。
5.  代码实现：
    
        public class AVLTree<T extends Comparable<? super T>> {
        	
        	//静态内部类：表示树节点
        	private static class BinaryNode<T>{
        		T element;
        		BinaryNode<T> left;
        		BinaryNode<T> right;
        		int height;
        		
        		BinaryNode(T theElement){
        			this(theElement,null,null);
        		}
        		BinaryNode(T theElement,BinaryNode<T> lt,BinaryNode<T> rt){
        			this.element=theElement;
        			this.left=lt;
        			this.right=rt;
        		}
        	}	
        	private BinaryNode<T> root;
        	
        	public AVLTree(){
        		this.root=null;
        	}
        	
        	//功能1：置空
        	public void makeEmpty() {
        		root=null;
        	}
        	
        	//功能2：判空
        	public boolean isEmpty() {
        		return root==null;
        	}
        	
        	//功能3：查找：返回树中包含最小元
        	public T findMax() {
        		return findMax(root).element;
        	}
        	
        	//功能4：查找：返回树中包含最大元
        	public T findMin() {
        		return findMin(root).element;
        	}
        	
        	//功能5：插入
        	public void insert(T x) {
        		root=insert(x,root);
        	}
        	
        	//功能6：删除结点
        	public void remove(T x) {
        		root=remove(x,root);
        	}
        	
        	//功能7：遍历AVL树
        	public void printTree() {
        		if(root==null) {
        			System.out.println("Empty Tree");
        		}
        		else {
        			printTree(root);
        		}
        	}
        	
        	private BinaryNode<T> insert(T x,BinaryNode<T> t){
        		//1.第一种情况：若平衡二叉排序树是一棵空树
        		if(t==null) {
        			return new BinaryNode<T>(x,null,null);
        		}
        		
        		int compareResult=x.compareTo(t.element);
        		
        		//2.第二种情况：若t小于根结点的关键字
        		if(compareResult<0) {
        			t.left=insert(x,t.left);
        			if(height(t.left)-height(t.right)==2) {
        				if(x.compareTo(t.left.element)<0) {	//LL型
        					t=rotateWithLeftChild(t);		//解决：右旋
        				}else {								//LR型
        					t=doubleWidthLeftChild(t);		//解决：左右双旋
        				}									
        			}
        		}
        
        		//3.第三种情况：若t大于根结点的关键字
        		else if(compareResult>0) {
        			t.right=insert(x,t.right);
        			if(height(t.right)-height(t.left)==2) {
        				if(x.compareTo(t.right.element)>0) {	//RR型
        					t=rotateWithRightChild(t);		//解决：左旋
        				}else {								//RL型
        					t=doubleWidthRightChild(t);		//解决：右左双旋
        				}
        			}
        		}
        
        		//4.第四种情况：若相等，则什么都不用做，返回就完事了
        		else {
        			;
        		}
        
        		t.height=Math.max(height(t.left),height(t.right))+1;
        		return t;
        	}
        	
        	//计算AVL结点的高度的方法
        	private int height(BinaryNode<T> t) {
        			return t==null?-1:t.height;
        	}
         
        	//左旋转
        	private BinaryNode<T> rotateWithRightChild(BinaryNode<T> k1) {
        		BinaryNode<T> k2=k1.right;
        		k1.right=k2.left;
        		k2.left=k1;
        		k1.height=Math.max(height(k1.left), height(k1.right))+1;
        		k2.height=Math.max(height(k2.left), k1.height)+1;
        		return k2;
        	}
        		
        	//右旋转
        	private BinaryNode<T> rotateWithLeftChild(BinaryNode<T> k2) {
        		BinaryNode<T> k1=k2.left;
        		k2.left=k1.right;
        		k1.right=k2;
        		k2.height=Math.max(height(k2.left), height(k2.right))+1;
        		k1.height=Math.max(height(k1.left), k2.height)+1;
        		return k1;
        	}
        	
        	//左右双旋转(先左后右旋转)
        	private BinaryNode<T> doubleWidthLeftChild(BinaryNode<T> k3) {
        		k3.left=rotateWithRightChild(k3.left);
        		return rotateWithLeftChild(k3);
        	}
        	
        	//右左双旋转(先右后左旋转)
        	private BinaryNode<T> doubleWidthRightChild(BinaryNode<T> k1) {
        		k1.right=rotateWithLeftChild(k1.right);
        		return rotateWithRightChild(k1);
        	}
         
        	private BinaryNode<T> remove(T x, BinaryNode<T> t) {
        		if(t==null) {
        			return t;
        		}
        		
        		//比较要删除的值和结点的大小
        		int compareResult=x.compareTo(t.element);
        
        		if(compareResult<0) {
        			t.left=remove(x,t.left);
        			//这是考虑父结点的平衡(父结点层层往上，就包含了根结点的平衡性）
        			删除前树是平衡的，删除的结点在左边，所以肯定只会出现右孩子结点的高度是否比左孩子结点的高度大2造成的不平衡
        			if (height(t.right) - height(t.left) == 2) {
        				//如果t.right的右儿子结点高度大于或者等于t.right的左儿子结点的高度就左旋，否则右左双旋
        				if (height(t.right.right) >= height(t.right.left)) {
        					t = rotateWithRightChild(t);
        				} else {
        					t = doubleWidthRightChild(t);
        				}
        			}
        		}else if(compareResult>0) {
        			t.right=remove(x,t.right);
        			//这是考虑父结点的平衡(父结点层层往上，就包含了根结点的平衡性）
        			//删除前树是平衡的，删除的结点在右边，所以肯定只会出现左孩子结点的高度是否比右孩子结点的高度大2造成的不平衡
        			if (height(t.left) - height(t.right) == 2) {
        				//如果t.left的左儿子结点高度大于或者等于t.left的右儿子结点的高度就右旋，否则左右双旋
        				if (height(t.left.left) >= height(t.left.right)) {
        					t = rotateWithLeftChild(t);
        				} else {
        					t = doubleWidthLeftChild(t);
        				}
        			}
        		}else if(compareResult==0) {
        			if(t.left !=null && t.right!=null) {//删除的结点有两个子结点
        				t.element=findMin(t.right).element;
        				t.right=remove(t.element,t.right);
        				//这是考虑本身结点的平衡
        				// 如果是删除是根节点，那么就需要两种情况都考虑？因为是用右子树中最小的结点替代它，所以还是只会出现左子树的高度是否比右子树的高度大2造成的不平衡
        				if (height(t.left) - height(t.right) == 2) {
        					if (height(t.left.left) >= height(t.left.right)) {
        						t = rotateWithLeftChild(t);
        					} else {
        						t = doubleWidthLeftChild(t);
        					}
        				} /*else if (height(t.right) - height(t.left) ==2) {
        					//如果t.right的左儿子结点高度大于或者等于t.right的右儿子结点的高度就右旋，否则左右双旋
        					if (height(t.right.right) >= height(t.right.left)) {
        						t = rotateWithRightChild(t);
        					} else {
        						t = doubleWidthRightChild(t);
        					}
        				}*/
        			}else {//删除的结点没有子结点或者有一个子结点
        				t=(t.left !=null)?t.left:t.right;
        			}	
        		}
        
        		
        		//因为删除了结点，所以结点的高度重新计算
        		if (t != null) {
        			t.height = Math.max(height(t.right), height(t.left)) + 1;
        		}
        		
        		return t;
        	}
        
        	private BinaryNode<T> findMin(BinaryNode<T> t) {
        		if(t==null) {
        			return null;
        		}else if(t.left==null) {
        			return t;
        		}
        		return findMin(t.left);
        	}
        	
        	private BinaryNode<T> findMax(BinaryNode<T> t) {
        		if(t!=null) {
        			while(t.right!=null) {
        				t=t.right;
        			}
        		}
        		return t;
        	}
        	
        	//先序遍历
        	private void printTree(BinaryNode<T> t) {
        		System.out.println(t.element);
        		if(t.left!=null) {
        			printTree(t.left);
        		}
        		if(t.right!=null) {
        			printTree(t.right);
        		}
        		
        	}
        
        }
    
    测试：
    
        public class Test {
            	public static void main(String[] args) throws Throwable{
            		AVLTree<Integer> avl=new AVLTree<>();
            		avl.insert(4);
            		avl.insert(2);
            		avl.insert(6);
            		avl.insert(1);
            		avl.insert(5);
            		//先序遍历
            		avl.printTree();
           
            	}    
        }
    
    ![20200404100911252.png][]

**二.删除**

对AVL树的删除多少要比插入复杂。如果删除操作相对较少，那么懒惰删除恐怖恐怕是最好的方式。  
懒惰删除：当一个元素要被删除时，它仍然留在树中，而只是被标记为删除。

二叉排序树的结点删除分为三种情况：

1.  删除的结点没有子结点
2.  删除的结点只有一个子结点
3.  删除的结点有两个子结点

AVL树删除结点也可分为上述三种情况：但是AVL树需要考虑平衡，因此需要再分情况讨论

1.  对于要删除的节点无子节点可以直接删除，即让其父节点将该子节点置空即可，再考虑父结点的平衡性又分三种情况
    
    1.  其父结点在N删除后，如果其平衡因子：-1 <= bf <= 1，不做处理；再考虑根结点的平衡性，分为三种情况
        
        1.  如果根结点平衡因子：-1 <= bf <= 1，则结束
        2.  如果根结点平衡因子：bf = -2，如果height(t.left.left) >= height(t.left.right)那么就右旋，否则左右双旋
        3.  如果根结点平衡因子：bf =  2，如果height(t.right.right) >= height(t.right.left)那么就t结点左旋，否则右左双旋
    2.  其父结点在N删除后，如果其平衡因子：bf = -2，那么还是同上，分为三种情况；再考虑根结点，根结点情况和上面相同，分为三种情况
    3.  其父结点在N删除后，如果其平衡因子：bf = 2，那么还是同上，分为三种情况；再考虑根结点，根结点情况和上面相同，分为三种情况
2.  对于要删除的节点只有一个子节点，则替换要删除的节点为其子节点，再考虑父结点的平衡性又分三种情况
    
    1.  其父结点在N删除后，如果其平衡因子：-1 <= bf <= 1，那么不用处理；再考虑根结点的平衡性，根结点情况和上面相同，分为三种情况
    2.  其父结点在N删除后，如果其平衡因子：bf = -2，那么还是同上，分为三种情况；再考虑根结点平衡性，根结点情况和上面相同，分为三种情况
    3.  其父结点在N删除后，如果其平衡因子：bf = 2，那么还是同上，分为三种情况；再考虑根结点平衡性，根结点情况和上面相同，分为三种情况
3.  对于要删除的节点有两个子节点，则首先找该节点的替换节点（即右子树中最小的节点，因为其其没有左孩子结点，替换方便），接着替换要删除的节点为替换节点，然后删除替换节点。因为使用子树中最小的节点替代了要删除的结点，所以需要  
    先考虑替代结点的平衡性，分三种情况，同上
    
    1.  先考虑其父结点的平衡性，分三种情况，同上
        
        1.  再考虑根节点的平衡性，分三种情况，同上

**总结：**

1.  对于要删除的节点无子结点可以直接删除，不用考虑自身结点的平衡性（因为自身都没有了）然后考虑其父结点的平衡性，再考虑根结点的平衡性（共9种情况）
2.  对于要删除的节点只有一个子结点，先使用其子结点替代它，不用考虑自身结点的平衡性（因为自己只有一个结点，还用来替代被删除的结点），然后考虑其父结点的平衡性，再考虑根结点的平衡性（共9种情况）  
      
    对于第一点和第二点，可以合并为一点：  
    对于要删除的节点无子结点或者只有一个子结点，如果有左结点，就让其替代它；否则就用右结点替代它。然后考虑其父结点的平衡性，最后考虑根结点的平衡性
3.  对于要删除的节点有两个子结点，先找到其右子树中最小的结点替代它，然后考虑替代后自身结点的平衡性，再考虑其父结点的平衡性，最后考虑根结点的平衡性  
      
    代码实现如下：
    
        //功能6：删除结点
        	public void remove(T x) {
        		root=remove(x,root);
        	}
        
        	private BinaryNode<T> remove(T x, BinaryNode<T> t) {
        		if(t==null) {
        			return t;
        		}
        		
        		//比较要删除的值和结点的大小
        		int compareResult=x.compareTo(t.element);
        
        		if(compareResult<0) {
        			t.left=remove(x,t.left);
        			//这是考虑父结点的平衡(父结点层层往上，就包含了根结点的平衡性）
        			删除前树是平衡的，删除的结点在左边，所以肯定只会出现右孩子结点的高度是否比左孩子结点的高度大2造成的不平衡
        			if (height(t.right) - height(t.left) == 2) {
        				//如果t.right的右儿子结点高度大于或者等于t.right的左儿子结点的高度就左旋，否则右左双旋
        				if (height(t.right.right) >= height(t.right.left)) {
        					t = rotateWithRightChild(t);
        				} else {
        					t = doubleWidthRightChild(t);
        				}
        			}
        		}else if(compareResult>0) {
        			t.right=remove(x,t.right);
        			//这是考虑父结点的平衡(父结点层层往上，就包含了根结点的平衡性）
        			//删除前树是平衡的，删除的结点在右边，所以肯定只会出现左孩子结点的高度是否比右孩子结点的高度大2造成的不平衡
        			if (height(t.left) - height(t.right) == 2) {
        				//如果t.left的左儿子结点高度大于或者等于t.left的右儿子结点的高度就右旋，否则左右双旋
        				if (height(t.left.left) >= height(t.left.right)) {
        					t = rotateWithLeftChild(t);
        				} else {
        					t = doubleWidthLeftChild(t);
        				}
        			}
        		}else if(compareResult==0) {
        			if(t.left !=null && t.right!=null) {//删除的结点有两个子结点
        				t.element=findMin(t.right).element;
        				t.right=remove(t.element,t.right);
        				//这是考虑本身结点的平衡
        				// 如果是删除是根节点，那么就需要两种情况都考虑？因为是用右子树中最小的结点替代它，所以还是只会出现左子树的高度是否比右子树的高度大2造成的不平衡
        				if (height(t.left) - height(t.right) == 2) {
        					if (height(t.left.left) >= height(t.left.right)) {
        						t = rotateWithLeftChild(t);
        					} else {
        						t = doubleWidthLeftChild(t);
        					}
        				} /*else if (height(t.right) - height(t.left) ==2) {
        					//如果t.right的左儿子结点高度大于或者等于t.right的右儿子结点的高度就右旋，否则左右双旋
        					if (height(t.right.right) >= height(t.right.left)) {
        						t = rotateWithRightChild(t);
        					} else {
        						t = doubleWidthRightChild(t);
        					}
        				}*/
        			}else {//删除的结点没有子结点或者有一个子结点
        				t=(t.left !=null)?t.left:t.right;
        			}	
        		}
        
        		
        		//因为删除了结点，所以结点的高度重新计算
        		if (t != null) {
        			t.height = Math.max(height(t.right), height(t.left)) + 1;
        		}
        		
        		return t;
        	}

**三.查询**

和二叉排序树查找元素相同：先和根节点比较，如果相同就返回，如果小于根节点则到左子树中递归查找，如果大于根节点则到右子树中递归查找。因此在排序二叉树中可以很容易获取最大（最右最深子节点）和最小（最左最深子节点）值。

[Link 1]: https://blog.csdn.net/yiguang_820/article/details/84287481
[20200404100911252.png]: /images/20230528/f9458f4c45c74f218d472fe590271650.png