这是学习的第二周了，第一周学习的内容以前自学过，感觉没那么吃力，第二周的课程看到题目后就觉得没那么简单，不过看完老师的视频觉得没有自己想象的那么难，感觉以前都是被这些名字给吓到了。

这周学完对基本的数据结构也算有了一定的了解，希望在以后的学习上能将这些知识理解并收为己用，解决自身学习和工作中的问题。

• 根据关键码值（Key Value）直接访问的数据结构
• 加快查找速度，数组的一种扩展

哈希表的映射函数叫做散列函数。散列函数生成的值要尽可能的随机和均匀分布。

• 散列函数计算得到的散列值是一个非负整数；
• 如果 key1 = key2，那 hash(key1) == hash(key2)；
• 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

装载因子：散列表的装载因子 = 填入表中的元素个数 / 散列表的长度，装载因子越大说明空闲位置越少，冲突越多，散列表的性能会下降。

• 开放寻址法

  • 适合数据量小，装载因子小的场景
  • 二次探测，双重散列

• 链表法

  • 基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表
  • 比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表

• 高度（从下往上，从0开始）
• 深度（从上往下，从0开始）
• 层（从上往下，从1开始）
• 数的高度（根节点的高度）
• 根节点（没有父节点）
• 叶子节点（没有子节点）

• 只有两个节点，左子节点，右子节点
• 满二叉树
  • 叶子节点都在最底层，
  • 除了叶子节点，所有节点都有两个子节点
• 完全二叉树
  • 叶子节点都在最底下两层
  • 最后一层叶子节点都靠左排列
  • 其他层节点个数都达到最大

• 前序遍历是指
  • 对于树中的任意节点来说，先打印这个节点，
  • 然后再打印它的左子树，
  • 最后打印它的右子树。
• 中序遍历是指
  • 对于树中的任意节点来说，先打印它的左子树，
  • 然后再打印它本身，
  • 最后打印它的右子树。
• 后序遍历是指
  • 对于树中的任意节点来说，先打印它的左子树，
  • 然后再打印它的右子树，
  • 最后打印这个节点本身。

前序遍历的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)

中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)

后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

• 左子树中每个节点的值都小于此节点的值
• 右子树中每个节点的值都大于此节点的值
• 左右子树也分别为二叉查找树

• 查询
• 插入
• 删除
• 快速找到最大和最小节点

• 大顶堆或大根堆（根节点最大）
• 小顶堆或小根堆（根节点最小）

• 堆是一颗完全二叉树。
• 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

• 一般是数组实现
• 假设根节点为0
  • 索引为i的左子节点 2*i+1
  • 索引为i的右子节点 2*i+2
  • 索引为i的父节点 floor((i-1)/2)

• 插入（HeapifyUp）
  • 插入堆尾部
  • 依次向上调整结构，到根即可
  • O(logN)
• 删除（HeapifyDown）
  • 将堆尾元素替换到顶部（替换被删除元素）
  • 一次从根部向下调整，到底即可

• Graph(V, E)
• V - vertex: 点
  • 度 入度和出度
  • 点与点之间：连通与否
• E - edge: 边
  • 有向和无向（单行线）
  • 权重（边长）