定义 # 一个特殊的二叉树结构 用数组表示时，对于数组中索引位置为 i 的元素，其对应树表示中，父节点，左右子节点的索引满足以下关系： Parent(i) = Math.floor(i/2) Left(i) = 2*i Right(i) = 2*i + 1 Max heap # 最大堆 除了根节点 A[i] <= A[parent(i)] Min heap # 最小堆 除了根节点，A[i] >= A[parent(i)] 通常用来实现优先队列 维持堆属性 # 构造最大堆 # 堆排序 # 优先队列 #
定义 # 树： 连接的 无向 无环图 Path # 路径： 节点和边的序列 路径长度； 路径里 边 的数量 Depth # 节点深度： 从根节点到当前节点的 路径 长度 Level # 节点层级：节点 depth + 1， （很少用） 树的层级：节点层级的最大值 Height # 节点高度： 从当前节点到 叶节点 的 最长 路径 长度 树的高度： 根节点的高度 Width # 树在深度 d 的宽度： 树在深度 d 的节点数量 树的宽度： 所有深度的最大宽 Binary Tree # 二叉树 Balanced # 平衡树的高度为 \(O(log n)\) Height-Balanced # 高度平衡，对任意节点而言，其子树的高度差 最多 为 1，空子树的高度为 -1 ...
Collision # 冲突： H(k1) = H(k2) 冲突解决方案 # Chaining # Open Addressing #
定义 # G = (V, E)， V 为非空顶点集，E 为边的集合 Directed Graph # 有向图 边 （u, v), u -> v ， v 跟 u 相邻 没有自循环的有向图是 简单有向图 Undirected Graph # 无向图 无向图不允许自循环 Degree # 度 In Degree # 入度 Out Degree # 出度: Path # <v0, v1, … , vk> v0 -> vk 的顶点的一个序列 长度： 路径中边的数量 Simple Path # 路径中所有的顶点都是不同的 Cycle # Edge # (u, v), 有向图中 (u, v) , (v, u) 是不一致的 ...
Singly linked list # 单链表 时间复杂度 # Access Search Insertion Deletion O(n) O(n) O(1) O(n) 注： 插入操作仅为在给定节点 Node 的指针 P 的前提下，在其后面插入一个节点，此时复杂度为 O(1)，若在 P 前面插入一个节点，则复杂度为 O(n), 因为需要遍历 Doubly linked list # 双链表 优点： # 可以双向遍历 删除操作更高效(O(1))，在已知给定节点的指针的前提下 插入操作 (O(1)) 缺点： # 额外的空间开销，用来存指针 所有操作需要维持两个指针的指向 时间复杂度 # Access Search Insertion Deletion O(n) O(n) O(1) O(n) / O(1) 注：如果需要遍历节点，则删除的时间复杂度为 O(n)