Skip to main content

数据结构-操作

遍历​

树​

  • 先根遍历
  • 后根遍历

二叉树​

递归遍历O(n)O(n)​

  • 先序遍历
  • 中序遍历
  • 后序遍历

非递归遍历​

  • 靠左深度优先
    • 待遍历栈
    • 遍历指针
    • 访问指针
  • 层序遍历
    • 待访问队列
    • 当前访问节点指针

图​

DFS​

BFS​

查找​

ASL​

ASL=∑i=1∣T∣PiCi,Pi=1∣T∣ASL=\sum^{|T|}_{i=1}P_iC_i,P_i=\frac{1}{|T|}

静态查找表​

  • 元素是否存在
  • 访问元素

顺序查找​

  • ASL=∑1=1nPiCi=1n∑i=1n≈n−12ASL=\sum^{n}_{1=1}P_iC_i=\frac{1}{n}\sum^{n}_{i=1}\approx \frac{n-1}{2}

二分查找​

  • ASLbs≈log⁡2n+1+1ASL_{bs} \approx \log_2^{n+1}+1
let sTable:number[]=[1,2,3,4,5,6,7,8,9,10,11];

let biSTree:number[]=[6,3,9,1,4,7,10,'',2,'',5,'',8,'',11];
     6
   /   \
  3     9
 / \   / \
1   4 7   10
 \     \   \
  2     8   11

分块查找​

let sTable:number[]=[6,3,9,1,4,7,10,2,5,8,11];
  |
  v
let bSTable:number[][]=[
  [6,9,11],
  [6,3,1,4,2,5],
  [9,7,8],
  [10,11]
];

动态查找表​

二叉排序树​

  • 性质
    • ∀t∈T, lchild(t)<t≤rchild(t)\forall t \in T,\space lchild(t) < t \le rchild(t)
  • 查找
  • 插入
  • 删除

平衡二叉树​

  • 性质
    • ∀t∈T, lchild(t)<t≤rchild(t) abs(h(lchild(t))−h(rchild(t)))={0,1}\forall t \in T, \space lchild(t) < t \le rchild(t) \space abs(h(lchild(t))-h(rchild(t)))=\{0,1\}
  • 插入
    • LL 单向右旋
    • RR 单向左旋
    • LR 先左后右双向旋转
    • RL 先右后左双向旋转平衡
  • 删除
    • 一般情况，被删除的节点的子树都需要更新

平衡 m 叉树​

  • 性质
    • N={n,A0K0,⋯ ,AnKn}N=\{n,A_0K_0,\cdots,A_nK_n\}
  • 概念
    • 关键字 K
      • Ki<Ki+1K_i<K_{i+1}
    • 子结点 A
      • ∀K∈Ai−1, K<Ki\forall K \in A_{i-1},\space K < K_i
    • ⌈m2⌉−1≥n≤m−1\lceil\frac{m}{2}\rceil-1 \ge n \le m-1
  • 分裂
    • 在插入操作中，若操作导致某节点n>m−1n>m-1，则需要分裂
  • 合并
    • 在分裂操作中，若操作导致某节点n<⌈m2⌉−1n<\lceil\frac{m}{2}\rceil-1，则需要合并

哈希表​

  • 概念
    • 哈希函数:H(K)H(K)
    • 散列:H(K)→dataH(K) \to data
    • 冲突:Ki≠Kj H(Ki)=H(Kj)K_i \neq K_j \space H(K_i) = H(K_j)
      • 同义词:Ki≠KjK_i \neq K_j
  • 哈希函数
    • 直接定址法
    • 数字分析法
    • 平方取中法
    • 折叠法
    • 随机数法
    • 除留余数法

排序​