平衡二叉查找树-AVL树代码实现

什么是“平衡二叉查找树”？

平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于1。完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。

平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。最先被发明的平衡二叉查找树是AVL树，它严格符合我刚讲到的平衡二叉查找树的定义，即任何节点的左右子树高度相差不超过1，是一种高度平衡的二叉查找树。

AVL树

AVL树（Adelson-Velsky and Landis Tree）是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logN)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis（英语：E. M. Landis），他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。

节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

基础代码

import java.util.Comparator;
public class AVLTree<E> extends BST<E> {
    public AVLTree() {
        this(null);
    }

    public AVLTree(Comparator<E> comparator) {
        super(comparator);
    }
    
    //重写该方法，AVL树Node节点有height属性，在添加AVL树节点的时候，使用AVL树的节点信息
    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new AVLNode<>(element, parent);
    }
    
    //TODO待完善
    @Override
    protected void afterAdd(Node<E> node) {
         // TODO 更新高度
         // TODO 恢复平衡
         // TODO 整棵树恢复平衡
    }
    
    //判断是否平衡
    private boolean isBalanced(Node<E> node) {
        return Math.abs(((AVLNode<E>) node).balanceFactor()) <= 1;
    }
    
    private static class AVLNode<E> extends Node<E> {
        int height = 1;//加入高度属性

        public AVLNode(E element, Node<E> parent) {
            super(element, parent);
        }

        //返回节点平衡因子
        public int balanceFactor() {
            int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
            return leftHeight - rightHeight;
        }

        //更新AVL节点高度
        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;
            if (leftHeight < rightHeight) return right;
            return isLeftChild() ? left : right;//高度相同的情况，返回同方向的节点
        }

        @Override
        public String toString() {
            String parentString = "null";
            if (parent != null) {
                parentString = parent.element.toString();
            }
            return element + "_p(" + parentString + ")_h(" + height + ")";
        }
    }
}

image-20210602205239018

普通二叉搜索树与AVL树平衡对比

image-20210602205350882

添加导致的失衡

image-20210602210145889

@Override
protected void afterAdd(Node<E> node) {
    while ((node = node.parent) != null) {
        if (isBalanced(node)) {
            // 更新高度
            updateHeight(node);
        } else {
            // 恢复平衡
            rebalance(node);//此时寻找到的node为不平衡的节点，即下面分析中的grand(祖父节点)
            // 整棵树恢复平衡
            break;
        }
    }
}
   

/**
 * 恢复平衡
 *
 * @param grand 高度最低的那个不平衡节点
 */
private void rebalance(Node<E> grand) {
    Node<E> parent = ((AVLNode<E>) grand).tallerChild();//祖父节点高度高的子节点为parent节点
    Node<E> node = ((AVLNode<E>) parent).tallerChild();//parent节点高度高的子节点为参与旋转的node节点
    if (parent.isLeftChild()) { // L
        if (node.isLeftChild()) { // LL
            rotateRight(grand);
        } else { // LR
            rotateLeft(parent);
            rotateRight(grand);
        }
    } else { // R
        if (node.isLeftChild()) { // RL
            rotateRight(parent);
            rotateLeft(grand);
        } else { // RR
            rotateLeft(grand);
        }
    }
}

LL型节点失衡

image-20210602210711893

LL型失衡-右旋转调整失衡

image-20210602210928094

private void rotateRight(Node<E> grand) {
    Node<E> parent = grand.left;
    Node<E> child = parent.right;
    grand.left = child;
    parent.right = grand;
    afterRotate(grand, parent, child);
}

private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
    // 让parent称为子树的根节点
    parent.parent = grand.parent;
    if (grand.isLeftChild()) {
        grand.parent.left = parent;
    } else if (grand.isRightChild()) {
        grand.parent.right = parent;
    } else { // grand是root节点
        root = parent;
    }

    // 更新child的parent
    if (child != null) {
        child.parent = grand;
    }

    // 更新grand的parent
    grand.parent = parent;

    // 更新高度
    updateHeight(grand);
    updateHeight(parent);
}

RR型节点失衡

image-20210602211408272

RR型失衡-左旋转调整失衡

image-20210602211533407

左旋转操作

image-20210603165108956

private void rotateLeft(Node<E> grand) {
    Node<E> parent = grand.right;
    Node<E> child = parent.left;
    grand.right = child;
    parent.left = grand;
    
    // 让parent称为子树的根节点
        parent.parent = grand.parent;
        if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else if (grand.isRightChild()) {
            grand.parent.right = parent;
        } else { // grand是root节点
            root = parent;
        }

        // 更新child的parent
        if (child != null) {
            child.parent = grand;
        }

        // 更新grand的parent
        grand.parent = parent;   
        // 更新高度
        updateHeight(grand);
        updateHeight(parent);           
    
}

LR型节点失衡

image-20210602212337675

LR型节点失衡 - RR左旋转，LL右旋转(双旋)

image-20210602212632414

LR型节点失衡

image-20210602212905553

RL - LL右旋转，RR左旋转(双旋)

image-20210602213016256

统一所有旋转操作

image-20210603170609741

/**
 * 恢复平衡
 *
 * @param grand 高度最低的那个不平衡节点
 */
private void rebalance(Node<E> grand) {
    Node<E> parent = ((AVLNode<E>) grand).tallerChild();
    Node<E> node = ((AVLNode<E>) parent).tallerChild();
    if (parent.isLeftChild()) { // L
        if (node.isLeftChild()) { // LL
            rotate(grand, node, node.right, parent, parent.right, grand);
        } else { // LR
            rotate(grand, parent, node.left, node, node.right, grand);
        }
    } else { // R
        if (node.isLeftChild()) { // RL
            rotate(grand, grand, node.left, node, node.right, parent);
        } else { // RR
            rotate(grand, grand, parent.left, parent, node.left, node);
        }
    }
}

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;
    }
    updateHeight(b);

    // e-f
    f.left = e;
    if (e != null) {
        e.parent = f;
    }
    updateHeight(f);

    // b-d-f
    d.left = b;
    d.right = f;
    b.parent = d;
    f.parent = d;
    updateHeight(d);
}

删除导致的失衡

image-20210603180519412

删除-LL型失衡-右旋转调整失衡

image-20210603182625342 image-20210603182729279

删除-RR型失衡-左旋转调整失衡

image-20210603183008896 image-20210603183043030

删除-LR型节点失衡 - RR左旋转，LL右旋转(双旋)

image-20210603183128084

删除-RL - LL右旋转，RR左旋转(双旋)

image-20210603183223332

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

---

• 二叉树基础代码

public class BinaryTree<E>  {
    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 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;
    }
    
    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);
    }

    //返回node节点的前驱节点
    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;
    }
    //返回node节点的后继节点
    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;
    }


    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;
        }
    }

}

• 二叉搜索树-代码

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值 这个定义定义了二叉树添加节点和删除节点的要求。

所以二叉搜索树继承于二叉树，实现了add和remove方法

• public void add(E element)
• public void remove(E element)

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++;

         // 新添加节点之后的处理
         afterAdd(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++;
      
      // 新添加节点之后的处理
      afterAdd(newNode);
   }
   
   /**
    * 添加node之后的调整
    * @param node 新添加的节点
    */
   protected void afterAdd(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-Tree完整代码

import java.util.Comparator;

public class AVLTree<E> extends BST<E> {
    public AVLTree() {
        this(null);
    }

    public AVLTree(Comparator<E> comparator) {
        super(comparator);
    }

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

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

    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new AVLNode<>(element, parent);
    }

    /**
     * 恢复平衡
     *
     * @param grand 高度最低的那个不平衡节点
     */
    @SuppressWarnings("unused")
    private void rebalance2(Node<E> grand) {
        Node<E> parent = ((AVLNode<E>) grand).tallerChild();
        Node<E> node = ((AVLNode<E>) parent).tallerChild();
        if (parent.isLeftChild()) { // L
            if (node.isLeftChild()) { // LL
                rotateRight(grand);
            } else { // LR
                rotateLeft(parent);
                rotateRight(grand);
            }
        } else { // R
            if (node.isLeftChild()) { // RL
                rotateRight(parent);
                rotateLeft(grand);
            } else { // RR
                rotateLeft(grand);
            }
        }
    }

    /**
     * 恢复平衡
     *
     * @param grand 高度最低的那个不平衡节点
     */
    private void rebalance(Node<E> grand) {
        Node<E> parent = ((AVLNode<E>) grand).tallerChild();
        Node<E> node = ((AVLNode<E>) parent).tallerChild();
        if (parent.isLeftChild()) { // L
            if (node.isLeftChild()) { // LL
                rotate(grand, node, node.right, parent, parent.right, grand);
            } else { // LR
                rotate(grand, parent, node.left, node, node.right, grand);
            }
        } else { // R
            if (node.isLeftChild()) { // RL
                rotate(grand, grand, node.left, node, node.right, parent);
            } else { // RR
                rotate(grand, grand, parent.left, parent, node.left, node);
            }
        }
    }

    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;
        }
        updateHeight(b);

        // e-f
        f.left = e;
        if (e != null) {
            e.parent = f;
        }
        updateHeight(f);

        // b-d-f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;
        updateHeight(d);
    }

    private void rotateLeft(Node<E> grand) {
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = child;
        parent.left = grand;
        afterRotate(grand, parent, child);
    }

    private void rotateRight(Node<E> grand) {
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        grand.left = child;
        parent.right = grand;
        afterRotate(grand, parent, child);
    }

    private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        // 让parent称为子树的根节点
        parent.parent = grand.parent;
        if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else if (grand.isRightChild()) {
            grand.parent.right = parent;
        } else { // grand是root节点
            root = parent;
        }

        // 更新child的parent
        if (child != null) {
            child.parent = grand;
        }

        // 更新grand的parent
        grand.parent = parent;

        // 更新高度
        updateHeight(grand);
        updateHeight(parent);
    }

    private boolean isBalanced(Node<E> node) {
        return Math.abs(((AVLNode<E>) node).balanceFactor()) <= 1;
    }

    private void updateHeight(Node<E> node) {
        ((AVLNode<E>) node).updateHeight();
    }

    private static class AVLNode<E> extends Node<E> {
        int height = 1;

        public AVLNode(E element, Node<E> parent) {
            super(element, parent);
        }

        public int balanceFactor() {
            int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
            return leftHeight - rightHeight;
        }

        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;
            if (leftHeight < rightHeight) return right;
            return isLeftChild() ? left : right;
        }

        @Override
        public String toString() {
            String parentString = "null";
            if (parent != null) {
                parentString = parent.element.toString();
            }
            return element + "_p(" + parentString + ")_h(" + height + ")";
        }
    }
}