avl树 订阅
在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis,他们在1962年的论文《An algorithm for the organization of information》中发表了它。 展开全文
在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis,他们在1962年的论文《An algorithm for the organization of information》中发表了它。
信息
外文名
AVL tree
特    点
最先发明
发明时间
1962
含    义
自平衡二叉查找树
中文名
AVL树
词汇来源
计算机科学
AVL树特点
AVL树本质上还是一棵二叉搜索树,它的特点是: [1]  1.本身首先是一棵二叉搜索树。2.带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。也就是说,AVL树,本质上是带了平衡功能的二叉查找树(二叉排序树,二叉搜索树)。
收起全文
精华内容
下载资源
问答
  • avl树
    2021-05-22 16:38:43

    一、什么是AVL树?

    首先解释一下为什么会出现AVL树,上一篇我们学习了二叉搜索树,现在我们来分析一下二叉搜索树的时间复杂度。我们会发现在某些情况下,二叉搜索树的时间复杂度会由O(logn)会退化为O(n),所以AVL树就出现了,就是说AVL树是二叉搜索树的一种改进。AVL树里多了一个平衡因子的概念。其实很好理解,平衡因子就是对树平衡程度的一种度量。

    平衡因子:该节点的左子树的高度减去右子树的高度的差值就叫做该节点的平衡因子。

    AVL树的平衡因子只可能是-1、0、1,AVL树的添加、删除时间复杂度都是O(logn)。

    假如某节点的平衡因子大于1或者小于-1,我们就认为该节点是失衡的。

    二、AVL树的添加

    我们先来看一个例子,我们往二叉树中添加节点13,节点14的平衡因子变成了2,节点15平衡因子变成了2,节点9的平衡因子变成了-2。不幸的是它们全部失衡了,你会发现失衡的节点全是添加节点的祖父节点。

    那么问题就很明显了,怎么解决失衡问题?答案只有两个字:自旋

    我们先梳理一下总体思路:

    1.通过加入的节点,不断循环,找到它的父节点。

    2.然后判断该节点是否失衡,如果不失衡,更新高度;如果失衡,进行自旋

    第一种情况:右旋

    假设我们不看中间的图,你很快就会发现自旋的节点高度会下降,此时我们自旋的节点就是g。如果我们找到了第一个失衡节点,并通过自旋达到了平衡。那么就说明整颗树就达到了平衡。思考一下为什么?仔细观察一下添加节点之前树的高度添加节点后自旋后树的高度是一样的,那不就说明整颗树现在是平衡的。

    节点g右旋的操作:

    g.left = p.right

    p.right = g;

    让节点p成为子树的根节点 

    更新T2、g的父节点

    更新节点p,g的高度

     

    第二种情况:左旋

    节点g左旋的操作:

    g.right = p.left

    p.left = g;

    让节点p成为子树的根节点 

    更新T1、g的父节点

    更新节点p,g的高度

    第三种情况:左右旋

    先将节点p左旋,然后将节点g右旋

    第四种情况:右左旋

     

     

    下面开始coding:

    这里我们继承的是我们上一次写的二叉搜索树,我们要做的就是在原来添加的方法后,增加一个balanceTree(Node<E> node)即可。

    public class AVLTree<E> extends BST<E> {
    
            private static class AVLNode<E> extends Node<E>{
    		    int height; //AVL树的高度
    		    public AVLNode(E element, Node<E> parent) {
    		   	    super(element, parent);
    		    }
    
              //其实就是取左子树和右子树中高度比较高的,然后加1
              public void updateHeight() {
    			int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
    			int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
    			height = 1 + Math.max(leftHeight, rightHeight);
    		  }
    
            //返回左子树和右子树比较高的子树
    		public Node<E> tallerChild() {
    			int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
    			int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
    			if (leftHeight >= rightHeight){
    				return left;
    			}else{
    				return right;
    			}
    		}
    	  }
    }

    我们重写父类的方法:

    @Override
    	protected void balanceTree(Node<E> node) {
    		//需要通过节点找到第一个失衡的节点
    		while((node = node.parent)!=null){
    			if(isBalance(node)){
    				//更新高度
    				updateHigh(node);
    			}else{
    				//自旋,维持平衡
    				rebalance(node);
    			}
    		}
    	}
    //更新高度的方法
    private void updateHigh(Node<E> node){
    	((AVLNode<E>)node).updateHeight();
    }

    剩下最核心的就是自旋了:

    我把思路写下来:

    1.首先通过这个不平衡的节点grand,找到节点p,然后通过节点n

    2.节点的方判断是上面的四种情况:LL-右旋 ,LR-左右旋,RR-左旋,RL-右左旋

        /**
    	 * 恢复平衡
    	 * @param grand 高度最低的那个不平衡节点
    	 */
    	private void rebalance(Node<E> grand) {
    		Node<E> parent = ((AVLNode<E>)grand).tallerChild(); //parent就是节点p
    		Node<E> node = ((AVLNode<E>)parent).tallerChild(); //节点node就是节点n
    		if(parent == node.left){ 
    			if(node == parent.left){ //LL - 右旋
    				rightTurn(grand);
    			}else{ //LR -左右旋
    				lefTurn(parent);
    				rightTurn(grand);
    			}
    		}else{ 
    			if(node == parent.right){ //RR - 左旋
    				lefTurn(grand);
    			}else{ //RL - 右左旋
    				rightTurn(parent);
    				lefTurn(grand);
    			}
    		}
    		updateHigh(grand);
    		updateHigh(parent);
    	}

    左右旋的步骤就是我们上面总结的:

    //左旋
    private void lefTurn(Node<E> grand) {
    		Node<E> parent = grand.right; //节点p
    		Node<E> child = parent.left; //子树T1
    		grand.right = child;
    		parent.left = grand;
    		//让p成为根节点
    		parent.parent = grand.parent;
    		if(grand == grand.parent.left){
    			grand.parent.left = parent;
    		}else if(grand == grand.parent.right){
    			grand.parent.right = parent;
    		}else{
    			root = parent;
    		}
    		if(child!=null){
    			child.parent = grand; //更新t1的parent
    		}
    		grand.parent = parent; //更新grand的parent
    	}
       
    
        //右旋
    	private void rightTurn(Node<E> grand) {
    		Node<E> parent = grand.left; //节点p
    		Node<E> child = parent.right; //子树T2
    		grand.left = child;
    		parent.right = grand;
    		//让p成为根节点
    		parent.parent = grand.parent;
    		if(grand == grand.parent.left){
    			grand.parent.left = parent;
    		}else if(grand == grand.parent.right){
    			grand.parent.right = parent;
    		}else{
    			root = parent;
    		}
    
    		//更新parent属性
    		if(child!=null){
    			child.parent = grand;
    		}
    		grand.parent = parent;
    
    	}

    我们发现上面四种情况很麻烦,有大佬找到了规律,我们一起看看。

    统一所有旋转操作:

    我们发现无论是哪种旋转,最后得到的树的结构都是一致的,所以我们可以写一个方法就可以,参数就是:a,b,c,d,e,f,g七个节点。

    private void rotate(
    			Node<E> r, // 子树的根节点
    			Node<E> b, Node<E> c,
    			Node<E> d,
    			Node<E> e, Node<E> f) {
    		// 让d成为这棵子树的根节点
    		d.parent = r.parent;
    		if (r.isLeftChild()) {
    			r.parent.left = d;
    		} else if (r.isRightChild()) {
    			r.parent.right = d;
    		} else {
    			root = d;
    		}
    
    		//b-c
    		b.right = c;
    		if (c != null) {
    			c.parent = b;
    		}
    		updateHigh(b);
    
    		// e-f
    		f.left = e;
    		if (e != null) {
    			e.parent = f;
    		}
    		updateHigh(f);
    
    		// b-d-f
    		d.left = b;
    		d.right = f;
    		b.parent = d;
    		f.parent = d;
    		updateHigh(d);
    	}

    三、AVL树的删除

    首先思考删除节点,会导致谁的失衡。删除节点16, 节点15和节点11失衡,我们会发现删除节点影响的是父节点或者是祖父节点的平衡因子,从而会导致它们的失衡。

    删除方法还是和添加方法是有点区别的:

    添加的时候我们只需要找到高度最低的节点,通过旋转,就能使整颗树达到平衡,原因在上面已经讲过了。但是删除不一样,举个例子:看上面左边这个二叉树,删除节点16导致节点15失衡,然后我们通过右旋节点15,但是这个子树树的高度变了,比原来少了1,那不就可能影响16更上面的祖父节点的平衡因子吗?所以我们需要一直迭代下去,知道整颗树的平衡。

    
    	@Override
    	protected void afterRemove(Node<E> node) {
    		while ((node = node.parent) != null) {
    			if (isBalanced(node)) {
    				// 更新高度
    				updateHeight(node);
    			} else {
    				// 恢复平衡
    				rebalance(node);
    			}
    		}
    	}

    最后给出完整的代码:

    第一个类是核心代码:后面两个类就是上次写的二叉搜索树,因为AVL树也是一种二叉搜素树,只不过它比二叉搜索树多了一个维持自己平衡的动作,正是这个动作使得AVL树的时间复杂度维持在O(logn),不会出现二叉搜索树退化成链表的情况。

    package AVL树;
    
    import java.util.Comparator;
    
    public class AVLTree<E> extends BST<E> {
    
    	private static class AVLNode<E> extends Node<E>{
    		int height; //AVL树的高度
    		public AVLNode(E element, Node<E> parent) {
    			super(element, parent);
    		}
    
    		public void updateHeight() {
    			int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
    			int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
    			height = 1 + Math.max(leftHeight, rightHeight);
    		}
    
    		public Node<E> tallerChild() {
    			int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
    			int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
    			if (leftHeight >= rightHeight){
    				return left;
    			}else{
    				return right;
    			}
    		}
    	}
    
    
    	@Override
    	protected void balanceTree(Node<E> node) {
    		//需要通过节点找到第一个失衡的节点
    		while((node = node.parent)!=null){
    			if(isBalance(node)){
    				//更新高度
    				updateHigh(node);
    			}else{
    				//自旋,维持平衡
    				rebalance(node);
    			}
    		}
    	}
    
    	/**
    	 * 恢复平衡
    	 * @param grand 高度最低的那个不平衡节点
    	 */
    	private void rebalance(Node<E> grand) {
    		Node<E> parent = ((AVLNode<E>)grand).tallerChild();
    		Node<E> node = ((AVLNode<E>)parent).tallerChild();
    		if(parent == node.left){
    			if(node == parent.left){ //LL- 右旋
    				rightTurn(grand);
    			}else{ //LR -左有旋
    				lefTurn(parent);
    				rightTurn(grand);
    			}
    		}else{
    			if(node == parent.right){ //RR -左旋
    				lefTurn(grand);
    			}else{ //RL - 右左旋
    				rightTurn(parent);
    				lefTurn(grand);
    			}
    		}
    		updateHigh(grand);
    		updateHigh(parent);
    	}
    
    	private void rotate(
    			Node<E> r, // 子树的根节点
    			Node<E> b, Node<E> c,
    			Node<E> d,
    			Node<E> e, Node<E> f) {
    		// 让d成为这棵子树的根节点
    		d.parent = r.parent;
    		if (r.isLeftChild()) {
    			r.parent.left = d;
    		} else if (r.isRightChild()) {
    			r.parent.right = d;
    		} else {
    			root = d;
    		}
    
    		//b-c
    		b.right = c;
    		if (c != null) {
    			c.parent = b;
    		}
    		updateHigh(b);
    
    		// e-f
    		f.left = e;
    		if (e != null) {
    			e.parent = f;
    		}
    		updateHigh(f);
    
    		// b-d-f
    		d.left = b;
    		d.right = f;
    		b.parent = d;
    		f.parent = d;
    		updateHigh(d);
    	}
    
    	private void lefTurn(Node<E> grand) {
    		Node<E> parent = grand.right; //节点p
    		Node<E> child = parent.left; //子树T1
    		grand.right = child;
    		parent.left = grand;
    		//让p成为根节点
    		parent.parent = grand.parent;
    		if(grand == grand.parent.left){
    			grand.parent.left = parent;
    		}else if(grand == grand.parent.right){
    			grand.parent.right = parent;
    		}else{
    			root = parent;
    		}
    		if(child!=null){
    			child.parent = grand; //更新t1的parent
    		}
    		grand.parent = parent; //更新grand的parent
    	}
    
    
    	private void rightTurn(Node<E> grand) {
    		Node<E> parent = grand.left; //节点p
    		Node<E> child = parent.right; //子树T2
    		grand.left = child;
    		parent.right = grand;
    		//让p成为根节点
    		parent.parent = grand.parent;
    		if(grand == grand.parent.left){
    			grand.parent.left = parent;
    		}else if(grand == grand.parent.right){
    			grand.parent.right = parent;
    		}else{
    			root = parent;
    		}
    
    		//更新parent属性
    		if(child!=null){
    			child.parent = grand;
    		}
    		grand.parent = parent;
    
    	}
    
    
    	private void updateHigh(Node<E> node){
    		((AVLNode<E>)node).updateHeight();
    	}
    
    
    	/**
    	 *
    	 * @param node
    	 * @return
    	 */
    	private boolean isBalance(Node<E> node){
    		return Math.abs(getHigh(node)) <=1;
    	}
    
    	public int getHigh(Node<E> node){
    		if(node == null) return 0;
    		if(node.left==null && node.right == null) return 0;
    		int leftHigh = 0;
    		int rightHigh = 0;
    		if(node.left!=null){
    			leftHigh = getHigh(node.left);
    		}
    		if(node.right!=null){
    			rightHigh = getHigh(node.right);
    		}
    		return leftHigh - rightHigh;
    	}
    }
    
    package AVL树;
    
    import AVL树.printer.BinaryTreeInfo;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    
    @SuppressWarnings("unchecked")
    public class BinaryTree<E> implements BinaryTreeInfo {
    	protected int size;
    	protected Node<E> root;
    	
    	public int size() {
    		return size;
    	}
    
    	public boolean isEmpty() {
    		return size == 0;
    	}
    
    	public void clear() {
    		root = null;
    		size = 0;
    	}
    	
    	public void preorder(Visitor<E> visitor) {
    		if (visitor == null) return;
    		preorder(root, visitor);
    	}
    	
    	private void preorder(Node<E> node, Visitor<E> visitor) {
    		if (node == null || visitor.stop) return;
    		
    		visitor.stop = visitor.visit(node.element);
    		preorder(node.left, visitor);
    		preorder(node.right, visitor);
    	}
    	
    	public void inorder(Visitor<E> visitor) {
    		if (visitor == null) return;
    		inorder(root, visitor);
    	}
    	
    	private void inorder(Node<E> node, Visitor<E> visitor) {
    		if (node == null || visitor.stop) return;
    		
    		inorder(node.left, visitor);
    		if (visitor.stop) return;
    		visitor.stop = visitor.visit(node.element);
    		inorder(node.right, visitor);
    	}
    	
    	public void postorder(Visitor<E> visitor) {
    		if (visitor == null) return;
    		postorder(root, visitor);
    	}
    	
    	private void postorder(Node<E> node, Visitor<E> visitor) {
    		if (node == null || visitor.stop) return;
    		
    		postorder(node.left, visitor);
    		postorder(node.right, visitor);
    		if (visitor.stop) return;
    		visitor.stop = visitor.visit(node.element);
    	}
    	
    	public void levelOrder(Visitor<E> visitor) {
    		if (root == null || visitor == null) return;
    		
    		Queue<Node<E>> queue = new LinkedList<>();
    		queue.offer(root);
    		
    		while (!queue.isEmpty()) {
    			Node<E> node = queue.poll();
    			if (visitor.visit(node.element)) return;
    			
    			if (node.left != null) {
    				queue.offer(node.left);
    			}
    			
    			if (node.right != null) {
    				queue.offer(node.right);
    			}
    		}
    	}
    	
    	public boolean isComplete() {
    		if (root == null) return false;
    		Queue<Node<E>> queue = new LinkedList<>();
    		queue.offer(root);
    		
    		boolean leaf = false;
    		while (!queue.isEmpty()) {
    			Node<E> node = queue.poll();
    			if (leaf && !node.isLeaf()) return false;
    
    			if (node.left != null) {
    				queue.offer(node.left);
    			} else if (node.right != null) {
    				return false;
    			}
    			
    			if (node.right != null) {
    				queue.offer(node.right);
    			} else { // 后面遍历的节点都必须是叶子节点
    				leaf = true;
    			}
    		}
    		
    		return true;
    	}
    	
    	public int height() {
    		if (root == null) return 0;
    		
    		// 树的高度
    		int height = 0;
    		// 存储着每一层的元素数量
    		int levelSize = 1;
    		Queue<Node<E>> queue = new LinkedList<>();
    		queue.offer(root);
    		
    		while (!queue.isEmpty()) {
    			Node<E> node = queue.poll();
    			levelSize--;
    			
    			if (node.left != null) {
    				queue.offer(node.left);
    			}
    			
    			if (node.right != null) {
    				queue.offer(node.right);
    			}
    
    			if (levelSize == 0) { // 意味着即将要访问下一层
    				levelSize = queue.size();
    				height++;
    			}
    		}
    		
    		return height;
    	}
    	
    	public int height2() {
    		return height(root);
    	}
    	
    	private int height(Node<E> node) {
    		if (node == null) return 0;
    		return 1 + Math.max(height(node.left), height(node.right));
    	}
    	
    	protected Node<E> createNode(E element, Node<E> parent) {
    		return new Node<>(element, parent);
    	}
    
    	protected Node<E> predecessor(Node<E> node) {
    		if (node == null) return null;
    		
    		// 前驱节点在左子树当中(left.right.right.right....)
    		Node<E> p = node.left;
    		if (p != null) {
    			while (p.right != null) {
    				p = p.right;
    			}
    			return p;
    		}
    		
    		// 从父节点、祖父节点中寻找前驱节点
    		while (node.parent != null && node == node.parent.left) {
    			node = node.parent;
    		}
    
    		// node.parent == null
    		// node == node.parent.right
    		return node.parent;
    	}
    	
    	protected Node<E> successor(Node<E> node) {
    		if (node == null) return null;
    		
    		// 前驱节点在左子树当中(right.left.left.left....)
    		Node<E> p = node.right;
    		if (p != null) {
    			while (p.left != null) {
    				p = p.left;
    			}
    			return p;
    		}
    		
    		// 从父节点、祖父节点中寻找前驱节点
    		while (node.parent != null && node == node.parent.right) {
    			node = node.parent;
    		}
    
    		return node.parent;
    	}
    
    	public static abstract class Visitor<E> {
    		boolean stop;
    		/**
    		 * @return 如果返回true,就代表停止遍历
    		 */
    		abstract boolean visit(E element);
    	}
    	
    	protected static class Node<E> {
    		E element;
    		Node<E> left;
    		Node<E> right;
    		Node<E> parent;
    		public Node(E element, Node<E> parent) {
    			this.element = element;
    			this.parent = parent;
    		}
    		
    		public boolean isLeaf() {
    			return left == null && right == null;
    		}
    		
    		public boolean hasTwoChildren() {
    			return left != null && right != null;
    		}
    		
    		public boolean isLeftChild() {
    			return parent != null && this == parent.left;
    		}
    		
    		public boolean isRightChild() {
    			return parent != null && this == parent.right;
    		}
    		
    		public Node<E> sibling() {
    			if (isLeftChild()) {
    				return parent.right;
    			}
    			
    			if (isRightChild()) {
    				return parent.left;
    			}
    			
    			return null;
    		}
    	}
    
    	@Override
    	public Object root() {
    		return root;
    	}
    
    	@Override
    	public Object left(Object node) {
    		return ((Node<E>)node).left;
    	}
    
    	@Override
    	public Object right(Object node) {
    		return ((Node<E>)node).right;
    	}
    
    	@Override
    	public Object string(Object node) {
    		return node;
    	}
    }
    
    package AVL树;
    
    import java.util.Comparator;
    
    @SuppressWarnings("unchecked")
    public class BST<E> extends BinaryTree<E> {
    	private Comparator<E> comparator;
    	
    	public BST() {
    		this(null);
    	}
    	
    	public BST(Comparator<E> comparator) {
    		this.comparator = comparator;
    	}
    
    	public void add(E element) {
    		elementNotNullCheck(element);
    		
    		// 添加第一个节点
    		if (root == null) {
    			root = createNode(element, null);
    			size++;
    
    			// 新添加节点之后的处理
    			balanceTree(root);
    			return;
    		}
    		
    		// 添加的不是第一个节点
    		// 找到父节点
    		Node<E> parent = root;
    		Node<E> node = root;
    		int cmp = 0;
    		do {
    			cmp = compare(element, node.element);
    			parent = node;
    			if (cmp > 0) {
    				node = node.right;
    			} else if (cmp < 0) {
    				node = node.left;
    			} else { // 相等
    				node.element = element;
    				return;
    			}
    		} while (node != null);
    
    		// 看看插入到父节点的哪个位置
    		Node<E> newNode = createNode(element, parent);
    		if (cmp > 0) {
    			parent.right = newNode;
    		} else {
    			parent.left = newNode;
    		}
    		size++;
    		
    		// 新添加节点之后的处理
    		balanceTree(newNode);
    	}
    	
    	/**
    	 * 添加node之后的调整
    	 * @param node 新添加的节点
    	 */
    	protected void balanceTree(Node<E> node) { }
    	
    	/**
    	 * 删除node之后的调整
    	 * @param node 被删除的节点
    	 */
    	protected void afterRemove(Node<E> node) { }
    
    	public void remove(E element) {
    		remove(node(element));
    	}
    
    	public boolean contains(E element) {
    		return node(element) != null;
    	}
    	
    	private void remove(Node<E> node) {
    		if (node == null) return;
    		
    		size--;
    		
    		if (node.hasTwoChildren()) { // 度为2的节点
    			// 找到后继节点
    			Node<E> s = successor(node);
    			// 用后继节点的值覆盖度为2的节点的值
    			node.element = s.element;
    			// 删除后继节点
    			node = s;
    		}
    		
    		// 删除node节点(node的度必然是1或者0)
    		Node<E> replacement = node.left != null ? node.left : node.right;
    		
    		if (replacement != null) { // node是度为1的节点
    			// 更改parent
    			replacement.parent = node.parent;
    			// 更改parent的left、right的指向
    			if (node.parent == null) { // node是度为1的节点并且是根节点
    				root = replacement;
    			} else if (node == node.parent.left) {
    				node.parent.left = replacement;
    			} else { // node == node.parent.right
    				node.parent.right = replacement;
    			}
    			
    			// 删除节点之后的处理
    			afterRemove(node);
    		} else if (node.parent == null) { // node是叶子节点并且是根节点
    			root = null;
    			
    			// 删除节点之后的处理
    			afterRemove(node);
    		} else { // node是叶子节点,但不是根节点
    			if (node == node.parent.left) {
    				node.parent.left = null;
    			} else { // node == node.parent.right
    				node.parent.right = null;
    			}
    			
    			// 删除节点之后的处理
    			afterRemove(node);
    		}
    	}
    	
    	private Node<E> node(E element) {
    		Node<E> node = root;
    		while (node != null) {
    			int cmp = compare(element, node.element);
    			if (cmp == 0) return node;
    			if (cmp > 0) {
    				node = node.right;
    			} else { // cmp < 0
    				node = node.left;
    			}
    		}
    		return null;
    	}
    	
    	/**
    	 * @return 返回值等于0,代表e1和e2相等;返回值大于0,代表e1大于e2;返回值小于于0,代表e1小于e2
    	 */
    	private int compare(E e1, E e2) {
    		if (comparator != null) {
    			return comparator.compare(e1, e2);
    		}
    		return ((Comparable<E>)e1).compareTo(e2);
    	}
    	
    	private void elementNotNullCheck(E element) {
    		if (element == null) {
    			throw new IllegalArgumentException("element must not be null");
    		}
    	}
    }
    

     

    更多相关内容
  • 数据结构之AVL树详解

    2020-12-26 05:31:33
    AVL树是最早提出的自平衡二叉树,在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis。AVL树种查找、插入和删除在平均和最坏情况下...
  • 之前只写了一些AVL树核心算法,这里给出一个AVL树的完整实现。 AVL树是平衡查找二叉树,不仅能避免二叉搜索树出现斜树的状况,更是能保持比较标准的O(log2N),但AVL树可能需要很多次的各种调整: 左儿子单旋转 左...
  • 在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者...
  • 二叉查找树,AVL树

    2021-01-07 10:28:17
    AVL树(平衡二叉查找树) 具有二叉查找树的全部特性。 每个节点的左子树的高度和右子树高度差值小于等于1(平衡二叉树的性质) 左旋:逆时针旋转两个节点,原先的右节点成为新的父节点,原先的父节点成为原先的右...
  • AVL树及JAVA实现

    2019-04-14 01:03:32
    NULL 博文链接:https://128kj.iteye.com/blog/1735464
  • AVL树Java中的AVL树实现有两个基本操作,使用这些操作树本身会保持平衡。 左旋转。 右旋。 然后将有四种可能性左-左情况:— x是y的左子代,y是z的左子代。 左右案例:— x是y的右子代,y是z的左子代。 左右案例:—...
  • avl_tree AVL树的python实现(自平衡二叉树) 描述: 这是具有以下外部方法的平衡二叉搜索树的实现: insert (data) 将数据插入树中,如果它尚未包含在树中insertList (list)通过迭代调用insert将list中的数据元素...
  • AVLTree_in_Java 用作键值集的AVL树描述:AVL树用作键值集作者:张玲涵电子邮件: 执照:GNU / GPL 注意:初始化AVLTree时,应指定键类型和值类型,例如new AVLTree (Comparator),该键必须是唯一的。 您需要定义...
  • AVL树的C语言实现

    2016-11-30 13:07:49
    AVL树的C语言实现
  • AVL树的判定问题.rar

    2020-07-01 15:09:25
    AVL 是一种平衡二叉搜索AVL 有一个特点,所有节点的平衡因子不能大于 1,即所有节点的左子树与右子的深度差只能为-1,0,1。根据这个概念,判断 AVL 就是去判断一棵二叉树是否是二叉搜索,并且是否...
  • java笔试题算法AVL 的实现,以及测试上插入的代码。 基于 Mark Allen Weiss 在其著作Data Structures and Algorithm Analysis in Java 中编写的代码。
  • AVL树详解

    多人点赞 热门讨论 2022-02-12 11:33:53
    目录AVL树的概念AVL树节点的定义AVL树如何高度平衡?右单旋左单旋左右双旋 AVL树的概念 二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,...

    AVL树的概念

    二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。 因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整), 即可降低树的高度,从而减少平均搜索长度。
    AVL树是具有以下性质的二叉搜索树:

    • 它的左右子树都是AVL树
    • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
      如下图是一棵AVL树:
      在这里插入图片描述

    如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在O( log ⁡ 2 N \log_2N log2N) ,搜索时间复杂度O( log ⁡ 2 N \log_2N log2N) )。

    AVL树节点的定义

    template<class K, class V>
    struct AVLTreeNode
    {
    	AVLTreeNode<K, V>* _left;	// 该节点的左孩子
    	AVLTreeNode<K, V>* _right;	// 该节点的右孩子
    	AVLTreeNode<K, V>* _parent;		// 该节点的双亲
    
    	pair<K, V> _kv;		// 存储数据的键值对
    	int _bf;			// 平衡因子(balance factor)
    	AVLTreeNode(const pair<K, V>& kv)
    		:_left(nullptr)
    		, _right(nullptr)
    		, _parent(nullptr)
    		, _kv(kv)
    		, _bf(0)
    	{}
    };
    

    每个节点平衡因子的计算为其右子树的高度减去左子树的高度。
    一个新节点既没有左子树也没有右子树,可以将它左右子树高度看作0,所以在构造函数中将新节点的平衡因子_bf初始化为0。

    AVL树如何高度平衡?

    AVL树是高度平衡的二叉搜索树,其左右子树高度之差不超过一。通过平衡因子_bf来记录左右子树的高度差,也就是说每个节点的平衡因子只有三种取值(-1/0/1),平衡因子的计算为右子树的高度减去左子树的高度,平衡因子为-1说明左子树比右子树高1,0说明左右子树一样高,1说明右子树比左子树高1。
    当平衡因子的高度更新为2或-2时,说明左右子树的高度差为2,此时AVL树不再平衡,那么如何控制它平衡呢?
    通过以下四种旋转

    右单旋

    新节点插入较高左子树的左侧:右单旋
    下面是抽象图:
    在这里插入图片描述
    在插入前,AVL树是平衡的,新节点插入到30的左子树中,30左子树增加了一层,导致以60为根的二叉树不平衡,通过右单旋使AVL树重新达到平衡。
    将30的右子树作60的左子树,再将60作为30的右子树,这样就完成了右单旋。根据二叉搜索树的性质,30的右子树subLR都比30大,而subLR都比60小,所以先让subLR作60的左子树,再让60作30的右子树不会违反二叉搜索树的性质。
    在旋转完成后更新节点的平衡因子即可。新插入的节点只会影响它父节点的平衡因子,以及它父节点的父节点的平衡因子…,此图中平衡因子受影响的节点为subL和parent,右单旋旋转完成后,parent的左右子树高度相同,subL的左右子树高度相同,它们的平衡因子都被改为0。
    在旋转过程中,有以下几种情况需要考虑:
    1.30节点的右孩子可能存在,也可能不存在
    2. 60可能是根节点,也可能是子树
    如果是根节点,旋转完成后,要更新根节点
    如果是子树,可能是某个节点的左子树,也可能是右子树
    需要更新30的父节点保证树的结构不会被破坏
    右单旋具象图:
    在AVL树中新插入节点5,AVL树不再平衡,通过右单旋使AVL树重新达到平衡。
    在这里插入图片描述
    右单旋代码:
    由于节点采用三叉链结构,所以也要更改_parent指针。

    void RotateR(Node* parent)
    {
    	Node* subL = parent->_left;		// 父节点左孩子
    	Node* subLR = subL->_right;		// 父节点左孩子的右孩子
    	parent->_left = subLR;
    	if (subLR)	// subRL可能为空
    		subLR->_parent = parent;
    	subL->_right = parent;
    	Node* parentParent = parent->_parent;
    	parent->_parent = subL;
    	if (parent == _root)	// 父节点为空节点
    	{
    		_root = subL;
    		_root->_parent = nullptr;
    	}
    	else			// 父节点不是空节点
    	{
    		if (parentParent->_left == parent)
    			parentParent->_left = subL;
    		else
    			parentParent->_right = subL;
    		subL->_parent = parentParent;
    	}
    	subL->_bf = parent->_bf = 0;	// 更新平衡因子
    }
    

    左单旋

    新节点插入较高右子树的右侧:左单旋
    左单旋抽象图:
    在这里插入图片描述
    左单旋的旋转可以参考右单旋,将subRL作为30的右子树,再将30作为60的左子树。
    30右子树都比30大,所以subRL可以做30的右子树,subRL和30以及30的左子树都比30小,可以做60的左子树,这样旋转不会违反二叉搜索树的性质。
    蓝色的新增节点会影响subR和parent的平衡因子,左单旋AVL树平衡后,subR和parent的左右子树高度相同,它们的平衡因子改为0。
    仍然需要注意的是subRL可能为空,parent可能为根节点,也可能不是根节点,在实现代码时要考虑以上情况。
    左单旋具象图:
    在AVL树中新插入节点90,AVL树不再平衡,通过右单旋使AVL树重新达到平衡。
    在这里插入图片描述
    左单旋代码:

    void RotateL(Node* parent)
    {
    	Node* subR = parent->_right;	// 父节点的右孩子
    	Node* subRL = subR->_left;		// 父节点右孩子的左孩子
    	parent->_right = subRL;
    	if (subRL)		// subRL可能为空
    		subRL->_parent = parent;
    	subR->_left = parent;
    	Node* parentParent = parent->_parent;
    	parent->_parent = subR;
    	if (parent == _root)	// 父亲是根节点
    	{
    		_root = subR;
    		_root->_parent = nullptr;
    	}
    	else		// 父亲不是根节点
    	{
    		if (parentParent->_left == parent)
    			parentParent->_left = subR;
    		else
    			parentParent->_right = subR;
    		subR->_parent = parentParent;
    	}
    	// 更新平衡因子
    	subR->_bf = parent->_bf = 0;
    }
    

    左右双旋

    新节点插入较高左子树的右侧:先左单旋再右单旋
    左右双旋抽象图:
    在这里插入图片描述

    新增节点在60的左子树上,将双旋变成单旋后再旋转,即:先对30进行左单旋,然后再对90进行右单旋,,简单来说就是60的左子树做30的右子树,60的右子树做90的左子树,然后30和90做60的左右子树,60成为树的根。
    此时平衡因子的更新分为三种情况:
    第一种情况就是上图新增节点在60的左子树,60的平衡因子变为-1,此时60的左子树比右子树高1,把60高的左子树做30的右子树,30左右子树高度相同,平衡因子更新为0,把60低的右子树做90的左子树,90的平衡因子为h - (h - 1),平衡因子为1,把30和90分别作为60的左右子树,此时60的左右子树高度相同,60的平衡因子更新为0。
    第二种情况新增节点在60的右子树,
    在这里插入图片描述
    60的平衡因子变为1,此时60的右子树比左子树高1,把60低的左子树做30的右子树,30的平衡因子更新为(h - 1) - h 为-1,把60高的右子树作为90的左子树,90的平衡因子更新为h - h = 0,60为新的根节点,其左右子树高度相同,平衡因子更新为0。
    第三种情况60就是新增节点
    在这里插入图片描述
    此时三个节点的平衡因子都为0。
    左右双旋代码:

    void RotateLR(Node* parent)
    {
    	Node* subL = parent->_left;
    	Node* subLR = subL->_right;
    	int bf = subLR->_bf;
    	RotateL(parent->_left);		// 以父亲的左孩子为根左单旋
    	RotateR(parent);        // 以父亲为根右单旋
    	// 更新平衡因子,分别对应上面的三种情况
    	if (bf == 1)		
    	{
    		subL->_bf = -1;
    		parent->_bf = 0;
    		subLR->_bf = 0;
    	}
    	else if (bf == -1)
    	{
    		subLR->_bf = 0;
    		parent->_bf = 1;
    		subLR->_bf = 0;
    	}
    	else if (bf == 0)
    	{
    		subL->_bf = 0;
    		parent->_bf = 0;
    		subLR->_bf = 0;
    	}
    	else
    	{
    		// 平衡因子出错
    		assert(false);
    	}
    }
    

    右左双旋

    新节点插入较高右子树的左侧:先右单旋再左单旋
    右左双旋抽象图:
    在这里插入图片描述

    将双旋变成单旋后再旋转,即:先对90进行右单旋,然后再对30进行左单旋,旋转完成后再考虑平衡因子的更新。
    右左双旋也分为三种情况:
    第一种情况如上如图新增节点在60的右子树,此时60的平衡因子为1。旋转完成后30的平衡因子变为(h - 1) - h,为-1,90的平衡因子变为h - h 为0,60的平衡因子为(h + 1) - (h + 1)为0。
    第二种情况新增节点在60的左子树
    在这里插入图片描述
    此时新增节点在60的左子树,60的左子树比右子树高1,60的平衡因子为-1,把60的左子树做30的右子树,30的平衡因子变为h - h为0,60的右子树做90的左子树,90的平衡因子更新为h - (h - 1)为1,60的左右子树高度相等,平衡因子更新为0。
    第三种情况60就是新增节点
    在这里插入图片描述
    此时三个节点左右子树高度都相同,平衡因子都为0。
    右左双旋代码:

    void RotateRL(Node* parent)
    {
    	Node* subR = parent->_right;	// 父节点的右孩子
    	Node* subRL = subR->_left;	//父节点右孩子的左孩子
    	int bf = subRL->_bf;	
    	RotateR(parent->_right);	// 以父亲的右子树为根右旋
    	RotateL(parent);		// 以父节点为根左旋
    	// 三种情况更新平衡因子
    	if (bf == 1)
    	{
    		subR->_bf = 0;
    		parent->_bf = -1;
    		subRL->_bf = 0;
    	}
    	else if (bf == -1)
    	{
    		subR->_bf = 1;
    		parent->_bf = 0;
    		subRL->_bf = 0;
    	}
    	else if(bf == 0)
    	{
    		subR->_bf = 0;
    		parent->_bf = 0;
    		subRL->_bf = 0;
    	}
    	else
    	{
    		// 平衡因子出错
    		assert(false);
    	}
    }
    

    当AVL树不平衡时通过以上四种旋转,使AVL树保持平衡。

    AVL树的插入

    先找到应插入节点的位置,插入后更新平衡因子,如果不平衡了通过旋转使AVL树重新平衡。
    插入控制平衡更新原则
    1.新增节点在parent右边,parent->bf++
    2.新增节点在parent左边,parent->bf- -
    a.如果parent的平衡因子等于1 or -1 继续往上更新 // 说明parent所在子树的高度变了
    b.如果parent的平衡因子等于0 停止更新 // 高度不变
    c.如果parent的平衡因子等于2 or -2 已经出现不平衡,需要旋转处理
    AVL树插入节点代码:

    bool Insert(const pair<K, V>& kv)
    {
    	if (_root == nullptr)
    	{
    		_root = new Node(kv);
    		return true;
    	}
    	Node* parent = nullptr;
    	Node* cur = _root;
    	while (cur)		// 找到应插入节点的位置
    	{
    		if (cur->_kv.first < kv.first)
    		{
    			parent = cur;
    			cur = cur->_right;
    		}
    		else if (cur->_kv.first > kv.first)
    		{
    			parent = cur;
    			cur = cur->_left;
    		}
    		else
    		{
    			return false;
    		}
    	}
    	cur = new Node(kv);
    	if (parent->_kv.first < kv.first)
    	{
    		parent->_right = cur;
    		cur->_parent = parent;
    	}
    	else
    	{
    		parent->_left = cur;
    		cur->_parent = parent;
    	}
    	// 控制平衡
    	while (cur != _root)
    	{
    		if (cur == parent->_right)
    		{
    			parent->_bf++;
    		}
    		else
    		{
    			parent->_bf--;
    		}
    		if (parent->_bf == 0)
    		{
    			break;
    		}
    		else if (parent->_bf == 1 || parent->_bf == -1)
    		{
    			// parent所在的子树高度变了,会影响parent->parent
    			// 继续往上更新
    			cur = parent;
    			parent = parent->_parent;
               }
    		else if (parent->_bf == 2 || parent->_bf == -2)
    		{
    			// parent所在子树已经不平衡,需要旋转处理
    			if (parent->_bf == -2)
    			{
    				if (cur->_bf == -1)
    				{
    					RotateR(parent);	// 右单旋
    				}
    				else    // cur->_bf == 1
    				{
    					RotateLR(parent);	// 左右双旋
    				}
    			}
    			else    // parent->_bf == 2
    			{
    				if (cur->_bf == 1)
    				{
    					RotateL(parent);	// 左单旋
    				}
    				else    // cur->_bf == -1
    				{
    					RotateRL(parent);	// 右左双旋
    				}
    			}
    			break;
    		}
    		else
    		{
    			// 插入节点之前,树已经不平衡了,或者bf出错,需要检查其他逻辑
    			assert(false);
    		}
    	}
    	return true;
    }
    

    AVL树的查找

    根据二叉搜索树的性质进行查找

    Node* Find(const K& key)
    {
    	Node* cur = _root;
    	while (cur)
    	{
    		if (cur->_kv.first < key)
    			cur = cur->_right;
    		else if (cur->_kv.first > key)
    			cur = cur->_left;
    		else
    			return cur;
    	}
    	return nullptr;
    }
    

    AVL树的性能

    AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这样可以保证查询时高效的时间复杂度,即 log ⁡ 2 N \log_2N log2N 。但是如果要对AVL树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。因此:如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑AVL树,但一个结构经常修改,就不太适合。

    展开全文
  • 潜析AVL树AVL树的双旋转 接上篇博文:简析AVL树AVL树的概念及单旋转 AVL树如何恢复平衡之双旋转 首先假设我们有一颗已经处于平衡的AVL树: 上篇博文已经解决了LL和RR两种情况的平衡恢复解决方案—-单旋转。这篇...
  • 作为我的数据结构和算法课程的一部分,我参与了 AVL 的实现。
  • avl_file是一个库,用于基于文件的线程AVL树(高度平衡的二叉树),具有多个键和并发访问权限,并在单个文件中使用固定长度的记录。
  • 二叉树之AVL树

    2022-03-09 22:15:38
    今天来细说下 AVL 树,并结合图示代码来认识并掌握 AVL 树的创建,删除,体会下 AVL 特有的自...与二叉树不同的是,AVL树是一颗平衡树: 节点 root,左子节点的高度 与 右子节点的高度,最大差值 = 1 下面看看 AV

    今天来细说下 AVL 树,并结合图示代码来认识并掌握 AVL 树的创建,删除,体会下 AVL 特有的自平衡性。

    目录:

    AVL 概念

    AVL 的旋转

    AVL 树旋转实现

    AVL 树代码实现(C语言)

    测试实例

    AVL 概念

    AVL 也是二叉树的一种,所以符合所有二叉树应有的特性,以及遍历方法

    与二叉树不同的是,AVL树是一颗平衡树:

    节点 root,左子节点的高度 与 右子节点的高度,最大差值 = 1

    下面看看 AVL 树的示例:

    理论上来讲 root 节点深度 = 1,依次增加,这里相反是因为后续代码初始节点深度 = 1

     再来看看 非 AVL 树的示例,把上图的节点 6 去掉

    可见针对 节点 5 来讲,左子树深度=3, 右子树深度=1,已经超过最大深度 1,所以不是 AVL 树

    AVL 树的旋转

    我们在操作树一定发生:添加或者删除节点,AVL 的状态可能会被破坏,基于不同形态的 非 AVL 树,我们有以下 四种姿态 需要通过旋转重回 AVL 形态

    如果把AVL树(平衡树)看做一个人,左右子节点就是左右手提的东西

    左手重或者右手重就会失去平衡,失去平衡的原因就是姿态

    比如:LR,左子节点深度过大,且是因为左子节点下的右子节点(多余)造成的

    形态一:LL 树 (Left-Left)

    节点 6 的左右不平衡,原因是

    1. Left 节点 4 更重

    2.  造成节点 4 更重的原因是 4 的 Left 节点 3 还有子节点

    形态二:RR 树 (Right-Right)

    节点 3 的左右不平衡,原因是

    1. Right 节点 6 更重

    2.  造成节点 6 更重的原因是 8 的 Right 节点 8 还有子节点

    形态三:LR 树 (Left-Right)

    节点 8 的左右不平衡,原因是

    1. Left 节点 4 更重

    2.  造成节点 4 更重的原因是 4 的 Right 节点 5 还有子节点

    形态四:RL 树 (Right-Left)

    节点 3 的左右不平衡,原因是

    1. Right 节点 8 更重

    2.  造成节点 8 更重的原因是 8 的 Left 节点 5 还有子节点

    AVL 树旋转实现

    形态一:LL 树旋转 

    既然左手 K1 重了,那么左手 K1 就当脑袋,脑壳 K2 顺势变成右手,这样占用了 新脑袋的右手,原本 K1 的右手就只能丢给 K2 的左手

    /* LL Rotation AVL Tree 
    ** Parameters:
    **		root - avl tree
    **
    		k2						k1
    	k1		c	-LL->		a		k2
      a    b				  d	       b   c
    d  
    */
    PNode ll_rotation(PNode k2)
    {
    	PNode k1;
    	
    	k1 = k2->left;
    	k2->left = k1->right;
    	k1->right = k2;
    	
    	k2->deep = MAX( DEEP(k2->left), DEEP(k2->right) ) + 1;
    	k1->deep = MAX( DEEP(k1->left), k2->deep ) + 1;
    	
    	return k1;
    }

    形态二:RR 树旋转  

     既然右手 K2 重了,那么右手 K2 就当脑袋,脑壳 K1 顺势变成左手,这样占用了 新脑袋的左手,原本 K2 的左手就只能丢给 K1 的右手

    /* RR Rotation AVL Tree 
    ** Parameters:
    **		root - avl tree
    **
    		k1						k2
    	a		k2	 -RR->		k1		c
    		  b    c		  a   b		  d
    				 d
    */
    PNode rr_rotation(PNode k1)
    {
    	PNode k2;
    	
    	k2 = k1->right;
    	k1->right = k2->left;
    	k2->left = k1;
    	
    	k1->deep = MAX( DEEP(k1->left), DEEP(k1->right) ) + 1;
    	k2->deep = MAX( DEEP(k2->right), k1->deep ) + 1;
    	
    	return k2;
    }

    形态三:LR 树旋转

    需经过两次变化,RR + LL ,按照右到左(LR)名字

    /* LR Rotation AVL Tree 
    ** Parameters:
    **		root - avl tree
    **
    		k3						k3						k2
    	k1		d	--RR->		k2		d		--LL->	 k1     k3
      a	  k2				  k1   c				   a   b   c   d
         b  c				a    b
    */
    PNode lr_rotation(PNode k3)
    {
    	PNode k1, k2;
    	
    	k1 = k3->left;
    	k2 = rr_rotation(k1);
    	k3->left = k2;
    	
    	k2 = ll_rotation(k3);
    	
    	return k2;
    }

    形态四:RL 树旋转

     需经过两次变化,LL+RR ,按照右到左(RL)名字

    /* LR Rotation AVL Tree 
    ** Parameters:
    **		root - avl tree
    **
    		k3						k3						k2
    	k1		d	--RR->		k2		d		--LL->	 k1     k3
      a	  k2				  k1   c				   a   b   c   d
         b  c				a    b
    */
    PNode lr_rotation(PNode k3)
    {
    	PNode k1, k2;
    	
    	k1 = k3->left;
    	k2 = rr_rotation(k1);
    	k3->left = k2;
    	
    	k2 = ll_rotation(k3);
    	
    	return k2;
    }

    AVL 树代码实现

    有个限定:

    1. 左子节点值 < root 节点值 < 右子节点值

    2. 不存在相同节点值

    数据结构

    typedef struct AVLTreeNode{
    	int val;
    	int deep;
    	struct AVLTreeNode *left;
    	struct AVLTreeNode *right;
    }Node, *PNode;

     获取树深

    #define DEEP(node) ( node == NULL ? 0 : node->deep )
    
    /* Get AVL Tree's Deep
    ** Parameters:
    **		root - avl tree
    ** Note: Deep incream from leaf(1) to root
    **
    */
    int avltree_get_deep(PNode root)
    {
    	return DEEP(root);
    }

    获取树的最小值的节点

    /* Get AVL Tree's Minimum Val Node
    ** Parameters:
    **		root - avl tree
    */
    PNode avltree_get_min(PNode root)
    {
    	if(root == NULL)
    		return NULL;
    	
    	while(root->left)
    		root = root->left;
    	
    	return root;
    }

     获取树的最大值的节点 

    /* Get AVL Tree's Minimum Val Node
    ** Parameters:
    **		root - avl tree
    */
    PNode avltree_get_min(PNode root)
    {
    	if(root == NULL)
    		return NULL;
    	
    	while(root->left)
    		root = root->left;
    	
    	return root;
    }

     创建树的节点

    /* Create AVL Tree Node
    ** Parameters:
    **		val - val
    **		left - left child
    **		right - right child
    */
    PNode avltree_create_node(int val, PNode left, PNode right)
    {
    	PNode newNode = (PNode)malloc(sizeof(Node));
    	if(newNode == NULL)
    		return NULL;
    	
    	newNode->val = val;
    	newNode->deep = 1;
    	newNode->left = left;
    	newNode->right = right;
    	
    	return newNode;
    }

    查找树的节点 

    /* Search Node of AVL Tree
    ** Parameters:
    **		root - avl tree
    **		val - node's val
    */
    PNode avltree_search_node(PNode root, int val)
    {
    	if(root == NULL || root->val == val)
    		return root;
    		
    	if(val < root->val)
    		return avltree_search_node(root->left, val);
    	else
    		return avltree_search_node(root->right, val);
    }

     插入节点到树,如果没有根节点则创建根节点

    /* Insert New Node to AVL Tree
    ** Parameters:
    **		root - avl tree
    **		val - node to insert
    */
    PNode avltree_insert_node(PNode root, int val)
    {
    	if(root == NULL)	
    	{
    		root = avltree_create_node(val, NULL, NULL);
    		if(root == NULL)
    			return NULL;
    	}
    	else if(val < root->val)
    	{
    		root->left = avltree_insert_node(root->left, val);
    		
    		if( ( DEEP(root->left) - DEEP(root->right) ) == 2 )
    		{
    			if(val < root->left->val)
    			{
    				printf("do ll...val=%d\n", val);
    				root = ll_rotation(root);
    			}
    			else
    			{
    				printf("do lr...val=%d\n", val);
    				root = lr_rotation(root);
    			}
    		}
    	}
    	else if(val > root->val)
    	{
    		root->right = avltree_insert_node(root->right, val);
    		
    		if( ( DEEP(root->right) - DEEP(root->left) ) == 2 )
    		{
    			if(val > root->right->val)
    			{
    				printf("do rr...val=%d\n", val);
    				root = rr_rotation(root);
    			}
    			else
    			{
    				printf("do rl...val=%d\n", val);
    				root = rl_rotation(root);
    			}
    		}
    	}
    	else
    		printf("insert %d fails, val exsits.\n", val);
    	
    	root->deep = MAX( DEEP(root->left), DEEP(root->right) ) + 1;
    	
    	return root;
    }

     删除指定值得节点

    /* Delete Node of AVL Tree
    ** Parameters:
    **		root - avl tree
    **		val - node's val
    */
    PNode avltree_delete_node_by_val(PNode root, int val)
    {
    	PNode node;
    	
    	node = avltree_search_node(root, val);
    	
    	if(node)
    	{
    		printf("find node, val=%d\n", node->val); 
    		avltree_delete_node(root, node);
    	}
    	else
    		printf("not find val:%d\n", val);
    		 
    	return root;
    }

     删除指定节点

    /* Delete Node of AVL Tree
    ** Parameters:
    **		root - avl tree
    **		node - node to delete
    */
    PNode avltree_delete_node(PNode root, PNode node)
    {
    	if(root == NULL || node == NULL)
    		return NULL;
    		
    	if(node->val < root->val)	// left side
    	{
    		root->left = avltree_delete_node(root->left, node);
    		if(DEEP(root->right) - DEEP(root->left) == 2)
    		{
    			PNode r = root->right;
    			if(DEEP(r->left) > DEEP(r->right))
    				root = rl_rotation(root);
    			else
    				root = rr_rotation(root);
    		}
    	}
    	else if(node->val > root->val) // right side
    	{
    		root->right = avltree_delete_node(root->right, node);
    		if(DEEP(root->left) - DEEP(root->right) == 2)
    		{
    			PNode l = root->left;
    			if(DEEP(l->left) > DEEP(l->right))
    				root = ll_rotation(root);
    			else
    				root = lr_rotation(root);
    		}
    	}
    	else // find
    	{
    		if(root->left && root->right)
    		{
    			if(DEEP(root->left) > DEEP(root->right))
    			{
    				// 1. find max node in left side
    				// 2. set max node val to root
    				// 3. delete max node
    				PNode maxNode = avltree_get_max(root->left);
    				root->val = maxNode->val;
    				root->left = avltree_delete_node(root->left, maxNode);
    			}
    			else
    			{
    				// 1. find min node in right side
    				// 2. set min node val to root
    				// 3. delete min node
    				PNode minNode = avltree_get_min(root->right);
    				root->val = minNode->val;
    				root->right = avltree_delete_node(root->right, minNode);
    			}
    		}
    		else
    		{
    			PNode tmp = root;
    			root = root->left ? root->left : root->right;
    			free(tmp);
    		}
    	}
    	
    	return root;
    }

    销毁树 

    /* Destory AVL Tree
    ** Parameters:
    **		root - avl tree
    */
    void avltree_destory(PNode root)
    {
    	if(root == NULL)
    		return;
    	
    	if(root->left)
    		avltree_destory(root->left);
    	if(root->right)
    		avltree_destory(root->right);
    	
    	printf("free %d\n", root->val);
    	free(root);
    }

    测试实例

    int main(void)
    {
    	int i;
    	int len;
    	int nodes[] ={3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9};
    	len = sizeof(nodes) / sizeof(nodes[0]);
    	
    	PNode root = NULL;
    	for(i=0; i<len; i++)
    	{
    		root = avltree_insert_node(root, nodes[i]);
    	}
    	
    	printf("\npreorder:\n");
    	preorder(root);
    	
    	printf("\ninorder:\n");
    	inorder(root);
    	
    	printf("\npreorder:\n");
    	postorder(root);
    	
    	printf("\nroot's deep: %d\n", DEEP(root));
    	printf("\nminimum: %d\n", avltree_get_min(root)->val);
    	printf("\nmaxmum: %d\n", avltree_get_max(root)->val);
    
    	printf("-----------delete node start-------\n");
    	avltree_delete_node_by_val(root, 12);
    	printf("\npreorder:\n");
    	preorder(root);
    	printf("\n");
    	
    	avltree_delete_node_by_val(root, 2);
    	printf("\npreorder:\n");
    	preorder(root);
    	printf("\n");
    	
    	printf("-----------delete node end-------\n");
    	
    	
    	printf("\ndesotry avl tree\n");
    	avltree_destory(root);
    	
    	return 0;
    }

    构建完成的树:

     

     执行结果:

    do ll...val=1
    do rr...val=5
    do rr...val=6
    do rr...val=7
    do rl...val=15
    do rl...val=14
    do rr...val=13
    do ll...val=12
    do ll...val=11
    do ll...val=10
    do lr...val=9
    
    preorder:
    val=7, deep=5
    val=4, deep=3
    val=2, deep=2
    val=1, deep=1
    val=3, deep=1
    val=6, deep=2
    val=5, deep=1
    val=13, deep=4
    val=11, deep=3
    val=9, deep=2
    val=8, deep=1
    val=10, deep=1
    val=12, deep=1
    val=15, deep=2
    val=14, deep=1
    val=16, deep=1
    
    inorder:
    val=1, deep=1
    val=2, deep=2
    val=3, deep=1
    val=4, deep=3
    val=5, deep=1
    val=6, deep=2
    val=7, deep=5
    val=8, deep=1
    val=9, deep=2
    val=10, deep=1
    val=11, deep=3
    val=12, deep=1
    val=13, deep=4
    val=14, deep=1
    val=15, deep=2
    val=16, deep=1
    
    preorder:
    val=1, deep=1
    val=3, deep=1
    val=2, deep=2
    val=5, deep=1
    val=6, deep=2
    val=4, deep=3
    val=8, deep=1
    val=10, deep=1
    val=9, deep=2
    val=12, deep=1
    val=11, deep=3
    val=14, deep=1
    val=16, deep=1
    val=15, deep=2
    val=13, deep=4
    val=7, deep=5
    
    root's deep: 5
    
    minimum: 1
    
    maxmum: 16
    -----------delete node start-------
    find node, val=12
    
    preorder:
    val=7, deep=5
    val=4, deep=3
    val=2, deep=2
    val=1, deep=1
    val=3, deep=1
    val=6, deep=2
    val=5, deep=1
    val=13, deep=4
    val=10, deep=3
    val=9, deep=2
    val=8, deep=1
    val=11, deep=1
    val=15, deep=2
    val=14, deep=1
    val=16, deep=1
    
    find node, val=2
    
    preorder:
    val=7, deep=5
    val=4, deep=3
    val=3, deep=2
    val=1, deep=1
    val=6, deep=2
    val=5, deep=1
    val=13, deep=4
    val=10, deep=3
    val=9, deep=2
    val=8, deep=1
    val=11, deep=1
    val=15, deep=2
    val=14, deep=1
    val=16, deep=1
    
    -----------delete node end-------
    
    desotry avl tree
    free 1
    free 3
    free 5
    free 6
    free 4
    free 8
    free 9
    free 11
    free 10
    free 14
    free 16
    free 15
    free 13
    free 7

    小结

    总算是描述完成(其实还没有,依据示例进行构建的过程留给用心的朋友自行画图,看看结果是否符合预期,这样才能加深 AVL 几种姿态的转变的理解),对照代码和图示应该对 AVL 树有了新的认识

    早期在工作项目中有看到基于 AVL 树的实现,当时一头雾水,现在是时候重温了

    更多数据结构详解

    展开全文
  • C++实现AVL树

    千次阅读 多人点赞 2022-01-02 13:37:12
    目录AVL树的概念AVL树的插入AVL树的四种旋转右单旋左单旋左右双旋右左双旋查找其他接口析构函数拷贝构造拷贝赋值 AVL树的概念 二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,...

    在这里插入图片描述

    AVL树的概念

    二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。

    一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:

    1. 它的左右子树都是AVL树
    2. 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
    3. 平衡因子的计算是右子树的高度减去左子树的高度的差值结果
      在这里插入图片描述

    如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在O(log N) ,搜索时间复杂度O( log N)。

    AVL树节点的定义

    template<class K, class V>
    struct AVLTreeNode 
    {
    	AVLTreeNode<K, V>* _left; //左孩子
    	AVLTreeNode<K, V>* _right; //右孩子
    	AVLTreeNode<K, V>* _parent; //父亲结点
    	 
    	pair<K, V> _Kv; //键值
    	int _bf; //平衡因子
    
    	//构造函数
    	AVLTreeNode(const pair<K, V>& Kv)
    		:_left(nullptr)
    		,_right(nullptr)
    		,_parent(nullptr)
    		,_Kv(Kv)
    		,_bf(0)
    	{ }
    
    };
    

    AVL树的定义

    template<class K, class V>
    class AVLTree 
    {
    	typedef AVLTreeNode<K, V> Node;
    public:
    	AVLTree() 
    		:_root(nullptr)
    	{}
    
    private:
    	Node* _root;
    };
    

    AVL树的插入

    AVL树就是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。那么AVL树的插入

    过程可以分为两步:

    按照二叉搜索树的方式插入新节点

    与根结点比较如果比根大就往右子树插入,如果比根小就往左子树插入,直到走到合适的位置就插入,由于这里是三叉链所以需要处理结点之间的关联关系

    bool Insert(const pair<K, V> &kv) 
    	{
    		if (!_root) _root = new Node(kv); //初始根节点
    
    		Node* cur = _root;
    		Node* parent = _root;
    		while (cur) 
    		{
    			K key = cur->_Kv.first;
    			if (key > kv.first) //比根结点的key值小,
    			{
    				parent = cur;
    				cur = cur->_left;
    			}
    			else if(key < kv.first)//比根结点的key值大,
    			{
    				parent = cur;
    				cur = cur->_right;
    			}
    			else 
    			{
    				return false;  //插入失败
    			}
    		}
    		
    		//开始插入
    		cur = new Node(kv);
    		Node* newNode = cur;
    		if (parent->_Kv.first > newNode->_Kv.first) //新插入的结点key值比根节点小就插入到左子树
    		{
    			parent->_left = newNode;
    			newNode->_parent = parent;
    		}
    		else		//新插入的结点key值比根节点大就插入到右子树
    		{
    			parent->_right = newNode;
    			newNode->_parent = parent;
    		}
    	}
    

    调整节点的平衡因子

    当左右子树的高度发生了变化,那么就需要对父亲及祖先路径上的所有结点的平衡因子进行调整

    在这里插入图片描述

    //更新祖先路径的所以结点的平衡因子
    		/* 
    			总结五种情况:
    				1、新增结点出现在父结点的左边,平衡因子减减
    				2、新增结点出现在父结点的右边,平衡因子加加
    				3、父亲的平衡因子为0就不再调整
    				4、父亲结点的平衡因子为1或者-1继续调整
    				5、父亲结点的平衡因子为2或者-2那就旋转
    				
    		*/
    	while (parent) 
    	{
    		if (parent->_left == cur) parent->_bf--;   //1、
    		if (parent->_right == cur) parent++;	   //2、
    		if (parent->_bf == 0) break; 			  //3、
    		if (parent->_bf == -1 || parent->_bf == 1)//4、 
    		{
    			cur = parent;
    			parent = parent->_parent;
    		}
    		if (parent->_bf == -2 || parent->_bf == 2) //5、
    		{
    			//旋转
    			if (parent->_bf == -2) 
    			{
    				if (cur->_bf == -1) RotateR(parent); //左边高,右单旋
    				else RotateLR(parent); //左右双旋
    			}
    			else //右 parent->_bf == 2
    			{
    				if (cur->_bf == 1) RotateL(parent);//右边高左单旋转
    				else RotateRL(parent); //右左双旋
    			}
    
    			break;
    		}
    	}
    

    AVL树的四种旋转

    旋转的原则是遵循搜索树的规则,尽量让两边平衡

    如果在一棵原本是平衡的AVL树中插入一个新节点,可能造成不平衡,此时必须调整树的结构,使之平衡化。根据节点插入位置的不同,AVL树的旋转分为四种:

    右单旋

    新节点插入较高左子树的左侧—左左:右单旋

    在这里插入图片描述
    不管是哪种单旋都得考虑两种情况:
    1、局部旋转,如果parent并不是树的_root结点,那么就需要调整subL和根结点的关系
    2、独立旋转,parent就是树的_root结点,那么subL就是旋转后的根节点了

    3、subLR有可能为null

    //右单旋
    void RotateR(Node* parent) 
    {
    	Node* subL = parent->_left;
    	Node* subLR = subL->_right;
    
    	parent->_left = subLR; 
    	if (subLR) subLR->_parent = parent;  //防止subLR为nullptr
    
    	subL->_right = parent;
    	Node* parent_parent = parent->_p	arent; //指针备份
    	parent->_parent = subL;
    	if (_root == parent) //如果parent就是树的根 
    	{
    		_root = subL;  //subL取代parent
    		_root->_parent = nullptr;
    	}
    	else  //如果parent并不是树的根
    	{
    		if (parent_parent->_left == parent) parent->_left = subL;
    		else parent_parent->_right = subL;
    
    		subL->_parent = parent_parent; //subL去做parent_parent的孩子
    	}
    	//调节平衡因子
    	subL->_bf = parent->_bf = 0;
    }
    

    左单旋

    新节点插入较高右子树的右侧—右右:左单旋

    在这里插入图片描述
    跟右单旋几乎是一样的做法
    1、局部旋转,如果parent并不是树的_root结点,那么就需要调整subL和根结点的关系
    2、独立旋转,parent就是树的_root结点,那么subL就是旋转后的根节点了
    3、subRL有可能为null

    //左单旋
    void RotateL(Node* parent) 
    {
    	Node* subR = parent->_right;
    	Node* subRL = subR->_left;
    	
    	parent->_right = subRL;
    	if (subRL) subRL->_parent = parent;
    	
    	subR->_left = parent;
    	Node* parent_parent = parent->_parent;
    	parent->_parent = subR;
    	
    	if (_root == parent) 
    	{
    		_root = subR;
    		_root->_parent = nullptr;
    	}
    	else  
    	{
    		if (parent_parent->_left == parent) parent_parent->_left = subR;
    		else parent_parent->_right = subR;
    
    		subR->_parent = parent_parent;
    	}
    	subR->_bf = parent->_bf = 0;
    }
    

    左右双旋

    新节点插入较高左子树的右侧—左右:先左单旋再右单旋

    1、新增结点在b或c都会影响左右子树的高度,从而引发双旋
    h > 0情况一:
    在这里插入图片描述
    h > 0,情况二:
    在这里插入图片描述
    h == 0情况三:

    在这里插入图片描述

    //左右旋转
    	void RotateLR(Node* parent) 
    	{
    		Node* subL = parent->_left;
    		Node* subLR = subL->_right;
    		int bf = subLR->_bf;
    
    		RotateL(parent->_left);
    		RotateR(parent);
    		if (bf == -1)  //h > 0,新增结点在b
    		{
    			parent->_bf = 1;
    			subLR->_bf = 0;
    			subL->_bf = 0;
    		}
    		else if (bf == 1) //h > 0,新增结点在c
    		{
    			subL->_bf = -1;
    			subLR->_bf = 0;
    			parent->_bf = 0;
    		}
    		else if(bf == 0) //h = 0
    		{
    			parent->_bf = 0;
    			subLR->_bf = 0;
    			subL->_bf = 0;
    		}
    		
    	}
    

    右左双旋

    右左双旋跟左右双旋的情况基本是类似的,这里就不列举多种情况了
    在这里插入图片描述
    新节点插入较高右子树的左侧—右左:先右单旋再左单旋

    	//右左旋转
    	void RotateRL(Node* parent)
    	{
    		Node* subR = parent->_right;
    		Node* subRL = subR->_left;
    		int bf = subRL->_bf;
    
    		RotateR(parent->_right);
    		RotateL(parent);
    		if (bf == -1)  //h > 0,新增结点在b
    		{
    			parent->_bf = 0;
    			subR->_bf = 1;
    			subRL->_bf = 0;
    		}
    		else if (bf == 1) //h > 0,新增结点在c
    		{
    			parent->_bf = -1;
    			subR->_bf = 0;
    			subRL->_bf = 0;
    		}
    		else if (bf == 0)//h = 0
    		{
    			subR->_bf = 0;
    			subRL->_bf = 0;
    			parent->_bf = 0;
    		}
    
    	}
    

    查找

    Node* Find(const K& key) 
    {
    	Node* cur = _root;
    	while (cur) 
    	{
    		if (key > cur->_Kv.first) cur = cur->_right; //左子树
    		else if (key < cur->_Kv.first) cur = cur->_left; //右子树
    		else return cur;
    	}
    }
    

    其他接口

    判断是不是平衡二叉树

    int height(Node* root) //求高度
    {
    	return !root ? 0 
    		   : max(height(root->_left), 
    			 height(root->_right)) + 1;
    }
    
    void _Inorder(Node* root)//中序遍历 
    {
    	if (!root) return;
    	_Inorder(root->_left);
    	printf("%d : %d\n",root->_Kv.first, root->_Kv.second);
    	_Inorder(root->_right);
    }
    
    //判断是不是平衡二叉树
    bool IsAVLTree() 
    {
    	return _IsAVLTree(_root);
    }
    
    bool _IsAVLTree(Node* root)
    {
    	if (!root) return true;
    	int left = height(root->_left);
    	int right = height(root->_right);
    	//检查平衡因子	
    	if (right - left != root->_bf)
    	{
    		printf("错误的平衡因子 %d :%d\n", root->_Kv.first, root->_Kv.second);
    		return false;
    	}
    	return (abs(right - left) < 2)
    		&& _IsAVLTree(root->_left)
    		&& _IsAVLTree(root->_right);
    }
    

    析构函数

    //析构函数
    ~AVLTree()
    {
    	Destroy(_root);
    	_root = nullptr;
    }
    
    void Destroy(Node *root)//后序销毁结点
    {
    	if (!root) return;
    	Destroy(root->_left);
    	Destroy(root->_right);
    	delete root;
    }
    

    拷贝构造

    Node* copy(Node* cp)
    {
    	if (!cp) return nullptr;
    
    	Node* newnode = new Node(cp->_Kv);
    	newnode->_left = copy(cp->_left);
    	newnode->_right = copy(cp->_right);
    	return newnode;
    }
    
    //拷贝构造
    AVLTree(const AVLTree<K, V>& job)
    {
    	if(&job != this)
    	_root = copy(job._root);
    }
    
    

    拷贝赋值

    void operator=(AVLTree<K, V> tmp)
    {
    	if (&tmp != this)
    	swap(tmp._root, this->_root);
    }
    

    重载operator[ ]

    V& operator[](const K& key)
    {
    	return (Insert(make_pair(key, V())).first)->_Kv.second;
    }
    

    AVL树的完整实现代码博主已经放在 git.

    在这里插入图片描述

    展开全文
  • 什么是AVL树AVL树的特点及形成原因 二叉搜索树基本概念 二叉搜索的特点 二叉搜索树的优点及缺点 改进的二叉搜索树——AVL树 AVL树的定义 AVL树的特点 结点的平衡因子balance 构建一个AVL树 构建一个AVL...
  • 该程序通过C++实现了AVL树的一些基础操作:1.编写AVL树判别程序,并判别一个二叉搜索树是否为AVL树;2.实现AVL树的ADT,包括其上的基本操作:结点的加入和删除;3.实现基本操作的动态演示(图形演示);最重要的是,该...
  • AVL树5.1 AVL树的相关概念及特点5.2 普通BST和AVL树添加对比6. AVL树设计6.1 继承结构6.2 普通BST添加导致失衡例子6.3 解决添加失衡——LL-右旋转(单旋)6.4 解决添加失衡——RR-左旋转(单旋)6.5 解决添加失衡——LR...
  • 查找树(二):AVL树

    2021-08-30 22:02:24
    AVL树2. 插入操作2.1 单旋转2.2 双旋转2.3 整棵树都平衡了吗?3. 删除操作 1. AVL树 从前面的探讨已经可以知道,普通的二分查找树的查找操作并不能实现O(log2n)的时间复杂度,因此需要为它添加平衡条件。这包含两个...
  • 使用mfc实现的图形化界面显示的avl树操作程序,可以进行新建,删除,查找等操作。
  • AVL树(动图详解)

    千次阅读 多人点赞 2021-11-22 22:00:56
    文章目录 AVL树的概念 AVL树结点的定义 AVL树的插入 AVL树的旋转 左单旋 右单旋 左右双旋 右左双旋 AVL树的验证 AVL树的查找 AVL树的修改 AVL树的删除 AVL树的性能 AVL树的概念 二叉搜索树虽然可以提高我们查找数据...
  • avl树实现hash表

    2018-12-29 13:57:58
    利用avl树实现hash表,自测通过。下载代码直接编译,即可运行。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 40,861
精华内容 16,344
关键字:

avl树

友情链接: ucmsjianzhan.zip