树
2017-07-16 本文已影响32人
riveraiyanzi
二叉树
遍历
前序，中序，后序。是以遍历根结点的顺序来定义的
写法：递归是很自然的写法，也可借助栈用循环来实现
与 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)，优点是当词汇量很大时，这样比较省空间。
例题
