关于java:数据结构之AVL

30次阅读

共计 8229 个字符，预计需要花费 21 分钟才能阅读完成。

AVL

均衡二叉树

均衡二叉查找树：简称均衡二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度均衡的二叉树，依据科学家的英文名也称为 AVL 树。它具备如下几个性质：

  1. 能够是空树。
  2. 如果不是空树，任何一个结点的左子树与右子树都是均衡二叉树，并且高度之差的绝对值不超过 1。

二叉搜寻树肯定水平上能够进步搜寻效率，然而当原序列有序时，例如序列 {1，2，3，4，5，6}，结构二叉搜寻树。根据此序列结构的二叉搜寻树为右斜树，同时二叉树进化成单链表，搜寻效率升高为 O(n)。

在此二叉搜寻树中查找元素 6 须要查找 6 次。

二叉搜寻树的查找效率取决于树的高度，因而放弃树的高度最小，即可保障树的查找效率。同样的序列 A，将其改为图中的形式存储，查找元素 6 时只需比拟 3 次，查找效率晋升一倍。

能够看出当节点数目肯定，放弃树的左右两端保持平衡，树的查找效率最高。

这种左右子树的高度相差不超过 1 的树为均衡二叉树。

均衡因子

某节点的左子树与右子树的高度 (深度) 差即为该节点的均衡因子（BF：Balance Factor）。

节点为 2 的深度为 1，因为没有子节点所有均衡因子是 0，节点为 4 的深度为 2，均衡因子是左孩子减去右孩子所以是1-0 = 1，均衡因子为 1。顺次类推，当有节点大于 1 的时候就阐明不是均衡二叉树。

public class AVLTree<K extends Comparable<K>, V> {

    private class Node{
        public K key;
        public V value;
        public Node left, right;
        public int height;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
            left = null;
            right = null;
            height = 1;
        }
    }

    private Node root;
    private int size;

    public AVLTree(){
        root = null;
        size = 0;
    }

    public int getSize(){return size;}

    public boolean isEmpty(){return size == 0;}

    // 取得节点 node 的高度
    private int getHeight(Node node){if(node == null) {return 0;}
        return node.height;
    }

    // 取得节点 node 的均衡因子
    private int getBalanceFactor(Node node){if(node == null) {return 0;}
        return getHeight(node.left) - getHeight(node.right);
    }

    // 向二分搜寻树中增加新的元素(key, value)
    public void add(K key, V value){root = add(root, key, value);
    }

    // 向以 node 为根的二分搜寻树中插入元素(key, value)，递归算法
    // 返回插入新节点后二分搜寻树的根
    private Node add(Node node, K key, V value){if(node == null){
            size ++;
            return new Node(key, value);
        }

        if(key.compareTo(node.key) < 0) {node.left = add(node.left, key, value);
        } else if(key.compareTo(node.key) > 0) {node.right = add(node.right, key, value);
        } else // key.compareTo(node.key) == 0
        {node.value = value;}

        // 更新 height
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

        // 计算均衡因子
        int balanceFactor = getBalanceFactor(node);
        if(Math.abs(balanceFactor) > 1) {System.out.println("unbalanced :" + balanceFactor);
        }

        return node;
    }

    // 返回以 node 为根节点的二分搜寻树中，key 所在的节点
    private Node getNode(Node node, K key){if(node == null) {return null;}

        if(key.equals(node.key)) {return node;} else if(key.compareTo(node.key) < 0) {return getNode(node.left, key);
        } else // if(key.compareTo(node.key) > 0)
        {return getNode(node.right, key);
        }
    }

    public boolean contains(K key){return getNode(root, key) != null;
    }

    public V get(K key){Node node = getNode(root, key);
        return node == null ? null : node.value;
    }

    public void set(K key, V newValue){Node node = getNode(root, key);
        if(node == null) {throw new IllegalArgumentException(key + "doesn't exist!");
        }

        node.value = newValue;
    }

    // 返回以 node 为根的二分搜寻树的最小值所在的节点
    private Node minimum(Node node){if(node.left == null) {return node;}
        return minimum(node.left);
    }

    // 删除掉以 node 为根的二分搜寻树中的最小节点
    // 返回删除节点后新的二分搜寻树的根
    private Node removeMin(Node node){if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size --;
            return rightNode;
        }

        node.left = removeMin(node.left);
        return node;
    }

    // 从二分搜寻树中删除键为 key 的节点
    public V remove(K key){Node node = getNode(root, key);
        if(node != null){root = remove(root, key);
            return node.value;
        }
        return null;
    }

    private Node remove(Node node, K key){if( node == null) {return null;}

        if(key.compareTo(node.key) < 0 ){node.left = remove(node.left , key);
            return node;
        }
        else if(key.compareTo(node.key) > 0 ){node.right = remove(node.right, key);
            return node;
        }
        else{// key.compareTo(node.key) == 0

            // 待删除节点左子树为空的状况
            if(node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size --;
                return rightNode;
            }

            // 待删除节点右子树为空的状况
            if(node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size --;
                return leftNode;
            }

            // 待删除节点左右子树均不为空的状况

            // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            // 用这个节点顶替待删除节点的地位
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;

            return successor;
        }
    }

}

二分搜寻树性质和平衡性

判断该树是否是一颗二分搜寻树

所谓的二分搜寻树，就是任意一个节点满足，大于左孩子，小于右孩子。所以二分搜寻树满足这样的一个性质：中序遍历之后的二叉树是程序的。所以咱们这里实现的思路是，改写二叉树的非递归版本的，来校验以后值和前一个值的大小关系。

    // 判断该二叉树是否是一颗二分搜寻树
    public boolean isBST() {List<K> keys = new ArrayList<>();
        inOrder(root, keys);
        for (int i = 0; i < keys.size(); i++) {if (keys.get(i - 1).compareTo(keys.get(i)) > 0) {return false;}
        }
        return true;
    }

    private void inOrder(Node node, List<K> keys) {if (node == null) {return;}
        inOrder(node.left, keys);
        keys.add(node.key);
        inOrder(node.right, keys);
    }

判断该树是否是一颗均衡二叉树

  • 1. 判断以根结点的树是否为均衡二叉树。求出左右子树的高度，判断它们的高度差是否超过了 1。
  • 2. 递归判断根的左子树是否为均衡二叉树
  • 3. 递归判断根的右子树是否为均衡二叉树
    留神：空树也是均衡二叉树
     // 判断该二叉树是否是一颗均衡二叉树
    public boolean isBalanced() {return isBalanced(root);
    }

    // 判断以 Node 为根的二叉树是否是一颗均衡二叉树，递归算法
    private boolean isBalanced(Node node) {if (node == null) {return true;}
        int balanceFactor = getBalanceFactor(node);
        if (Math.abs(balanceFactor) > 1) {return false;}
        return isBalanced(node.left) && isBalanced(node.right);
    }

旋转操作的基本原理

咱们在插入数据的时候可能会突破平衡性，所以咱们须要沿着节点向上保护平衡性。

在什么时候保护均衡？

在一开始，咱们增加一个节点 12，均衡因子是 0。

而后增加一个节点 8，这时候均衡因子是 0，而 12 的均衡因子是 1。

而后增加一个节点 5，这时候均衡因子是 0，而 8 的均衡因子是 1，12 的均衡因子就变为了 2。

这时候就不再是均衡二叉树。

右旋（LL）

  1. 根节点（Y）的左孩子代表根节点
  2. （X）节点的右子树变为（Y）的左子树
  3. 将此节点（Y）变为（X）根节点的右子树

代码逻辑为：

x.right = y
y.left = T3

动图援用于此

具体动画演示如下：

当旋转之后，咱们这棵树仍旧放弃二分搜寻树和均衡二叉树的性质。

    // 向以 node 为根的二分搜寻树中插入元素(key, value)，递归算法
    // 返回插入新节点后二分搜寻树的根
    private Node add(Node node, K key, V value) {if (node == null) {
            size++;
            return new Node(key, value);
        }

        if (key.compareTo(node.key) < 0) {node.left = add(node.left, key, value);
        } else if (key.compareTo(node.key) > 0) {node.right = add(node.right, key, value);
        } else // key.compareTo(node.key) == 0
        {node.value = value;}

        // 更新 height
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

        // 计算均衡因子
        int balanceFactor = getBalanceFactor(node);
        if (Math.abs(balanceFactor) > 1) {System.out.println("unbalanced :" + balanceFactor);
        }

        // 均衡保护
        if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {return rightRotate(node);
        }

        return node;
    }

    // 对节点 y 进行向右旋转操作，返回旋转后新的根节点 x
    //        y                              x
    //       / \                           /   \
    //      x   T4     向右旋转 (y)        z     y
    //     / \       - - - - - - - ->    / \   / \
    //    z   T3                       T1  T2 T3 T4
    //   / \
    // T1   T2
    private Node rightRotate(Node y) {
        Node x = y.left;
        Node t3 = x.right;
        x.right = y;
        y.left = t3;
        // 更新 x 和 y 的高度
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
        return x;
    }

左旋（RR）

  1. 根节点（Y）的右孩子代替根节点地位
  2. （X）的左子树变为（Y）的右子树
  3. （Y）自身变为（X）的左子树

代码逻辑为：

x.left = y;
y.right = t3;

动图如下：

LR 和 RL

LR 的状况

如下图这样的状况，咱们插入一个节点 10，这个时候 10 和 12 都比 8 大，咱们不论是应用 LL 还是 RR 都无奈达到成果。

咱们首先能够对 x 节点进行左旋，失去如下图所示，这样我就会发现以后树结构曾经变成了 LL 的状况，咱们进行右旋即可。

动图演示：

RL 的状况

RL 和 LR 其实是对称的关系。

咱们首先将 x 进行右旋，而后转换为 RR 的状况，再进行左旋即可。

    // 向以 node 为根的二分搜寻树中插入元素(key, value)，递归算法
    // 返回插入新节点后二分搜寻树的根
    private Node add(Node node, K key, V value) {if (node == null) {
            size++;
            return new Node(key, value);
        }

        if (key.compareTo(node.key) < 0) {node.left = add(node.left, key, value);
        } else if (key.compareTo(node.key) > 0) {node.right = add(node.right, key, value);
        } else // key.compareTo(node.key) == 0
        {node.value = value;}

        // 更新 height
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

        // 计算均衡因子
        int balanceFactor = getBalanceFactor(node);
        if (Math.abs(balanceFactor) > 1) {System.out.println("unbalanced :" + balanceFactor);
        }

        // 均衡保护  LL
        if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {return rightRotate(node);
        }
        // 均衡保护  RR
        if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {return leftRotate(node);
        }
        // 均衡保护  LR
        if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // 均衡保护  RL
        if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

从 AVL 中删除元素

删除和增加代码相似，具体也是删除元素后进行均衡保护。

    // 从二分搜寻树中删除键为 key 的节点
    public V remove(K key) {Node node = getNode(root, key);
        if (node != null) {root = remove(root, key);
            return node.value;
        }
        return null;
    }

    private Node remove(Node node, K key) {if (node == null) {return null;}
        Node retNode;
        if (key.compareTo(node.key) < 0) {node.left = remove(node.left, key);
            retNode = node;
        } else if (key.compareTo(node.key) > 0) {node.right = remove(node.right, key);
            retNode = node;
        } else {// key.compareTo(node.key) == 0

            // 待删除节点左子树为空的状况
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                retNode = rightNode;
            }
            // 待删除节点右子树为空的状况
            else if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                retNode = leftNode;
            } else {
                // 待删除节点左右子树均不为空的状况
                // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
                // 用这个节点顶替待删除节点的地位
                Node successor = minimum(node.right);
                successor.right = remove(node.right, successor.key);
                successor.left = node.left;
                node.left = node.right = null;
                retNode = successor;
            }
        }

        if(retNode == null){return null;}

        // 更新 height
        retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));

        // 计算均衡因子
        int balanceFactor = getBalanceFactor(retNode);
        if (Math.abs(balanceFactor) > 1) {System.out.println("unbalanced :" + balanceFactor);
        }

        // 均衡保护  LL
        if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) {return rightRotate(retNode);
        }
        // 均衡保护  RR
        if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) {return leftRotate(retNode);
        }
        // 均衡保护  LR
        if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {node.left = leftRotate(retNode.left);
            return rightRotate(retNode);
        }

        // 均衡保护  RL
        if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {node.right = rightRotate(retNode.right);
            return leftRotate(retNode);
        }
        return retNode;
    }

正文完
java
发表至： java
2020-08-17
 0
一次和前端的相互甩锅的问题记录
JUC并发包背后的那些事儿
即时通讯之服务端篇Tigase
Spring-Data-JPA中的getOnefindOne以及findById