数据结构_平衡二叉树(AVL)

古城微笑少年丶 2023-07-12 05:17 7阅读 0赞

### 文章目录 ###

*  介绍
 *  左旋转
 *  右旋转
 *  双旋转

# 介绍 #

*  平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树， 可以保证查询效率较高。
 *  它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

# 左旋转 #

如果右子树高度-左子树高度>1,左旋转

/**
     * 左旋转
     */
    private void leftRotate() {
        
    	//创建新的结点，以当前根结点的值
    	Node newNode = new Node(val);
    	//把新的结点的左子树设置成当前结点的左子树
    	newNode.left = left;
    	//把新的结点的右子树设置成当前结点的右子树的左子树
    	newNode.right = right.left;
    	//把当前结点的值替换成右子结点的值
    	val = right.val;
    	//把当前结点的右子树设置成当前结点右子树的右子树
    	right = right.right;
    	//把当前结点的左子树(左子结点)设置成新的结点
    	left = newNode;
    }

# 右旋转 #

如果左子树高度-右子树高度>1,右旋转

/**
     * 右旋转
     */
    private void rightRotate() {
        
    	//创建新的结点，以当前根结点的值
    	Node newNode = new Node(val);
    	//把新的结点的右子树设置成当前结点的右子树
    	newNode.right = right;
    	//把新的结点的左子树设置成当前结点的左子树的右子树
    	newNode.left = left.right;
    	//把当前结点的值替换成左子结点的值
    	val = left.val;
    	//把当前结点的左子树设置成当前结点左子树的左子树
    	left = left.left;
    	//把当前结点的右子树(右子结点)设置成新的结点
    	right = newNode;
    }

# 双旋转 #

/**
     * 添加节点
     * @param val
     */
    public void add(int val) {
        
    	if (val < this.val) {
        
    		if (this.left == null) {
        
    			this.left = new Node(val);
    		} else {
        
    			this.left.add(val);
    		}
    	} else {
        
    		if (this.right == null) {
        
    			this.right = new Node(val);
    		} else {
        
    			this.right.add(val);
    		}
    	}
    	//如果右子树高度-左子树高度>1,左旋转
    	if (rightHeight() - leftHeight() > 1) {
        
    		//如果右子树的左子树高度>右子树的右子树高度，将右子树先进行右旋转
    		if (right != null && right.leftHeight() > right.rightHeight()) {
        
    			right.rightRotate();
    		}
    		leftRotate();
    	}
    	//如果左子树高度-右子树高度>1,,右旋转
    	if (leftHeight() - rightHeight() > 1) {
        
    		//如果左子树的右子树高度>左子树的左子树高度，将左子树先进行左旋转
    		if (left != null && left.rightHeight() > left.leftHeight()) {
        
    			left.leftRotate();
    		}
    		rightRotate();
    	}
    }