数据结构

数据结构

起男 1,142 2020-09-16

数据结构

栈(stack)

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶(top)。它是后进先出(lifo)的。对栈的基本操作只有push(进栈)和pop(出栈)两种，前者相当于插入最后，后者相当于删除最后的原生

队列(queue)

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为对头

链表是一种数据结构，和数组同级。比如java中我们使用的ArrayList，其实现原理是数组。而LinkedList的实现原理就是链表。链表在进行循环遍历时效率不高，但是插入和删除时优势明显

散列表(hash table)

散列表也叫哈希表是一种查找算法，与链表，树等算法不同的是，散列表算法在查找时不需要进行一系列和关键字的比较操作

散列表算法希望能尽量做到不经过任何比较，通过一次存取就能得到所查找的数据元素，因而必须要在数据元素的存储位置和它的关键字之间建立一个确定的对应关系，使每个关键字和散列表中一个唯一的存储位置相对应。因此在查找时，只要根据这个对应关系找到给定关键字在散列表中位置即可，这种对应关系被称为散列函数(可用用h(key)表示)

构造散列函数的方法有

  • 之间定址法：取关键字或关键字的某个线性函数值为散列地址
  • 数字分析法
  • 平均取值法：取关键字平方后的中间几位为散列地址
  • 折叠法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为散列地址
  • 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址
  • 随机数法：选择一个随机函数，取关键字的随机函数值为它的散列地址

排序二叉树

首先如果普通二叉树每个节点满足：左子树所有节点值小于它的根节点值，且右子树所有节点值大于它的根节点值，这样的二叉树就是排序二叉树

插入操作

首先要从根节点开始往下找到自己要插入的位置(即新节点的父节点)

具体流程是：

  • 新节点与当前节点比较，如果相同则表示已经存在且不能重复插入；如果小于当前节点，则到左子树中寻找，如果左子树为空则当前节点为要找的父节点，新节点插入到当前节点的左子树即可；如果大于当前节点，则到右子树中寻找，如果右子树为空则当前节点为要找的父节点，新节点插入到当前节点的右子树即可

删除操作

删除操作注意分为三种情况：

  1. 要删除的节点无子节点：可以直接删除，即让其父节点将该子节点置空即可
  2. 要删除的节点只有一个子节点：替换要删除的节点成其子节点
  3. 要删除的节点有两个子节点：首先找到该节点的替换节点(即右子树中最小的节点)，接着替换要删除的节点为替换节点，然后删除替换节点

查询操作

注意流程为：

  • 先和根节点比较，如果相同就返回，如果小于根节点则到左子树中递归查找，如果大于根节点则到右子树中递归查找

因此在排序二叉树中可以很容易获取最大(最右最深子节点)和最小(最左最深子节点)值

红黑树

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它是一种特殊的二叉查找树。红黑树的每个节点上都存储位表示节点的颜色，可以说红(Red)或黑(Black)

红黑树的特性

  • 每个节点或者是黑色，或者是红色
  • 根节点的黑色
  • 每个叶子节点是黑色【注：这里叶子节点是指为空(NIL或NULL)的叶子节点】
  • 如果一个节点是红色的，则它的子节点必须是黑色的
  • 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点

添加

  1. 将红黑树当作一颗二叉查找树，将节点插入

  2. 将插入节点着色为“红色”

    • 被插入精度是根节点：直接把此节点涂为黑色

    • 被插入节点的父节点是黑色：什么也不需要做。节点被插入后，仍然是红黑树

    • 被插入节点的父节点是红色：这种情况下，被插入节点是一定存在在非空祖父节点的；进一步讲，被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节点本身就是黑色节点)。理解这点之后，我们依据“叔叔节点的情况”，将这种情况进一步划分为：

      现象策略
      当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点(叔叔节点)也是红色1.将父节点设置为黑色
      2.将叔叔节点设置为黑色
      3.将祖父节点设置为红色
      4.将祖父节点设为当前节点(红色节点)；即之后继续对当前节点进行操作
      当前父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子1.将父节点作为新的当前节点
      2.以新的当前节点为支点进行左旋
      当前父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子1.将父节点设置为黑色
      2.将祖父节点设置为红色
      3.以祖父节点为支点进行右旋

  3. 通过一系列的原子或着色等操作，使之重新称为一颗红黑树

删除

  1. 将红黑树当作一颗二叉查找树，将节点删除

    • 被删除节点没有子节点：直接将该节点删除
    • 被删除节点有一个子节点：删除该节点，并用该节点唯一的字节的顶替
    • 被删除节点有二个子节点：先找出它的后继节点，然后把它的后继节点的内容负责给该节点的内容，之后删除它的后继节点

  2. 通过旋转和重新着色等一系列操作来修正该树，使之重新称为一颗红黑树

    • x是红+黑节点：直接把x设为黑色

    • x是黑+黑节点，且x是根：什么都不做

    • x是黑+黑节点，且x不是根：

      现象策略
      x是黑+黑节点，x的兄弟节点是红色1.将x的兄弟节点设置为黑色
      2.将x的父节点设置为红色
      3.对x的父节点进行左旋
      4.左旋后，从新设置x的兄弟节点
      x是黑+黑节点，x的兄弟节点是黑色，x的兄弟节点的两个子节点都是黑色1.将x的兄弟节点设置为红色
      2.设置x的父节点为新的x节点
      x是黑+黑节点，下的兄弟节点是黑色，x的兄弟节点左孩子是红色，右孩子是黑色的1.将x兄弟节点的左孩子设置为黑色
      2.将x兄弟节点设置为红色
      3.对x的兄弟节点进行右旋
      4.右旋后，重新设置x的兄弟节点
      x是黑+黑节点，x的兄弟节点是黑色，x的兄弟节点右还是是红色，左还是是任意颜色1.将x父节点颜色赋值给x的兄弟节点
      2.将x父节点设置为黑色
      3.将x兄弟节点的右子节点设置为黑色
      4.对x的父节点进行左旋
      5.设置x为根节点

B-TREE

b-tree又叫平衡多路查找树。一颗m阶的b-tree的特性如下：

  • 树中每个节点至多有m个孩子
  • 除根节点和叶子节点外，其它每个节点至少有ceil(m/2)个孩子
  • 若根节点不是叶子节点，则至少有2个孩子(特殊情况：没有孩子的根节点，即根节点为叶子节点，整棵树只有一个根节点)
  • 所有叶子节点都出现在同一层，叶子节点不包含任何关键字信息(可以看做是外部节点或查询失败的节点，实际上这些节点不存在，指向这些节点的指针都为null)
  • 每个非终端节点中包含有n个关键字信息
    • Li(i=1...n)为关键字，且关键字按顺序排序K(i-1) < Ki
    • Pi为指向子树根的接点，且指针P(i-1)指向子树种所有节点的关键字均小于Ki，但都大于K(i-1)
    • 关键字的个数n必须满足：ceil(m/2)-1 <= n <= m-1

一颗m阶的b+tree和m阶的b-tree区别在于：

  • 有n棵子树的节点种含有n个关键字(b-tree是由n-1个关键字)
  • 所有的叶子节点种包含了全部关键字的信息，及指向含有这些关键字纪录的指针，且叶子节点本身依关键字的大小自小而大的顺序连接(b-tree的叶子节点并没有包含全部需要查找的信息)
  • 所有的非终端节点可以看成是索引部分，节点种仅含有其子树根节点种最大或最小的关键字(b-tree的非终端节点也包含需要查找的有效信息)

位图

位图的原理就是用一个bit来标识一个数字是否存在，采用一个bit来存储一个数据，所以这样可以大大的节省空间。bitmap是很常用的数据结构，比如用于bloom filter种；用于无重复整数的排序等待。bitmap通常基于数组来实现，数组中每个元素可以看成是一系列二进制数，所有元素组成更大的二进制集合

数据结构