12.数据结构之AVL树

前言

提到平衡二叉查找树，不得不提二叉查找树。二叉查找树，说简单点，其实就是将我们的数据节点，有序的维护为一个树形结构。这样我们查的时候，那么我们查找某个节点在不在集合中的时间复杂度实际上就是树的高度。如果节点在根节点左右均匀分布，那么维护的树的高度就会最低。

本节，我会详细介绍如何将一个不平衡的二叉树重新平衡。

1. 概念

1.1 平衡二叉树

平衡二叉树(Self-Balancing Binary Search Tree或Height-Balanced Binary SearchTree)，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。也就是说，平衡二叉树要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。

有两位俄罗斯数学家GMAdelson-Velskii和EMLandis在1962年共同发明一种解决平衡二叉树的算法，所以有不少资料中也称这样的平衡二叉树为AVL树。

在这里插入图片描述
如上图举例所示：

  1. 图1 是平衡二叉树，因为每个节点左右字树差值都不超过1
  2. 图二不是平衡二叉树，是因为树首先得是二叉排序树，才能是平衡二叉树，但是图二 59 大于 58 ，不应该在58 的左子节点
  3. 图3 不是平衡二叉树，是因为插入37 后，节点58 左子树减去右子树高度为2，不满足条件
  4. 图4 是平衡二叉树

1.2 平衡因子

我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF(BalanceFactor)，那么平衡叉树上所有结点的平衡因子只可能是-1、0和1，只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

1.3 最小不平衡子树

距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。由此可得，在上面的图3中，最小不平衡子树是58 以下的子树。
在这里插入图片描述

2. 实现原理

平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。

我们以数组节点{3，2，1，4，5，6，7，10，9，8}为例，构造平衡二叉树：

  1. 对于数组a[10]={3,2,1,5,710,9,8的前两位3和2我们很正常地构建到了第3个数“1”时，发现此时根结点“3”的平衡因子变成了2，此时整棵树都成了最小不平衡子树，因此需要调整如图1 (结点左上角数字为平衡因子BF值)。因为BF值为正，因此我们将整个树进行右旋(顺时针旋转)，此时结点2成了根结点，3成了2的右孩子，这样三个结点的BF值均为0非常的平衡，如图2所示。
    在这里插入图片描述
  2. 然后我们再增加结点4，平衡因子没发生改变，如图3。增加结点5时，结点3的BF值为-2，说明要旋转了。由于BF是负值，所以我们对这棵最小平衡子树进行左旋(逆时针旋转)，如图4，此时我们整个树又达到了平衡。

在这里插入图片描述

  1. 继续增加结点6时，发现根结点2的BF值变成了-2,。如图6，所以我们对根结点进行了左旋，注意此时本来结点3是4的左孩子，由于旋转后需要满足二叉排序树特性，因此它成了结点2的右孩子，如图7。增加结点7，同样的左旋转，使得整棵树达到平衡，如图8和图9所示。
    在这里插入图片描述

  2. 当增加结点10时，结构无变化，如图10。再增加结点9，此时结点7的BF变成了-2，理论上我们只需要旋转最小不平衡子树7，9，10即可，但是如果左旋转后，结点9就成了10的右孩子，这是不符合二叉排序树的特性，此时不能简单的左旋，如图11所示。
    在这里插入图片描述

  3. 仔细观察图11，发现根本原因在于结点7的BF是-2而结点10的BF是1也就是说，它们俩一正一负，符号并不统一，而前面的几次旋转，无论左还是右旋最小不平衡子树的根结点与它的子结点符号都是相同的。这就是不能直接旋转的关键。那怎么办呢?

    不统一，不统一就把它们先转到符号统一再说，于是我们先对结点9和结点10进行右旋使得结点10成了9的右子树，结点9的BF为-1，此时就与结点7的BF值符号统一了，如图12所示。

  4. 这样我们再以结点7为最小不平衡子树进行左旋，得到图13。接着插入8，情况与刚才类似，结点6的BF是-2，而它的右孩子9的BF是1，如图14，因此首先以9为根结点，进行右旋，得到图15，此时结点6和结点7的符号都是负，再以6为根结点左旋，最终得到最后的平衡二叉树，如图16所示。
    在这里插入图片描述

通过刚才这个例子，你会发现，所谓的平衡二叉树，其实就是在二叉排序树创建过程中保证它的平衡性，一旦发现有不平衡的情况，马上处理，这样就不会造成不可收拾的情况出现。

当最小不平衡子树根结点的平衡因子BF是大于1时，就右旋，小于-1时就左旋，如上例中结点1、5、6、7的插入等。插入结点后，最小不平衡子树的BF与它的子树的BF符号相反时就需要对结点先进行一次旋转以使得符号相同后，再反向旋转一次才能够完成平衡操作，如上例中结点9、8的插入时。

3. 代码实现

3.1 定义树节点和树类

3.1.1 定义AVL树节点类

package org.wanlong.tree;

/**
 * @author wanlong
 * @version 1.0
 * @description: 平衡二叉树节点
 * @date 2023/6/5 19:03
 */
public class AVLNode<T> {

    //数据
    T data;
    //左孩子
    AVLNode<T> left;
    //右孩子
    AVLNode<T> right;

    //高度
    int height;


    public AVLNode(T data) {
        this.data = data;
    }
}

3.1.2 定义平衡树类

package org.wanlong.tree;

/**
 * @author wanlong
 * @version 1.0
 * @description: 平衡二叉查找树
 * @date 2023/6/1 15:47
 */
public class AVLTree<T extends Comparable<? super T>> {

    //根节点
    private AVLNode<T> root;

    //允许最大的不平衡因子
    private static final int ALLOWED_IMBALANCE = 1;

    //返回树的高度
    private int height(AVLNode<T> t) {
        return t == null ? -1 : t.height;
    }
    public boolean isEmpty() {
        return root == null;
    }

    public void makeEmpty() {
        root = null;
    }

    public T findMin() {
        return findMin(root).data;
    }

    public T findMax() {
        return findMax(root).data;
    }

    /**
     * @param root:
     * @return org.wanlong.tree.AVLNode<T>
     * @Description:找最小节点
     * @Author: wanlong
     * @Date: 2023/6/5 20:00
     **/
    private AVLNode<T> findMin(AVLNode<T> root) {
        if (root == null) {
            return null;
        } else if (root.left == null) {
            return root;
        }
        return findMin(root.left);
    }

    /**
     * @param root:
     * @return org.wanlong.tree.AVLNode<T>
     * @Description:找最大节点
     * @Author: wanlong
     * @Date: 2023/6/5 19:30
     **/
    private AVLNode<T> findMax(AVLNode<T> root) {
        if (root == null) {
            return null;
        } else if (root.right == null) {
            return root;
        } else {
            return findMax(root.right);
        }
    }


    /**
     * @return void
     * @Description: 打印
     * @Author: wanlong
     * @Date: 2023/6/5 19:31
     **/
    public void printTree() {
        if (isEmpty()) {
            System.out.println("节点为空");
        } else {
            printTree(root);
        }
    }

    /**
     * @return void
     * @Description: 打印
     * @Author: wanlong
     * @Date: 2023/6/5 19:31
     **/
    public void printTree(AVLNode<T> root) {
        if (root != null) {
            System.out.print(root.data);
            if (null != root.left) {
                System.out.print("左边节点" + root.left.data);
            }
            if (null != root.right) {
                System.out.print("右边节点" + root.right.data);
            }
            System.out.println();
            printTree(root.left);
            printTree(root.right);
        }
    }
}

3.2 右旋RR

在这里插入图片描述

3.2.1 思路

如图所示。当传入一个二叉排序树P

  1. 将它的左孩子结点定义为L,将L的右子树变成P的左子树
  2. 将P改成L的右子树
  3. 将L替换P成为根结点
  4. 重新计算树的高度
  5. 这样就完成了一次右旋操作，图中三角形代表子树，N代表新增结点。调整完后，需要重新计算树的高度。

3.2.2 代码

/**
 * @param p: 最小不平衡子树
 * @return void
 * @Description:右旋
 * @Author: wanlong
 * @Date: 2023/6/5 18:36
 **/
AVLNode<T> rightRotate(AVLNode p) {
    AVLNode k1 = p.left;
    p.left = k1.right;
    k1.right = p;
    p.height = Math.max(height(p.left), height(p.right)) + 1;
    k1.height = Math.max(height(k1.left), p.height) + 1;
    return k1;
}

3.3 左旋LL

在这里插入图片描述

3.3.1 思路

左旋和右旋相反，代码类似。

3.3.2 代码

 /**
  * @param k2:最小不平衡子树
  * @return void
  * @Description:左旋
  * @Author: wanlong
  * @Date: 2023/6/5 18:46
  **/
 AVLNode<T> leftRotate(AVLNode k2) {
     AVLNode k1 = k2.right;
     k2.right = k1.left;
     k1.left = k2;
     k2.height = Math.max(height(k2.right), height(k2.left)) + 1;
     k1.height = Math.max(height(k1.right), k2.height) + 1;
     return k1;
 }

3.4 双旋LR

从之前的案例可以看到，当最小不平衡子树的根节点平衡因子为正，而它的左节点平衡因子是负的时候，此时需要进行双旋LR。

3.4.1 思路

在LR旋转中，我们需要先左旋，再右旋，左旋是保证节点的符号相同

3.4.2 代码

    /**
     * @param k2:
     * @return org.wanlong.tree.AVLNode<T>
     * @Description: LR型双旋转 先左旋，再右旋
     * @Author: wanlong
     * @Date: 2023/6/5 19:15
     **/
    AVLNode<T> leftRightRotate(AVLNode k2) {
        k2.left = leftRotate(k2.left);
        return rightRotate(k2);
    }

3.5 双旋RL

从之前的案例可以看到，当最小不平衡子树的根节点平衡因子为负，而它的右节点平衡因子是正的时候，此时需要进行双旋RL。

3.5.1 思路

在RL旋转中，我们需要先右旋，再左旋，右旋是保证节点的符号相同

3.5.2 代码

    /**
     * @param k2:
     * @return org.wanlong.tree.AVLNode<T>
     * @Description: RL型双旋转 先右旋，再左旋
     * @Author: wanlong
     * @Date: 2023/6/5 19:15
     **/
    AVLNode<T> rightLeftRotate(AVLNode k2) {
        k2.right = rightRotate(k2.right);
        return leftRotate(k2);
    }

3.6 完整代码

package org.wanlong.tree;

/**
 * @author wanlong
 * @version 1.0
 * @description: 平衡二叉查找树
 * @date 2023/6/1 15:47
 */
public class AVLTree<T extends Comparable<? super T>> {

    //根节点
    private AVLNode<T> root;

    //允许最大的不平衡因子
    private static final int ALLOWED_IMBALANCE = 1;

    //返回树的高度
    private int height(AVLNode<T> t) {
        return t == null ? -1 : t.height;
    }

    public boolean isEmpty() {
        return root == null;
    }

    public void makeEmpty() {
        root = null;
    }

    public T findMin() {
        return findMin(root).data;
    }

    public T findMax() {
        return findMax(root).data;
    }

    //插入节点
    public void insert(T x) {
        root = insert(x, root);
    }

    //删除节点
    public void remove(T x) {
        root = remove(x, root);
    }

    //以某节点为根节点，删除子树的对应节点
    private AVLNode<T> remove(T x, AVLNode<T> t) {

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

        int compareResult = x.compareTo(t.data);

        //小于当前根节点
        if (compareResult < 0) {
            t.left = remove(x, t.left);
        } else if (compareResult > 0) {
            //大于当前根节点
            t.right = remove(x, t.right);
        } else if (t.left != null && t.right != null) {
            //找到右边最小的节点
            t.data = findMin(t.right).data;
            //当前节点的右边等于原节点右边删除已经被选为的替代节点
            t.right = remove(t.data, t.right);
        } else {
            t = (t.left != null) ? t.left : t.right;
        }
        return balance(t);
    }

    //以某节点为根节点，插入子树的对应节点
    private AVLNode<T> insert(T x, AVLNode<T> t) {

        //如果根节点为空，则当前x节点为根及诶单
        if (null == t) {
            return new AVLNode(x);
        }

        int compareResult = x.compareTo(t.data);

        //小于当前根节点 将x插入根节点的左边
        if (compareResult < 0) {
            t.left = insert(x, t.left);
        } else if (compareResult > 0) {
            //大于当前根节点 将x插入根节点的右边
            t.right = insert(x, t.right);
        } else {

        }
        return balance(t);
    }


    /**
     * @param t:
     * @return org.wanlong.tree.AVLNode<T>
     * @Description: 平衡节点方法
     * @Author: wanlong
     * @Date: 2023/6/5 19:58
     **/
    private AVLNode<T> balance(AVLNode<T> t) {
        if (t == null) {
            return t;
        }
        //左子树大于右子树 ，平衡因子大于1
        if (height(t.left) - height(t.right) > ALLOWED_IMBALANCE) {
            //左子树的左子树高度大于左子树的右子树高度 即根节点左节点的平衡因子和根节点一致 直接右旋
            if (height(t.left.left) >= height(t.left.right)) {
                t = rightRotate(t);
            } else {
                //左子树的左子树高度小于左子树的右子树高度 即根节点左节点的平衡因子为负数，和根节点相反 ，此时需要先左旋，再右旋
                t = leftRightRotate(t);
            }
            //右子树高度 大于 左子树，平衡因子小于 -1
        } else if (height(t.right) - height(t.left) > ALLOWED_IMBALANCE) {
            //右子树的右子树高度 大于 右子树的左子树高度 ，根节点右节点的平衡因子和根节点一致，直接左旋
            if (height(t.right.right) >= height(t.right.left)) {
                t = leftRotate(t);
            } else {
                //右子树的右子树高度 小于 右子树的左子树高度 ，根节点右节点的平衡因子和根节点相反，先右旋，再左旋
                t = rightLeftRotate(t);
            }
        }
        //重新计算树的高度
        t.height = Math.max(height(t.left), height(t.right)) + 1;
        return t;
    }


    /**
     * @param p: 最小不平衡子树
     * @return void
     * @Description:右旋
     * @Author: wanlong
     * @Date: 2023/6/5 18:36
     **/
    AVLNode<T> rightRotate(AVLNode p) {
        AVLNode k1 = p.left;
        p.left = k1.right;
        k1.right = p;
        p.height = Math.max(height(p.left), height(p.right)) + 1;
        k1.height = Math.max(height(k1.left), p.height) + 1;
        return k1;
    }


    /**
     * @param k2:最小不平衡子树
     * @return void
     * @Description:左旋
     * @Author: wanlong
     * @Date: 2023/6/5 18:46
     **/
    AVLNode<T> leftRotate(AVLNode k2) {
        AVLNode k1 = k2.right;
        k2.right = k1.left;
        k1.left = k2;
        k2.height = Math.max(height(k2.right), height(k2.left)) + 1;
        k1.height = Math.max(height(k1.right), k2.height) + 1;
        return k1;
    }

    /**
     * @param k2:
     * @return org.wanlong.tree.AVLNode<T>
     * @Description: LR型双旋转 先左旋，再右旋
     * @Author: wanlong
     * @Date: 2023/6/5 19:15
     **/
    AVLNode<T> leftRightRotate(AVLNode k2) {
        k2.left = leftRotate(k2.left);
        return rightRotate(k2);
    }

    /**
     * @param k2:
     * @return org.wanlong.tree.AVLNode<T>
     * @Description: RL型双旋转 先右旋，再左旋
     * @Author: wanlong
     * @Date: 2023/6/5 19:15
     **/
    AVLNode<T> rightLeftRotate(AVLNode k2) {
        k2.right = rightRotate(k2.right);
        return leftRotate(k2);
    }


    /**
     * @param root:
     * @return org.wanlong.tree.AVLNode<T>
     * @Description:找最小节点
     * @Author: wanlong
     * @Date: 2023/6/5 20:00
     **/
    private AVLNode<T> findMin(AVLNode<T> root) {
        if (root == null) {
            return null;
        } else if (root.left == null) {
            return root;
        }
        return findMin(root.left);
    }

    /**
     * @param root:
     * @return org.wanlong.tree.AVLNode<T>
     * @Description:找最大节点
     * @Author: wanlong
     * @Date: 2023/6/5 19:30
     **/
    private AVLNode<T> findMax(AVLNode<T> root) {
        if (root == null) {
            return null;
        } else if (root.right == null) {
            return root;
        } else {
            return findMax(root.right);
        }
    }


    /**
     * @return void
     * @Description: 打印
     * @Author: wanlong
     * @Date: 2023/6/5 19:31
     **/
    public void printTree() {
        if (isEmpty()) {
            System.out.println("节点为空");
        } else {
            printTree(root);
        }
    }

    /**
     * @return void
     * @Description: 打印
     * @Author: wanlong
     * @Date: 2023/6/5 19:31
     **/
    public void printTree(AVLNode<T> root) {
        if (root != null) {
            System.out.print(root.data);
            if (null != root.left) {
                System.out.print("左边节点" + root.left.data);
            }
            if (null != root.right) {
                System.out.print("右边节点" + root.right.data);
            }
            System.out.println();
            printTree(root.left);
            printTree(root.right);
        }
    }
}

4. 测试验证

@Test
public void testAVLTree(){
    //3，2，1，4，5，6，7，10，9，8
    AVLTree<Integer> tree = new AVLTree<>();
    int[] array=new int[]{3,2,1,4,5,6,7,10,9,8};
    for (int i : array) {
        tree.insert(i);
    }
    tree.printTree();
    System.out.println("=====");
    Integer min = tree.findMin();
    Integer max = tree.findMax();
    System.out.println("min:"+min);
    System.out.println("max:"+max);
}

代码运行结果：

4左边节点2右边节点7
2左边节点1右边节点3
1
3
7左边节点6右边节点9
6左边节点5
5
9左边节点8右边节点10
8
10
=====
min:1
max:10

可以看到，和下图预期结果一致：
在这里插入图片描述

5. 参考资料：

国外数据结构演示网站
大话数据结构图书
java实现AVL树

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/26071.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

HNU-操作系统OS-实验Lab7

HNU-操作系统OS-实验Lab7

OS_Lab7_Experimental report 湖南大学信息科学与工程学院 计科 210X wolf （学号 202108010XXX） 实验目的 理解操作系统的同步互斥的设计实现；理解底层支撑技术：禁用中断、定时器、等待队列；在ucore中理解信号量（semaphore）机制的具体实现；理解管程机制，在ucore内…
阅读更多...
在linux服务器中对R语言中for循环设置多核运行

在linux服务器中对R语言中for循环设置多核运行

1 问题 在R中构建了for循环&#xff0c;由于循环过多&#xff0c;运行速度过慢&#xff0c;且不同循环之间是并行关系&#xff0c;拟通过多核运行可以解决此问题。 2 代码设置 2.1 shell脚本中的设置 b.sh export OPENBLAS_NUM_THREADS8Rscript ./..._1.R \2.2 R代码中的设…
阅读更多...
python数据可视化-matplotlib学习总结

python数据可视化-matplotlib学习总结

目录 &#xff08;一&#xff09;常见的图形 1、趋势图&#xff08;直线图&#xff09;&#xff1a;plot&#xff08;&#xff09; 2、散点图&#xff1a;scatter(): (二&#xff09;统计图形 1、柱状图&#xff1a;bar( 2、条形图&#xff1a;barh() 3、直方图&#xff…
阅读更多...
【ZLM】ZLM源码阅读一

【ZLM】ZLM源码阅读一

目录 初始化 RTP RTSP RTMP TCPServer的初始化 参考文档 初始化 RTP RTSP RTMP TCPServer的初始化 参考文档 本文参考&#xff1a; (17条消息) 《ZLToolKit源码学习笔记》&#xff08;20&#xff09;网络模块之TcpServer_秦时小的博客-CSDN博客 RTP https://blog.csdn.…
阅读更多...
探秘 | 如何分辨内网和外网？

探秘 | 如何分辨内网和外网？

目录 &#x1f4a1; 什么是外网IP、内网IP&#xff1f; &#x1f4a1; 对于自有路由器上网的用户&#xff0c;可以这样理解外网IP、内网IP &#x1f4a1; 几个大家经常会问的问题 什么是外网IP、内网IP&#xff1f;很多用户都有一个疑惑&#xff0c;如果不使用路由器拨号上网…
阅读更多...
Redis实现分布式锁的原理：常见问题解析及解决方案、源码解析Redisson的使用

Redis实现分布式锁的原理：常见问题解析及解决方案、源码解析Redisson的使用

0、引言&#xff1a;分布式锁的引出 锁常常用于多线程并发的场景下保证数据的一致性&#xff0c;例如防止超卖、一人一单等场景需求 。通过加锁可以解决在单机情况下安全问题&#xff0c;但是在集群模式下就不行了。集群模式&#xff0c;即部署了多个服务器、并配置了负载均衡后…
阅读更多...
ChatGPT 使用 拓展资料：2023年6月 吴恩达大咖Deeplearning.ai最新课程

ChatGPT 使用 拓展资料：2023年6月 吴恩达大咖Deeplearning.ai最新课程

ChatGPT 使用 拓展资料：2023年6月 吴恩达大咖Deeplearning.ai最新课程 Deeplearning.ai刚刚发布几个新的课程https://www.deeplearning.ai/short-courses/?utm_campaign=May%20Short%20Course%20Launch&utm_content=250952287&utm_medium=social&utm_source=link…
阅读更多...
汽车出海势头旺，汽车零部件企业如何破浪前行？

汽车出海势头旺，汽车零部件企业如何破浪前行？

随着国内汽车市场逐渐饱和&#xff0c;中国汽车企业开始寻求“汽车出海”的新市场增长点。在政府加大汽车出海政策支持力度下&#xff0c;根据中汽协数据&#xff0c;一季度的新能源汽车出口达24.8万辆&#xff0c;同比增长1.1倍。中国汽车行业持续深耕海外市场&#xff0c;出口…
阅读更多...
SQL server入门一【简单介绍与简单建表】

SQL server入门一【简单介绍与简单建表】

SQLserver登录方式 Windows身份验证 用户名登录 通常登录名为sa&#xff0c;密码为下载时设置的密码 SQL server建立一个数据库 数据库中建表存储数据(输入命令建表) 数据库的简单介绍与概念 含义 可以对数据进行存储和管理的软件以及数据本身统称为数据库 组成 数据库由表…
阅读更多...
微服务架构之RPC调用

微服务架构之RPC调用

在单体应用时&#xff0c;一次服务调用发生在同一台机器上的同一个进程内部&#xff0c;也就是说调用发生在本机内部&#xff0c;因此也被叫作本地方法调用。在进行服务化拆分之后&#xff0c;服务提供者和服务消费者运行在两台不同物理机上的不同进程内&#xff0c;它们之间的…
阅读更多...
自建极简Ethercat主站-底层驱动编写

自建极简Ethercat主站-底层驱动编写

1、简介 MECM&#xff08;Mini Ethercat Master&#xff09;,名字随便起的。已经学习了一段时间的Ethercat总线了&#xff0c;目前的想法就是自己简单实现一个Ethercat主站&#xff0c;没有太多的冗余功能&#xff0c;暂时不考虑太多的容错机制&#xff0c;仅实现目前用到的FO…
阅读更多...
性能测试监控平台：InfluxDB+Grafana+Jmeter

性能测试监控平台：InfluxDB+Grafana+Jmeter

前言 性能测试工具jmeter自带的监视器对性能测试结果的实时展示&#xff0c;在Windows系统下的GUI模式运行&#xff0c;渲染和效果不是太好&#xff0c;在linux环境下又无法实时可视化。 2023年最新出炉性能测试教程&#xff0c;真实企业性能压测全流程项目实战训练大合集&am…
阅读更多...
整型在内存中的存储

整型在内存中的存储

目录 一、为什么内存中存储补码&#xff1f; 二、大小端概念 百度笔试试题&#xff1a; 几道小题&#xff1a; 一、为什么内存中存储补码&#xff1f; 上一节我们了解了原码&#xff0c;反码&#xff0c;补码的概念&#xff08;http://t.csdn.cn/N0grg&#xff09;&#xff…
阅读更多...
1-1 统计数字问题

1-1 统计数字问题

题目&#xff1a; 我的答案&#xff1a; 一、信息 二、分析 1.如何选择数据结构&#xff1f; 2.如何选择算法有很多思路&#xff1f; 3.如何用文件实现输入输出&#xff1f; 三、思考 疑问1 我选择了一开始数组选择使用数组是一个不错的选择&#xff0c;尤其在这个问题中…
阅读更多...
vulnhub dc-8

vulnhub dc-8

1.信息搜集 端口 22,80,31337 存活ip 192.168.85.136 2.访问网站&#xff0c;进行信息搜集 在欢迎页面发现sql注入 sqlmap进行跑数据 python sqlmap.py -u "http://192.168.85.136/?nid1" --batch -D d7db -T users -C name,pass --dump尝试robots.txt,发现后他登…
阅读更多...
生成程序片段(程序依赖图PDG)

生成程序片段(程序依赖图PDG)

生成程序片段(程序依赖图PDG) 生成程序片段 标准方法是&#xff1a; 基于依赖性分析的切片。 使用程序依赖图表示依赖。 从中生成切片。 我们将专注于这种方法。但是&#xff0c;还有其他选择。 程序依赖图 The Program Dependence Graph (PDG) 表示数据和控制依赖项&#xf…
阅读更多...
《深入理解计算机系统(CSAPP)》第7章 链接 - 学习笔记

《深入理解计算机系统(CSAPP)》第7章 链接 - 学习笔记

写在前面的话&#xff1a;此系列文章为笔者学习CSAPP时的个人笔记&#xff0c;分享出来与大家学习交流&#xff0c;目录大体与《深入理解计算机系统》书本一致。因是初次预习时写的笔记&#xff0c;在复习回看时发现部分内容存在一些小问题&#xff0c;因时间紧张来不及再次整理…
阅读更多...
java单元测试( Hamcrest 断言)

java单元测试( Hamcrest 断言)

java单元测试( Hamcrest 断言) 单元测试特征: 1 范围狭窄 2 限于单一类或方法 3 体积小 为什么要编写单元测试&#xff1f; 为了防止错误&#xff08;很明显&#xff01;&#xff09; 而且还可以提高开发人员的生产力&#xff0c;因为单元测试&#xff1a; (1) 帮助实施——在…
阅读更多...
力扣sql中等篇练习(二十八)

力扣sql中等篇练习(二十八)

力扣sql中等篇练习(二十八) 1 每个城市最高气温的第一天 1.1 题目内容 1.1.1 基本题目信息 1.1.2 示例输入输出 1.2 示例sql语句 # Write your MySQL query statement below SELECT w.city_id,MIN(w.day) day,w.degree FROM Weather w INNER JOIN (SELECT city_id,MAX(degr…
阅读更多...
【算法学习系列】07 - 无序数组中的局部最小值问题

【算法学习系列】07 - 无序数组中的局部最小值问题

文章目录 说明约束条件简单说下思路解决方案随机无序数组样本生成器算法实现验证代码进行大样本随机测试验证算法正确性 说明 在算法中&#xff0c;局部最小值是指一个函数在一个局部范围内的最小值。 具体而言&#xff0c;如果一个函数在一个小区间内的取值都比该区间内的其他…
阅读更多...
最新文章

Copyright @ 2022~2023