乐趣区

关于算法-数据结构:看动画学算法之平衡二叉搜索树AVL-Tree

作者：

jiezi

在

简介

均衡二叉搜寻树是一种非凡的二叉搜寻树。为什么会有均衡二叉搜寻树呢？

考虑一下二叉搜寻树的非凡状况，如果一个二叉搜寻树所有的节点都是右节点，那么这个二叉搜寻树将会进化成为链表。从而导致搜寻的工夫复杂度变为O(n),其中n是二叉搜寻树的节点个数。

而均衡二叉搜寻树正是为了解决这个问题而产生的，它通过限度树的高度，从而将工夫复杂度升高为O(logn)。

AVL的个性

在探讨AVL的个性之前，咱们先介绍一个概念叫做均衡因子，均衡因子示意的是左子树和右子树的高度差。

如果均衡因子=0，示意这是一个齐全均衡二叉树。

如果均衡因子=1，那么这棵树就是均衡二叉树AVL。

也就是是说AVL的均衡因子不可能大于1。

先看一个AVL的例子：

总结一下，AVL首先是一个二叉搜寻树，而后又是一个二叉均衡树。

AVL的构建

有了AVL的个性之后，咱们看下AVL是怎么构建的。

public class AVLTree {

    //根节点
    Node root;

    class Node {
        int data; //节点的数据
        int height; //节点的高度
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

同样的，AVL也是由各个节点形成的，每个节点领有data，left和right几个属性。

因为是二叉均衡树，节点是否均衡还跟节点的高度无关，所以咱们还须要定义一个height作为节点的高度。

在来两个辅助的办法，一个是获取给定的节点高度：

//获取给定节点的高度
    int height(Node node) {
        if (node == null)
            return 0;
        return node.height;
    }

和获取均衡因子：

//获取均衡因子
    int getBalance(Node node) {
        if (node == null)
            return 0;
        return height(node.left) - height(node.right);
    }

AVL的搜寻

AVL的搜寻和二叉搜寻树的搜寻形式是统一的。

先看一个直观的例子，怎么在AVL中搜寻到7这个节点：

搜寻的根本步骤是：

  1. 从根节点15登程，比拟根节点和搜寻值的大小
  2. 如果搜寻值小于节点值，那么递归搜寻左侧树
  3. 如果搜寻值大于节点值，那么递归搜寻右侧树
  4. 如果节点匹配，则间接返回即可。

相应的java代码如下：

//搜寻办法，默认从根节点搜寻
    public Node search(int data){
        return search(root,data);
    }

    //递归搜寻节点
    private Node search(Node node, int data)
    {
        // 如果节点匹配，则返回节点
        if (node==null || node.data==data)
            return node;

        // 节点数据大于要搜寻的数据，则持续搜寻右边节点
        if (node.data > data)
            return search(node.left, data);

        // 如果节点数据小于要搜素的数据，则持续搜寻左边节点
        return search(node.right, data);
    }

AVL的插入

AVL的插入和BST的插入是一样的，不过插入之后有可能会导致树不再均衡，所以咱们须要做一个再均衡的步骤。

看一个直观的动画：

插入的逻辑是这样的：

  1. 从根节点登程，比拟节点数据和要插入的数据
  2. 如果要插入的数据小于节点数据，则递归左子树插入
  3. 如果要插入的数据大于节点数据，则递归右子树插入
  4. 如果根节点为空，则插入以后数据作为根节点

插入数据之后，咱们须要做再均衡。

再均衡的逻辑是这样的：

  1. 从插入的节点向上找出第一个未均衡的节点，这个节点咱们记为z
  2. 对z为根节点的子树进行旋转，失去一个均衡树。

依据以z为根节点的树的不同，咱们有四种旋转形式：

  • left-left：

如果是left left的树，那么进行一次右旋就够了。

右旋的步骤是怎么样的呢？

  1. 找到z节点的左节点y
  2. 将y作为旋转后的根节点
  3. z作为y的右节点
  4. y的右节点作为z的左节点
  5. 更新z的高度

相应的代码如下：

Node rightRotate(Node node) {
        Node x = node.left;
        Node y = x.right;

        // 右旋
        x.right = node;
        node.left = y;

        // 更新node和x的高度
        node.height = max(height(node.left), height(node.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;

        // 返回新的x节点
        return x;
    }
  • right-right:

如果是right-right模式的树，须要通过一次左旋：

左旋的步骤正好和右旋的步骤相同：

  1. 找到z节点的右节点y
  2. 将y作为旋转后的根节点
  3. z作为y的左节点
  4. y的左节点作为z的右节点
  5. 更新z的高度

相应的代码如下：

//左旋
    Node leftRotate(Node node) {
        Node x = node.right;
        Node y = x.left;

        //左旋操作
        x.left = node;
        node.right = y;

        // 更新node和x的高度
        node.height = max(height(node.left), height(node.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;

        // 返回新的x节点
        return x;
    }
  • left-right：

如果是left right的状况，须要先进行一次左旋将树转变成left left格局，而后再进行一次右旋，失去最终后果。

  • right-left：

如果是right left格局，须要先进行一次右旋，转换成为right right格局，而后再进行一次左旋即可。

当初问题来了，怎么判断一个树到底是哪种格局呢？咱们能够通过获取均衡因子和新插入的数据比拟来判断：

  1. 如果balance>1,那么咱们在Left Left或者left Right的状况，这时候咱们须要比拟新插入的data和node.left.data的大小

    如果data < node.left.data，示意是left left的状况，只须要一次右旋即可

    如果data > node.left.data，示意是left right的状况，则须要将node.left进行一次左旋，而后将node进行一次右旋

  2. 如果balance<-1,那么咱们在Right Right或者Right Left的状况，这时候咱们须要比拟新插入的data和node.right.data的大小
    如果data > node.right.data，示意是Right Right的状况，只须要一次左旋即可

    如果data < node.left.data，示意是Right left的状况，则须要将node.right进行一次右旋，而后将node进行一次左旋

插入节点的最终代码如下：

//插入新节点，从root开始
    public void insert(int data){
        root=insert(root, data);
    }

    //遍历插入新节点
    Node insert(Node node, int data) {

        //先依照一般的BST办法插入节点
        if (node == null)
            return (new Node(data));

        if (data < node.data)
            node.left = insert(node.left, data);
        else if (data > node.data)
            node.right = insert(node.right, data);
        else
            return node;

        //更新节点的高度
        node.height = max(height(node.left), height(node.right)) + 1;

        //判断节点是否均衡
        int balance = getBalance(node);

        //节点不均衡有四种状况
        //1.如果balance>1,那么咱们在Left Left或者left Right的状况，这时候咱们须要比拟新插入的data和node.left.data的大小
        //如果data < node.left.data，示意是left left的状况，只须要一次右旋即可
        //如果data > node.left.data，示意是left right的状况，则须要将node.left进行一次左旋，而后将node进行一次右旋
        //2.如果balance<-1,那么咱们在Right Right或者Right Left的状况，这时候咱们须要比拟新插入的data和node.right.data的大小
        //如果data > node.right.data，示意是Right Right的状况，只须要一次左旋即可
        //如果data < node.left.data，示意是Right left的状况，则须要将node.right进行一次右旋，而后将node进行一次左旋

        //left left
        if (balance > 1 && data < node.left.data)
            return rightRotate(node);

        // Right Right
        if (balance < -1 && data > node.right.data)
            return leftRotate(node);

        // Left Right
        if (balance > 1 && data > node.left.data) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // Right Left
        if (balance < -1 && data < node.right.data) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        //返回插入后的节点
        return node;
    }

AVL的删除

AVL的删除和插入相似。

首先依照一般的BST删除，而后也须要做再均衡。

看一个直观的动画：

删除之后，节点再均衡也有4种状况：

  1. 如果balance>1,那么咱们在Left Left或者left Right的状况，这时候咱们须要比拟左节点的均衡因子

    如果左节点的均衡因子>=0，示意是left left的状况，只须要一次右旋即可

    如果左节点的均衡因<0，示意是left right的状况，则须要将node.left进行一次左旋，而后将node进行一次右旋

  2. 如果balance<-1,那么咱们在Right Right或者Right Left的状况，这时候咱们须要比拟右节点的均衡因子

    如果右节点的均衡因子<=0，示意是Right Right的状况，只须要一次左旋即可

    如果右节点的均衡因子>0，示意是Right left的状况，则须要将node.right进行一次右旋，而后将node进行一次左旋

相应的代码如下：

Node delete(Node node, int data)
    {
        //Step 1. 一般BST节点删除
        // 如果节点为空，间接返回
        if (node == null)
            return node;

        // 如果值小于以后节点，那么持续左节点删除
        if (data < node.data)
            node.left = delete(node.left, data);

        //如果值大于以后节点，那么持续右节点删除
        else if (data > node.data)
            node.right = delete(node.right, data);

       //如果值雷同，那么就是要删除的节点
        else
        {
            // 如果是单边节点的状况
            if ((node.left == null) || (node.right == null))
            {
                Node temp = null;
                if (temp == node.left)
                    temp = node.right;
                else
                    temp = node.left;

                //没有子节点的状况
                if (temp == null)
                {
                    node = null;
                }
                else // 单边节点的状况
                    node = temp;
            }
            else
            {  //非单边节点的状况
                //拿到右侧节点的最小值
                Node temp = minValueNode(node.right);
                //将最小值作为以后的节点值
                node.data = temp.data;
                // 将该值从右侧节点删除
                node.right = delete(node.right, temp.data);
            }
        }

        // 如果节点为空，间接返回
        if (node == null)
            return node;

        // step 2: 更新以后节点的高度
        node.height = max(height(node.left), height(node.right)) + 1;

        // step 3: 获取以后节点的均衡因子
        int balance = getBalance(node);

        // 如果节点不再均衡，那么有4种状况
        //1.如果balance>1,那么咱们在Left Left或者left Right的状况，这时候咱们须要比拟左节点的均衡因子
        //如果左节点的均衡因子>=0，示意是left left的状况，只须要一次右旋即可
        //如果左节点的均衡因<0，示意是left right的状况，则须要将node.left进行一次左旋，而后将node进行一次右旋
        //2.如果balance<-1,那么咱们在Right Right或者Right Left的状况，这时候咱们须要比拟右节点的均衡因子
        //如果右节点的均衡因子<=0，示意是Right Right的状况，只须要一次左旋即可
        //如果右节点的均衡因子>0，示意是Right left的状况，则须要将node.right进行一次右旋，而后将node进行一次左旋
        // Left Left Case
        if (balance > 1 && getBalance(node.left) >= 0)
            return rightRotate(node);

        // Left Right Case
        if (balance > 1 && getBalance(node.left) < 0)
        {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // Right Right Case
        if (balance < -1 && getBalance(node.right) <= 0)
            return leftRotate(node);

        // Right Left Case
        if (balance < -1 && getBalance(node.right) > 0)
        {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }

本文的代码地址：

learn-algorithm

本文收录于 http://www.flydean.com/11-algorithm-avl-tree/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！

欢送关注我的公众号:「程序那些事」,懂技术，更懂你！

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章