前端工程师的自我修养

数据结构

栈（stack）

操作

  • push - 最上方插入元素

  • pop - 返回最上方元素，并从栈中移除

堆（heap）

数结构，完全二叉树的一种特殊类型，所有节点满足根节点大于（小于）左右子节点，所以堆顶为最大（最小）元素。

  • 查找

  • 插入

  • 删除

队列 （queue）

操作

  • enqueue - 在队尾插入元素

  • dequeue - 返回队首元素，并从队列删除

数组（array）

操作

  • get - 读取某个索引的元素

  • set - 替换某个索引的元素

  • insert - 在某个索引插入元素

  • delete - 删除某个索引的元素

  • size - 返回数组长度

链表（linked list）

操作

  • insertHead - 在链表头部之前插入元素

  • insertAfter - 在指定元素之后插入新元素

  • has - 查找指定元素

  • delete - 删除指定元素

树（tree）

二叉树（binary tree）

满二叉树（perfect binary tree）

节点铺满树的每一层。

        6
     /    \
    2      8
   /  \   / \
  1   4  3   9

完全二叉树（complete binary tree）

节点必须逐层、从左到右添加。也就是仅有最后一层没铺满。

        6
     /    \
    2      8
   /  \   / 
  1   4  3

二叉搜索树（binary search tree）

定义：

  • 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  • 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  • 任意节点的左、右子树也分别为二叉查找树；
  • 没有值重复的节点。
      6
     /  \
    2    8
   /  \   \
  1    4   9
      / \   \
     3   5  10

查找效率：平均为 O(log2n)，相当于二分查找

插入效率：平均为 O(log2n)，二分查找到对应位置

删除效率：平均为 O(log2n)，二分查找到对应节点，将其用中序遍历的后继节点替换

最差情况下全为O(n)，比如全部节点只有右子树（类似链表），层数为n。

平衡二叉树（balanced binary tree）

所有节点都满足：其左右子树的高度差值不大于1。

      1
     /  \
    2    8
   /  \   \
  6    4   9
      / \
     3   5

平衡二叉搜索树（AVL tree）

同时满足“二叉搜索树”和“平衡二叉树”的所有特性。

      6
     /  \
    2    8
   /  \   \
  1    4   9
      / \
     3   5

普通的“二叉搜索树”在经历多次插入删除操作后，可能会变得极不平衡，导致查找效率退化。

AVL 树则能一直保持较好的查找效率。可以通过对“二叉搜索树”中失衡节点进行“左旋”、“右旋”等操作，使其变成“AVL 树”。

红黑树

红黑树是更进一步的“AVL 树”，其平衡条件更易达到，有更少的“旋转”操作，从而有更好的增删性能。

定义：

  • 节点是红色或黑色。
  • 根是黑色。
  • 所有叶子都是黑色（叶子是NIL节点）。
  • 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
  • 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

这些约束可以确保：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。即查找效率最差也是O(log2n)。

          b13
        /     \
     r8        r17
    /  \       /  \
  b1   b11   b15  b25
    \             /  \
    r6         r22  r27

二叉树的遍历

       1
      /  \
     2     3
   /  \     \
  4    5     6
      / \
     7    8

  • 深度优先遍历:

    前序(根->左->右): 1 2 4 5 7 8 3 6

    中序(左->根->右): 4 2 7 5 8 1 3 6

    后序(左->右->根): 4 7 8 5 2 6 3 1

  • 广度优先遍历:

    1 -> 2 3 -> 4 5 6 -> 7 8

堆（heap）

分类

  • 小顶堆：

    所有节点满足：节点值小于其子节点

  • 大顶堆：

    所有节点满足：节点值大于其子节点

图（graph）

分类

  • 有向图

  • 无向图

存储方式

  • 邻接矩阵：全部节点作为矩阵的行和列，matrix[i][j] 表示 i 节点与 j 节点是否邻接

  • 邻接表：全部节点作为数组，各自存储与自己邻接的其他节点

操作

  • 插入点

  • 返回点的相邻点

  • 遍历图，可分为DFS/BFS

散列表（hash table）

操作

  • has - 查找指定元素

  • add - 插入元素