树

二叉树

遍历

前序，中序，后序。是以遍历根结点的顺序来定义的
写法：递归是很自然的写法，也可借助栈用循环来实现

与 DFS, BFS 的关系

前序遍历就是 DFS，但是这三种中并没有 BFS

Binary search tree

掌握二叉搜索树的性质，搜索某个节点的方法。
注意不要跟 binary search 算法搞混了，binary search 是在一个排序数组中二分查找某个元素

Binary Indexed Tree or Fenwick Tree

We have an array arr[0 . . . n-1]. We should be able to
1 Find the sum of first i elements.
2 Change value of a specified element of the array arr[i] = x where 0 <= i <= n-1.
Binary Indexed Tree 使得上面这两个操作的时间复杂度都为 O(lgn)。^[1]
用在边插入，边搜索的场景，所以时间复杂度 O(lgn) 有意义。
例题

Segment Tree

Segment Tree 要解决的也是上面这个问题，但是实现比 Binary Indexed Tree or Fenwick Tree 复杂，没有掌握。^[2]

堆

堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。这种数据结构具有以下性质。

• 任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）
• 堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入
  将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

Priority Queue

优先队列的底层实现应该是堆。
例题

Trie

用于单词的插入和搜索。add, search 的时间复杂度为 lg(n)，优点是当词汇量很大时，这样比较省空间。
例题

---

1. http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/ ↩

2. http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/ ↩