美文网首页
21-平衡二叉搜索树-AVL树

21-平衡二叉搜索树-AVL树

作者: weyan | 来源:发表于2021-08-30 12:38 被阅读0次

    一、AVL树

    1.添加可能会导致失衡
    2.解决失衡

    (首先出现失衡的节点g)代表祖父节点； p 代表父节点； n代表当前节点；T0/T1/T2......代表的是一块不确定的子节点，添加一个(红颜色)节点后会导致从g点开始失衡

    • \color{#FF3030}{也可以理解为添加一个红颜色节点后，n节点导致g节点失衡}

    第一种情况- LL : LL代表g节点的左子节点p的左子节点

    • 解决办法：对g右旋转

    第二种情况-RR : RR代表g节点的右子节点p的右子节点n

    • 解决办法：对g左旋转

    第三种情况-LR : LR代表g节点的左子节点p的右子节点n

    • 解决办法：先对p左旋转，然后再对g右旋转

    第四种情况-RL : RL代表g节点的右子节点p的左子节点n

    • 解决办法：先对p右旋转，然后再对g左旋转

    完整代码如下：

    • BinaryTree(二叉树)
    //二叉树
package com.weyan.tree;

import java.util.LinkedList;
import java.util.Queue;

import com.weyan.printer.BinaryTreeInfo;

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 preorderTraversal() {
        preorderTraversal(root);
    }

    private void preorderTraversal(Node<E> node) {
        if (node == null)
            return;
        System.out.println(node.element);
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }

    // 中序遍历（递归方法）
    public void inorderTraversal() {
        inorderTraversal(root);
    }

    private void inorderTraversal(Node<E> node) {
        if (node == null)
            return;
        preorderTraversal(node.left);
        System.out.println(node.element);
        preorderTraversal(node.right);
    }

    // 后序遍历（递归方法）
    public void postorderTraversal() {
        postorderTraversal(root);
    }

    private void postorderTraversal(Node<E> node) {
        if (node == null)
            return;
        preorderTraversal(node.left);
        preorderTraversal(node.right);
        System.out.println(node.element);
    }

    // 层序遍历(通过链表实现)
    public void levelorderTraversal() {
        if (root == null)
            return;
        Queue<Node<E>> queue = new LinkedList<>();
        // 入队
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 出队
            Node<E> node = queue.poll();
            System.out.println(node.element);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    /*
     * 使用自定义打印器 需要实现以下几个方法
     * 
     */
    @Override
    public Object root() {
        // TODO Auto-generated method stub
        return root;
    }

    @SuppressWarnings("unchecked")
    @Override
    public Object left(Object node) {
        // TODO Auto-generated method stub
        return ((Node<E>) node).left;
    }

    @SuppressWarnings("unchecked")
    @Override
    public Object right(Object node) {
        // TODO Auto-generated method stub
        return ((Node<E>) node).right;
    }

    @SuppressWarnings("unchecked")
    @Override
    public Object string(Object node) {
        // TODO Auto-generated method stub
        // 打印出parent
        Node<E> myNode = (Node<E>) node;
        String parentString = "null";
        if (myNode.parent != null) {
            parentString = myNode.parent.element.toString();
        }
        return myNode.element + "_(" + parentString + ")";
    }

    // 前驱节点
    protected Node<E> predecessor(Node<E> node) {
        if (node == null)
            return null;
        // 前驱节点在左子树当中（left.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.right) {
            node = node.parent;
        }
        // node.parent == null && node.left == null
        return node.parent;
    }

    // 后继节点
    protected Node<E> successor(Node<E> node) {
        if (node == null)
            return null;
        // 前驱节点在左子树当中（right.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.left) {
            node = node.parent;
        }
        // node.parent == null && node.right == null
        return node.parent;
    }

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

    /** ---递归写法--- **/
    // 二叉树的高度
//  public int height() {
//      return nodeHeight(root);
//  }
    // 节点高度
//  private int nodeHeight(Node<E> node) {
//      if (node == null) return 0;
//      return 1 + Math.max(nodeHeight(node.left), nodeHeight(node.right));
//  }

    /** ---层序遍历写法--- **/
    // 二叉树的高度
    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 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;
    }

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

        // 度为2节点
        public boolean hasTwoChildrenNode() {
            return left != null && right != null;
        }

        // 当前节点是否是父节点的左子节点
        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }

        // 当前节点是否是父节点的右子节点
        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }

    }

}
    • BST(二叉搜索树)
    package com.weyan.tree;

import java.util.Comparator;

@SuppressWarnings("unchecked")
public class BST<E> extends BinaryTree<E> {
    private Comparator<E> comparator;
    //java 默认构造函数是无参数
    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;
        while (node != null) {
            parent = node;
            cmp = compare(element, node.element);
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {// 相等
                node.element = element;
                return;
            }
        }
        // 看看插入到父节点的哪个位置
        Node<E> newNode = createNode(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else if (cmp < 0) {
            parent.left = newNode;
        }
        size++;
        
        //添加节点之后的处理
        afterAdd(newNode);
    }
    
    //添加node节点之后的调整
    protected void afterAdd(Node<E> node) { }

    public void remove(E element) {
        remove(node(element));
    }

    private void remove(Node<E> node) {
        if (node == null) {
            return;
        }
        size--;
        // 度为2的节点
        if (node.hasTwoChildrenNode()) {
            // 找到后继节点
            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;
            }
        } else if (node.parent == null) {// node是叶子节点并且是根节点
            root = null;
        } else {// node是叶子节点，但不是根节点
            if (node == node.parent.right) {
                node.parent.right = null;
            } else {// node == node.parent.left
                node.parent.left = null;
            }
        }
    }

    // 根据元素查找对应的节点
    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 {
                node = node.left;
            }
        }
        return null;
    }

    /// 是否包含一个元素
    public boolean contains(E element) {
        return node(element) != null;
    }

    // 比较两个节点,返回值==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");
        }
    }

}
    • AVLTree（AVL平衡二叉搜索树）
    package com.weyan.tree;

import java.util.Comparator;

public class AVLTree<E> extends BST<E> {

    // java 默认构造函数是无参数
    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 Node<E> createNode(E element, Node<E> parent) {
        // TODO Auto-generated method stub
        return new AVLNode<>(element, 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();
    }

    // 恢复平衡，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
                rotateRight(grand);
            } else { // LR
                rotateLeft(parent);
                rotateRight(grand);
            }
        } else { // R
            if (node.isLeftChild()) { // RL
                rotateRight(parent);
                rotateLeft(grand);
            } else { // RR
                rotateLeft(grand);
            }
        }
    }

    // 左旋转
    private void rotateLeft(Node<E> grand) {
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = child;
        parent.left = grand;
        
        //更新parent/grand/child的parent和parent/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;
        
        //更新parent/grand/child的parent和parent/grand的高度
        afterRotate(grand, parent, child);
    }
    //更新parent/grand/child的parent和parent/grand的高度
    private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        // parent称为子树的根节点,更新parent的parent
        parent.parent = grand.parent;
        if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else if (grand.isRightChild()) {
            grand.parent.right = parent;
        } else {
            root = parent;
        }

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

    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 AVLNode<E> tallerChild() {
            int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
            if (leftHeight > rightHeight)
                return (AVLNode<E>) left;
            if (leftHeight < rightHeight)
                return (AVLNode<E>) right;
            return isLeftChild() ? (AVLNode<E>) left : (AVLNode<E>) right;
        }

    }

}
    • Main
    package com.weyan;

import java.util.Comparator;
import java.util.regex.Matcher;

import com.weyan.file.Files;
import com.weyan.printer.BinaryTreeInfo;
import com.weyan.printer.BinaryTrees;
import com.weyan.tree.AVLTree;
import com.weyan.tree.BST;
import com.weyan.tree.BinarySearchTree;

public class Main {
    // 自定义类实现比较器PersonComparator
    private static class PersonComparator implements Comparator<Person> {
        public int compare(Person e1, Person e2) {
            return e1.getAge() - e2.getAge();
        }
    }

    // 自定义类实现比较器PersonComparator2
    private static class PersonComparator2 implements Comparator<Person> {
        public int compare(Person e1, Person e2) {
            return e2.getAge() - e1.getAge();
        }
    }

    @SuppressWarnings("unused")
    private static void test1() {
        // 传入比较器PersonComparator
        BinarySearchTree<Person> bst1 = new BinarySearchTree<Person>(new PersonComparator());
        bst1.add(new Person(12));
        bst1.add(new Person(15));
        // 传入比较器PersonComparator2
        BinarySearchTree<Person> bst2 = new BinarySearchTree<Person>(new PersonComparator2());
        bst2.add(new Person(12));
        bst2.add(new Person(15));
        // 不传入比较器
        BinarySearchTree<Person> bst3 = new BinarySearchTree<Person>();
        bst3.add(new Person(12));
        bst3.add(new Person(15));

        /*
         * java 中的匿名类 类似于iOS中的Block JS中的闭包(funciton)
         */
        BinarySearchTree<Person> bst4 = new BinarySearchTree<Person>(new Comparator<Person>() {

            @Override
            public int compare(Person o1, Person o2) {
                return o1.getAge() - o2.getAge();
            }
        });
        bst4.add(new Person(12));
        bst4.add(new Person(15));
    }

    @SuppressWarnings("unused")
    private static void test2() {
        Integer data[] = new Integer[] { 7, 4, 9, 2, 5, 8, 11, 3 };
        BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
        for (int i = 0; i < data.length; i++) {
            bst.add(data[i]);
        }
        BinaryTrees.println(bst);
    }

    @SuppressWarnings("unused")
    private static void test3() {
        BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
        for (int i = 0; i < 40; i++) {
            bst.add((int) (Math.random() * 100));
        }
        String str = BinaryTrees.printString(bst);
        str += "\n";// 这一步一定得换行，不然后面追加的图会错乱
        Files.writeToFile("/Users/xieweiyan/Desktop/printer.txt", str);
    }
    
    private static void test4() {
        Integer data[] = new Integer[] { 7, 4, 9, 2, 5, 8, 11, 3 };
        BST<Integer> bst = new BST<Integer>();
        for (int i = 0; i < data.length; i++) {
            bst.add(data[i]);
        }
        BinaryTrees.println(bst);
    }
    
    private static void test5() {
        Integer data[] = new Integer[] { 85, 19, 69, 3, 7, 99, 95, 2, 1, 70, 44, 58, 11, 21, 14, 93, 57, 4, 56 };
        AVLTree<Integer> avlTree = new AVLTree<Integer>();
        for (int i = 0; i < data.length; i++) {
            avlTree.add(data[i]);
        }
        BinaryTrees.println(avlTree);
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
//      test1();
//      test2();
//      test3();
//      test4();
        test5();
    }

}

    验证结果

    第二种回复平衡的方法：统一旋转操作

    AVLTree 平衡二叉搜索树改动代码如下

    package com.weyan.tree;

import java.util.Comparator;

public class AVLTree<E> extends BST<E> {

    // java 默认构造函数是无参数
    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 {// 不平衡，恢复为平衡
                rebalance2(node);
                break;
            }

        }

    }

    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        // TODO Auto-generated method stub
        return new AVLNode<>(element, 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 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
                rotate(grand, node.left, node, node.right, parent, parent.right, grand, grand.right);
            } else { // LR
                rotate(grand, parent.left, parent, node.left, node, node.right, grand, grand.right);
            }
        } else { // R
            if (node.isLeftChild()) { // RL
                rotate(grand, grand.left, grand, node.left, node, node.right, parent, parent.right);
            } else { // RR
                rotate(grand, grand.left, grand, parent.left, parent, node.left, node, node.right);
            }
        }
    }

    // 统一旋转操作
    private void rotate(Node<E> r, // 子树的根节点(不平衡节点点)
            Node<E> a, Node<E> b, Node<E> c, Node<E> d, Node<E> e, Node<E> f, Node<E> g) {
        // 让d成为这棵子树的根节点
        d.parent = r.parent;
        if (r.isLeftChild()) {
            r.parent.left = d;
        } else if (r.isRightChild()) {
            r.parent.right = d;
        } else {
            root = d;
        }

        // 处理a-b-c
        b.left = a;
        b.right = c;
        if (a != null) {
            a.parent = b;
        }
        if (c != null) {
            c.parent = b;
        }
        // 更新中间b节点的高度
        updateHeight(b);

        // 处理e-f-g
        f.left = e;
        f.right = g;
        if (e != null) {
            e.parent = f;
        }
        if (g != null) {
            g.parent = f;
        }
        // 更新中间f节点的高度
        updateHeight(f);

        // 处理b-d-f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;
        // 更新中间d节点的高度
        updateHeight(d);

    }

    /*---------------第一种方法恢复平衡----------*/
    // 第一种方法恢复平衡，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
//              rotateRight(grand);
//          } else { // LR
//              rotateLeft(parent);
//              rotateRight(grand);
//          }
//      } else { // R
//          if (node.isLeftChild()) { // RL
//              rotateRight(parent);
//              rotateLeft(grand);
//          } else { // RR
//              rotateLeft(grand);
//          }
//      }
//  }

    // 左旋转
    private void rotateLeft(Node<E> grand) {
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = child;
        parent.left = grand;

        // 更新parent/grand/child的parent和parent/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;

        // 更新parent/grand/child的parent和parent/grand的高度
        afterRotate(grand, parent, child);
    }

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

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

    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 AVLNode<E> tallerChild() {
            int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
            if (leftHeight > rightHeight)
                return (AVLNode<E>) left;
            if (leftHeight < rightHeight)
                return (AVLNode<E>) right;
            return isLeftChild() ? (AVLNode<E>) left : (AVLNode<E>) right;
        }

    }

}

    验证结果

    结果比对
    3.删除操作导致的失衡
    • 红色代表要删除的节点
    • 绿色代表 如果绿色节点不存在，可能会导致更高层的祖先节点会失衡。
    平衡二叉搜索树删除也可能会导致父节点或祖父节点失衡
    4.解决删除操作导致的失衡方案

    代码如下：
    BST:二叉搜索树

    package com.weyan.tree;

import java.util.Comparator;

@SuppressWarnings("unchecked")
public class BST<E> extends BinaryTree<E> {
    private Comparator<E> comparator;
    //java 默认构造函数是无参数
    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;
        while (node != null) {
            parent = node;
            cmp = compare(element, node.element);
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {// 相等
                node.element = element;
                return;
            }
        }
        // 看看插入到父节点的哪个位置
        Node<E> newNode = createNode(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else if (cmp < 0) {
            parent.left = newNode;
        }
        size++;
        
        //添加节点之后的处理
        afterAdd(newNode);
    }
    
    //添加node节点之后的调整
    protected void afterAdd(Node<E> node) { }

    public void remove(E element) {
        remove(node(element));
    }

    private void remove(Node<E> node) {
        if (node == null) {
            return;
        }
        size--;
        // 度为2的节点
        if (node.hasTwoChildrenNode()) {
            // 找到后继节点
            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;
            }
            //node:删除的节点，删除之后的处理
            afterRemove(node);
        } else if (node.parent == null) {// node是叶子节点并且是根节点
            root = null;
            //node:删除的节点，删除之后的处理。
            afterRemove(node);
        } else {// node是叶子节点，但不是根节点
            if (node == node.parent.right) {
                node.parent.right = null;
            } else {// node == node.parent.left
                node.parent.left = null;
            }
            //node:删除的节点，删除之后的处理。
            afterRemove(node);
        }
    }
    
    //删除node节点之后的调整
    protected void afterRemove(Node<E> 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 {
                node = node.left;
            }
        }
        return null;
    }

    /// 是否包含一个元素
    public boolean contains(E element) {
        return node(element) != null;
    }

    // 比较两个节点,返回值==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");
        }
    }

}

    AVLTree:平衡二叉搜索树

    package com.weyan.tree;

import java.util.Comparator;

public class AVLTree<E> extends BST<E> {

    // java 默认构造函数是无参数
    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 {// 不平衡，恢复为平衡
                rebalance2(node);
                break;
            }
        }
        
    }
    
    ///删除之后的操作
    @Override
    protected void afterRemove(Node<E> node) {
        while ((node = node.parent) != null) {
            if (isBalanced(node)) {// 平衡，更新高度
                updateHeight(node);
            } else {// 不平衡，恢复为平衡
                rebalance2(node); 
                //注：跟afterAdd的区别是 不用break,因为平衡一次过后可能还会存在上层祖节点不平衡，需要多次平衡调整。
            }
        }
        
    }

    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        // TODO Auto-generated method stub
        return new AVLNode<>(element, 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 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
                rotate(grand, node.left, node, node.right, parent, parent.right, grand, grand.right);
            } else { // LR
                rotate(grand, parent.left, parent, node.left, node, node.right, grand, grand.right);
            }
        } else { // R
            if (node.isLeftChild()) { // RL
                rotate(grand, grand.left, grand, node.left, node, node.right, parent, parent.right);
            } else { // RR
                rotate(grand, grand.left, grand, parent.left, parent, node.left, node, node.right);
            }
        }
    }

    // 统一旋转操作
    private void rotate(Node<E> r, // 子树的根节点(不平衡节点点)
            Node<E> a, Node<E> b, Node<E> c, Node<E> d, Node<E> e, Node<E> f, Node<E> g) {
        // 让d成为这棵子树的根节点
        d.parent = r.parent;
        if (r.isLeftChild()) {
            r.parent.left = d;
        } else if (r.isRightChild()) {
            r.parent.right = d;
        } else {
            root = d;
        }

        // 处理a-b-c
        b.left = a;
        b.right = c;
        if (a != null) {
            a.parent = b;
        }
        if (c != null) {
            c.parent = b;
        }
        // 更新中间b节点的高度
        updateHeight(b);

        // 处理e-f-g
        f.left = e;
        f.right = g;
        if (e != null) {
            e.parent = f;
        }
        if (g != null) {
            g.parent = f;
        }
        // 更新中间f节点的高度
        updateHeight(f);

        // 处理b-d-f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;
        // 更新中间d节点的高度
        updateHeight(d);

    }

    /*---------------第一种方法恢复平衡----------*/
    // 第一种方法恢复平衡，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
//              rotateRight(grand);
//          } else { // LR
//              rotateLeft(parent);
//              rotateRight(grand);
//          }
//      } else { // R
//          if (node.isLeftChild()) { // RL
//              rotateRight(parent);
//              rotateLeft(grand);
//          } else { // RR
//              rotateLeft(grand);
//          }
//      }
//  }

    // 左旋转
    private void rotateLeft(Node<E> grand) {
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = child;
        parent.left = grand;

        // 更新parent/grand/child的parent和parent/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;

        // 更新parent/grand/child的parent和parent/grand的高度
        afterRotate(grand, parent, child);
    }

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

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

    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 AVLNode<E> tallerChild() {
            int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
            if (leftHeight > rightHeight)
                return (AVLNode<E>) left;
            if (leftHeight < rightHeight)
                return (AVLNode<E>) right;
            return isLeftChild() ? (AVLNode<E>) left : (AVLNode<E>) right;
        }

    }

}
    验证结果 比对结果

    总结

    相关文章

      网友评论

          本文标题：21-平衡二叉搜索树-AVL树

          本文链接：https://www.haomeiwen.com/subject/ieizsltx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|21-平衡二叉搜索树-AVL树|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！