手撕AVL树

爱被打了一巴掌 2022-02-25 03:36 150阅读 0赞

### 手撕AVL树 ###

*   *  BST
     *  AVL Tree
     *  旋转
     *   *  右旋转
         *   *   *  将parent的左节点断开，再将断开的左节点的右子树断开，重新接到parent，作为parent新的左子树
         *  左旋转
         *  最终代码
         *  节点删除

## BST ##

BINARY SEARCH TREE二叉查找树，代表树中节点为有序存储  
所有节点都相同满足以下条件之一  
1.左子节点值大于等于根节点值且右子节点值小于根节点值  
2.左子节点值小于等于根节点值且右子节点值大于根节点值  
的二叉树即位二叉查找树  
AVL average BST 是一棵平衡的二叉查找树，通过平衡使得单次查找的时间复杂度不会超过logn

## AVL Tree ##

平衡树的特点是，任意一个节点，其左子树的高度与右子树的高度差保持在1以内（包括1）  
当出现高度差超过1的子树则进行旋转来调整，旋转时不破坏有序

## 旋转 ##

### 右旋转 ###

假设左边过高（一般这种过高表现为高度差为2，因为我们应在每次进行插入和删除时旋转进行维护，所以不会出现高度差为3的情况）  
![普通右旋][format_png]  
这时我们通过这种右旋转可以把左边过高子树的一个节点提上来，使得左子树节点高度-1，右子树节点高度+1  
伪代码就是  
parent = 要旋转的节点  
将parent的左节点断开，再将断开的左节点的右子树断开，重新接到parent，作为parent新的左子树  
将parent从他父亲断开，将parent作为他原来的左子节点（被断开的左子节点）的右子树  
最后将parent原来的父亲作为此时parent新的父节点（原来的左子节点）的父亲（就是交换位置）

代码实现

public Node rightTransformAndReturn(Node node) { 
    		System.out.println("right transform");
    		Node left = node.leftChild;
    		Node leftRightChild = left.rightChild;
    		if(leftRightChild!=null) { 
    			leftRightChild.parent = node;
    			leftRightChild.status = LEFTSTATUS;
    		}
    		node.leftChild = leftRightChild;
    		left.rightChild = node;
    		left.parent = node.parent;
    		node.parent = left;
    		left.status = node.status;
    		if(node.status == LEFTSTATUS) { 
    			left.parent.leftChild = left;
    		}
    		else if(node.status == RIGHTSTATUS){ 
    			left.parent.rightChild = left;
    		}
    		else { 
    			root = left;
    		}
    		node.status = RIGHTSTATUS;
    		while(node!=null) { 
    			node.height = Math.max(getHeight(node.leftChild)+1, getHeight(node.rightChild)+1);
    			node = node.parent;
    		}
    		node = left;
    		return node;
    	}

上面只分析了第一种情况，有时左子树会是这样  
![特殊右旋][format_png 1]  
这时如果按照第一种的做法，此时最终结果会使得右子树高于左子树导致不平衡  
原因是第一步里有 这一步

##### 将parent的左节点断开，再将断开的左节点的右子树断开，重新接到parent，作为parent新的左子树 #####

这一步是为了保证其有序不被破坏，所以从断开的是其左节点的右子树，也就是这颗右子树高度是不变的  
而后右子树又会链接到parent，如果导致树高的不平衡是这颗右子树造成，则旋转后其仍是不平衡的（因为左边减少的高度1实际是左子树的高度）

于是我们得想办法把他变回第一种情况，做法就是，先使用左旋转其parent的左子树，将其变为下图  
![特殊右旋][format_png 2]  
这时就可以使用第一种情况的方法来应对了  
至于为什么只要一次右旋转因为一开始我们就讲过，高度差不会超过2，那平衡的子树的左右结点高度差就不会超过1

### 左旋转 ###

此处就是右旋转的镜像实现，就不过多阐述

public Node leftTransformAndReturn(Node node) { 
    		System.out.println("left transform");
    		Node right = node.rightChild;
    		Node rightLeftChild = right.leftChild;
    		if(rightLeftChild!=null) { 
    			rightLeftChild.parent = node;
    			rightLeftChild.status = RIGHTSTATUS;
    		}
    		node.rightChild = rightLeftChild;
    		right.leftChild = node;
    		right.parent = node.parent;
    		node.parent = right;
    		right.status = node.status;
    		if(node.status == LEFTSTATUS) { 
    			right.parent.leftChild = right;
    		}
    		else if(node.status == RIGHTSTATUS){ 
    			right.parent.rightChild = right;
    		}
    		else { 
    			root = right;
    		}
    		node.status = LEFTSTATUS;
    		while(node!=null) { 
    			node.height = Math.max(getHeight(node.leftChild)+1, getHeight(node.rightChild)+1);
    			node = node.parent;
    		}
    		node = right;
    		return node;
    	}

### 最终代码 ###

我们将上方阐述的特殊情况（左旋转的可以联想都是对应的）总结，把对于两种情况的处理都封装  
使用递归实现

public class AVLTree { 
    
    	Node root;
    	static final int LEFTSTATUS = 0;
    	static final int RIGHTSTATUS = 1;
    
    	static class Node{ 
    		int num;
    		Node leftChild;
    		Node rightChild;
    		Node parent;
    		int height = 0;
    		int status = -1;//root
    		@Override
    		public String toString() { 
    			return num+",height["+height+"]->left["+(leftChild==null?"null":leftChild.num)+"],->right["+(rightChild==null?"null":rightChild.num)+"]";
    		}
    		
    	}
    	public void printTree(Node parent) { 
    		if(parent!=null) { 
    			System.out.println(parent);
    			printTree(parent.leftChild);
    			printTree(parent.rightChild);
    		}
    	}
    	//注意，左旋右旋会改变原来的父节点位置的节点(包括root)
    	public Node leftTransformAndReturn(Node node) { 
    		System.out.println("left transform");
    		Node right = node.rightChild;
    		//双旋转
    		if(getHeight(right.leftChild)>getHeight(right.rightChild)) { 
    			rightTransformAndReturn(right);
    		}
    		Node rightLeftChild = right.leftChild;
    		if(rightLeftChild!=null) { 
    			rightLeftChild.parent = node;
    			rightLeftChild.status = RIGHTSTATUS;
    		}
    		node.rightChild = rightLeftChild;
    		right.leftChild = node;
    		right.parent = node.parent;
    		node.parent = right;
    		right.status = node.status;
    		if(node.status == LEFTSTATUS) { 
    			right.parent.leftChild = right;
    		}
    		else if(node.status == RIGHTSTATUS){ 
    			right.parent.rightChild = right;
    		}
    		else { 
    			root = right;
    		}
    		node.status = LEFTSTATUS;
    		while(node!=null) { 
    			node.height = Math.max(getHeight(node.leftChild)+1, getHeight(node.rightChild)+1);
    			node = node.parent;
    		}
    		node = right;
    		return node;
    	}
    	public Node rightTransformAndReturn(Node node) { 
    		System.out.println("right transform");
    		Node left = node.leftChild;
    		//双旋转
    		if(getHeight(left.rightChild)>getHeight(left.leftChild)) { 
    			leftTransformAndReturn(left);
    		}
    		Node leftRightChild = left.rightChild;
    		if(leftRightChild!=null) { 
    			leftRightChild.parent = node;
    			leftRightChild.status = LEFTSTATUS;
    		}
    		node.leftChild = leftRightChild;
    		left.rightChild = node;
    		left.parent = node.parent;
    		node.parent = left;
    		left.status = node.status;
    		if(node.status == LEFTSTATUS) { 
    			left.parent.leftChild = left;
    		}
    		else if(node.status == RIGHTSTATUS){ 
    			left.parent.rightChild = left;
    		}
    		else { 
    			root = left;
    		}
    		node.status = RIGHTSTATUS;
    		while(node!=null) { 
    			node.height = Math.max(getHeight(node.leftChild)+1, getHeight(node.rightChild)+1);
    			node = node.parent;
    		}
    		node = left;
    		return node;
    	}
    
    	public int getHeight(Node node) { 
    		//获得树高，null为-1
    		return node == null ? -1 : node.height;
    	}
    	public int getBF(Node node) { 
    		//获得平衡因子---左子树高-右子树高
    		return  getHeight(node.leftChild)- getHeight(node.rightChild);
    	}
    	public void avl(Node parent) { 
    		if(parent == null) { 
    			return;
    		}
    		else { 
    			Node left = parent.leftChild;
    			Node right = parent.rightChild;
    			if(getHeight(right)>getHeight(left)+1) { 
    				leftTransformAndReturn(parent);
    			}
    			else if(getHeight(left)>getHeight(right)+1) { 
    				rightTransformAndReturn(parent);
    			}
    			else { 
    				avl(parent.parent);
    			}
    		}
    	}
    	public Node addAndReturnParent(Node node,Node parent) { 
    		if(parent == null) { 
    			root = parent = node;
    		}
    		else { 
    			if(parent.num>node.num) { 
    				//right add
    				Node right = parent.rightChild;
    				if(right == null) { 
    					node.parent = parent;
    					node.status = RIGHTSTATUS;
    					parent.rightChild = node;
    					if(parent.leftChild == null) { 
    						Node temp = parent;
    						temp.height++;
    						boolean flag = true;
    						while((temp=temp.parent)!=null && flag) { 
    							int oldHeight = temp.height;
    							temp.height = Math.max(getHeight(temp.leftChild)+1, getHeight(temp.rightChild)+1);
    							flag = (oldHeight != temp.height);
    						}
    						avl(parent);
    					}
    				}
    				else { 
    					addAndReturnParent(node,right);
    				}
    			}
    			else { 
    				//left add
    				Node left = parent.leftChild;
    				if(left == null) { 
    					node.parent = parent;
    					parent.leftChild = node;
    					node.status = LEFTSTATUS;
    					if(parent.rightChild == null) { 
    						Node temp = parent;
    						temp.height++;
    						boolean flag = true;
    						while((temp=temp.parent)!=null && flag) { 
    							int oldHeight = temp.height;
    							temp.height = Math.max(getHeight(temp.leftChild)+1, getHeight(temp.rightChild)+1);
    							flag = (oldHeight != temp.height);
    						}
    						avl(parent);
    					}
    				}
    				else { 
    					addAndReturnParent(node,left);
    				}
    			}
    		}
    		return parent;
    	}
    	public Node addNum(int num) { 
    		Node node = new Node();
    		node.num = num;
    		addAndReturnParent(node, root);
    		return node;
    	}
    	
    	public Node findNum(int num) { 
    		Node node = root;
    		while(node!=null) { 
    			if(node.num == num)
    				break;
    			else if(node.num<num)
    				node = node.leftChild;
    			else
    				node = node.rightChild;
    		}
    		return node;
    	}
    
    }

### 节点删除 ###

如果要删除节点，此时第一考虑树高，  
1.如果是叶子节点我们可以直接删除，并调整树  
2.不是叶子节点，找出一个作为替代的叶子节点，顶替其位置（只需要交换值），把问题变为第一种情况

具体的顶替查找就是，如果其左子树为空则左旋一次，变为叶子节点  
如果右子树为空则右旋一次，变为叶子结点  
如果都不为空，根据左右子树高度判断，  
从高度大的一方查找替代后能保持有序的叶子节点（此处判断主要是为了优化减少旋转的次数，不判断选择一边也不影响，因为最终都会调整）  
最后删除叶子节点后递归调整树

代码实现

public Node deleteNode(Node node) { 
    		System.out.println("delete Node...:"+node);
    		if(node == null)
    			return node;
    		if(getHeight(node)==0) { 
    			Node parent = node.parent;
    			node.parent = null;
    			if(node == root) { 
    				root = null;
    			}
    			else if(node.status == LEFTSTATUS) { 
    				parent.leftChild = null;
    				Node temp = parent;
    				boolean flag = true;
    				while((temp=temp.parent)!=null && flag) { int oldHeight = temp.height; temp.height = Math.max(getHeight(temp.leftChild)+1, getHeight(temp.rightChild)+1); flag = (oldHeight != temp.height); } avl(parent); } else { parent.rightChild = null; Node temp = parent; boolean flag = true; while((temp=temp.parent)!=null && flag) { int oldHeight = temp.height; temp.height = Math.max(getHeight(temp.leftChild)+1, getHeight(temp.rightChild)+1); flag = (oldHeight != temp.height); } avl(parent); } } else { if(node.leftChild == null) { leftTransformAndReturn(node); deleteNode(node); } else if(node.rightChild == null) { rightTransformAndReturn(node); deleteNode(node); } else if(getHeight(node.leftChild)>getHeight(node.rightChild)) { 
    				Node leftSmall = node.leftChild;
    				while(leftSmall.rightChild!=null) { 
    					leftSmall = leftSmall.rightChild;
    				}
    				node.num ^= leftSmall.num;
    				leftSmall.num ^= node.num;
    				node.num ^= leftSmall.num;
    				deleteNode(leftSmall);
    			}
    			else { 
    				Node rightBig = node.rightChild;
    				while(rightBig.leftChild!=null) { 
    					rightBig = rightBig.leftChild;
    				}
    				node.num ^= rightBig.num;
    				rightBig.num ^= node.num;
    				node.num ^= rightBig.num;
    				deleteNode(rightBig);
    			}
    		}
    		return node;
    	}
    	public Node deleteNum(int num) { 
    		Node node = findNum(num);
    		return deleteNode(node);
    	}

更多文章，请搜索公众号歪歪梯Club  
![更多资料，请搜索公众号编程宝可梦][20200521183346518.jpg]

[format_png]: /images/20220225/52d44419d0e941e1b9781eea88f0daa1.png
[format_png 1]: /images/20220225/5835dc1d1a42459dbf630c4b98af3267.png
[format_png 2]: /images/20220225/55d64ca624f846b8b33ddba4a1bf716e.png
[20200521183346518.jpg]: /images/20220225/651bee0930624aee892a7d1e5b66f0f3.png