• 数据结构基础学习


    数据结构

    栈:

    • 特点:先进后出,后进先出

    队列:

    • 特点:从后端进去,前端出来。先进先出,后进后出

    数组

    • 特点:查询快,增删慢的模型,添加效率也低下
    • 查询:通过地址值或者索引值来查找,查询任意数据时间相同
    • 删除效率低下:删除某一个数据,同时后面的数据前面移动
    • 添加效率低下:添加位置后每一个数据后移,在添加元素

    链表

    • 每个数据都是一个结点(都是独立的对象,不连续),有一个地址值,包括元素和下一个结点的地址值。

    • 前一个结点记录后一个结点的地址值

    • 链表的查询比较慢,需要从头节点开始

    • 链表的增删快,只需要在对应位置,插上对应的数据的地址,和下一结点的地址值 即可



      树:

      • 节点:每一个元素
      image-20230909183936454

    节点详解:
    image-20230909184049898

    • 度:每一个节点的子节点数量称为度

    image-20230909184447543

    • 二叉树:每个节点最多有2个分支的树就是二叉树
    • 树的高度:为层数。层数从上到下
    • 根节点:最上层为根节点
    • 根节点的左子树:(蓝色虚线部分)
    • 根节点的右子节点:(红色实线部分)

    image-20230909185116271

    • 二叉查找树:

    image-20230909185354484

    • 特点:
      1.每个节点上最多有2个子节点
      2.每个节点的左子节点都小于节点
      3.每个节点的右子节点都大于节点

      • 添加节点规则:

        • 小的存左边,大的存右边,相等不存
      • 查找结点方法:和添加规则一样的


    二叉树的遍历方式:

    1.前序遍历:从根出发:根->左->右
    2.中序遍历:从左出发:左->中(当前结点)->右
    3.后续遍历:从左出发:左->右->中
    4.层序遍历:从根出发:根->左->右->下一层->根->左->右->

    平衡二叉树:

    • 规则:任意结点的左右子树高度差不超过1

      • 平衡二叉树的保持平衡的旋转机制
      • 触发时机:添加一个结点后,该树不是平衡二叉树
        1.左旋
        确定支点:从添加的结点一个个的向上寻找,找到不平衡的点
        旋转:将不平衡的点降级(左子节点),原来不平衡的点下个节点,晋级
      image-20230911104707577 image-20230911105105555

      ​ 多种情况:找到不平衡点,将不平衡的右子节点晋升,不平衡点降级,原来的不平衡点的右子节点的左节点,变为不平衡的点的右子节点
      image-20230911105325204
      image-20230911105424289

      2.右旋

      确定支点:从添加的结点一个个的向上寻找,找到不平衡的点

      和左旋简单版差不多
      image-20230911110322498

    难度版:找到不平衡点,将不平衡的左子节点晋升,不平衡点降级,原来的不平衡点的左子节点的右节点,变为不平衡的点的左子节点

    • 旋转的配合:一次旋转不能将二叉树进行平衡,只能通过多次旋转

      • 左左,左右
      • 右右,右左

      红黑树:

    1972年成为二叉平衡树b树,是一种特殊的查找树,不是规则的树,通过红黑规则实现的

    红黑规则:

    • 每一个结点必须是红色,或者是黑色
    • 根节点必须是黑色
    • 一个结点没有子节点或者父节点,则该节点的指针属性为nil,这些nil视为叶节点,每个叶节点是黑色的
    • 红色结点的子节点必须是黑色的(红红不能相联
    • 每一个结点的到叶结点的简单路径上,均包含相同数目的黑色节点

    红黑树节点的添加规则:

    • 默认添加节点的颜色是红色的这样的效率最高

    • 添加规则多种
      image-20230912192055336

    • 红黑树的增删改查性能比较好

    image-20230912191405327" style=“zoom: 67%;” />

    • 添加规则多种
      [外链图片转存中…(img-DgYDbTk2-1694765134852)]
    • 红黑树的增删改查性能比较好
  • 相关阅读:
    MYSQL数据库恢复(误删操作)
    使用vscode + lldb + codelldb调试可执行程序
    【Spring Boot】Day01
    字符流,编码表,字符流写数据,字符流读数据
    pcan二次开发文档 | PEAK-System Documentation
    冒泡排序和鸡尾酒排序和快速排序
    欧洲巨头强力支持Higg项目,事关2000个品牌
    2022年11月19日(星期六):骑行甸尾
    Redis 3.2.3 crashed by signal: 11 服务宕机问题排查
    自动化测试总计
  • 原文地址:https://blog.csdn.net/weixin_49513202/article/details/132906304