Python implementation of imooc course 玩转数据结构, thanks for that great course (instructor liuyubobobo) !
Any pull-request is welcome:)
Any quesitons please email to [email protected]
Array 数组 Stack 栈 Queue 队列 Linked List 链表 Binary Search Tree 二分搜索树 Heap 堆
Segment Tree 线段树 Trie Union Find 并查集
AVL Red Black Tree 红黑树 Hash Table 哈希表
二叉堆：
- 堆中任意节点的值一定小于等于其父节点的值（最大堆）
- 用数组实现即可
- 对于任意节点i，左孩子是2 * i + 1, 右孩子是2 * i + 2，父节点(i - 1) // 2 （因为索引从0开始）
- 添加元素时候，先在最下面的最左边添加一个元素，再执行sift_up操作
- sift_up: 新添加的节点和父亲节点比较，交换，再递归重复（因为如果新节点的值比父亲节点大，则一定比父亲节点的另一个节点大，大于号保持不变性）
- extract_max_heap: 取出堆顶的值，并将最小层最左边的元素移到堆顶，再执行sift_down
- sift_down: 每次要下沉的元素和两个孩子比较，和两个孩子中最大的交换位置，再递归重复
- replace: 取出一个最大的，再放入一个新元素，set 0 index，再从0开始sift_down
- heapify: 将任意数组整理成堆的形状, 从最后一个非叶子节点开始计算，倒着从后向前sift_down即可 (算法复杂度是O(n)的！！！)
- 最后一个非叶子节点：先拿到最后一个节点的索引，计算它的父亲节点的索引即可(再递归所有非叶子节点)！！！
- d叉堆 d-ary heap
- 索引堆：可以看到堆中间的元素（最短路径和Dijkstra中可能用到）
- 二项堆，斐波那契堆
- 广义队列（普通队列，优先队列，随机队列，栈也可以理解成一个队列）
线段树：O(logn)
- 区间染色
- 区间查询(动态不停的更新和查询), 区间本身固定
- 线段树不是完全二叉树，但是是一棵平衡二叉树（任何节点的左右深度之差小于等于1）
- 第h层（h从0开始）：h层有2 ** h - 1个节点
- 如果区间有n个元素，则4n的空间足以
Trie:
- 重点应用是查询前缀
UnionFind
- 连接问题
- union(e1, e2), query(e1, e2)
- use array for implementation
- 可以基于size优化
- 可以基于rank优化
- 路径压缩(发生在find操作中顺便进行)
- 查询合并都是�O(h)
- 并查集的优势是在合并查询都有的场景
AVL
- G.M.Adelson-Velsky and E.M.Landis
- 自平衡二分搜索树
- 对于任意一个节点，左子树和右子树的高度差不能超过1
- 平衡因子：叶子节点为0，非叶子节点左右子树高度差
- 左旋转，右旋转，在插入节点的时候造成了不平衡 LL, RR
- 插入的元素在不平衡的节点的左侧的左侧 -> 右旋转，将下图的B作为新节点
A
/
B
/
new node
- LR和RL LR -> LL, RL -> RR
A
/
B
\
new node
红黑树
- 红黑树也是平衡二分搜索树，统计性能更好
-
- 每个节点要么是红色，要么是黑色
-
- 根节点是黑色的
-
- 每一个叶子节点（最后的空节点）是黑色的(空节点既是根节点，又是叶子节点，是黑色的)
-
- 如果一个节点是红色的，那么他的孩子节点都是黑色的(why? because red node's parent MUST BE BLACK!!!, so a red node can not be the parent node of another red node)
-
- 从任意一个节点到叶子节点，经过的黑色节点数目是一样的(红色节点不一定一样多)，因为1）绝对平衡，高度一致，2）不算红色节点
- 算法4（作者Robert Sedgewick即红黑树发明人之一）
- Donald Knuth的弟子(The art of computer Programming, TAOCP)
- 23树：节点可以存放一个元素或者两个元素, 2节点，3节点, 2-3树是一棵绝对平衡的树(从根节点到任意一个叶子节点经过的节点数目都是相同的)
- 23树永远不会添加新节点到一个空的位置上(找最后一个叶子节点)
- why 23 tree === r-b tree? 红色节点相当于表示它和它父亲节点等效于23树种的3节点！！！所有的红色节点都是左倾斜的。
- 23树中的2节点即黑节点，3节点即红-黑节点（红在左边）
- 如果经常添加，删除，红黑树性能高于AVL
- 所有的红节点都是向左倾斜的
- 红黑树中添加新元素：左旋转 -> 右旋转 -> 颜色翻转
- 红黑树删除节点（太复杂）
哈希表
- 设计哈希函数，key通过哈希函数得到的index分布越均匀越好
- 哈希冲突处理
- 大整数：取模（可能造成分布不均匀，直接丢弃了部分数字的信息）-> 模一个素数
- 空间换时间
- 一致性，高效性，均匀性
- hash冲突可以使用链地址法解决 (seperate chaining)
- hash(-121211) & 0x7fffffff % M 0x7fffffff (f == 1111, 7 == 111，一共是31个1 == 2147483647，相当于抹去了最高位符号位的1)
- 哈希表开了M个空间，对于冲突的元素以链表（或者TreeMap, TreeSet）形式插入
- 平均每个地址承载的元素多过一定程度，即扩容 N/M >= upper_tol
- 平均每个地址承载的元素少过一定程序，即缩容 N/M < lower_tol
- 开放地址法，不必马上插入相同hash的链表中，放入下一个空白的位置即可(线性探测，平方探测，二次哈希),这样可以使得数组整体被使用率比较高（负载率高，均匀度高）
- 再哈希法（rehashing）
- coalesced hashing（综合了sperate chaining和open addressing）
平摊分析：Amortized Analysis, resize时候会引入。 remove_last时resize太过着急，出现复杂度震荡，使用lazy方案： 扩容2倍，缩容1/4（错开）
删除任意节点：
- 叶子节点
- 只有左孩子或者只有右孩子
- 既有做孩子又有右孩子（* Hibbard Deletion *）:找被删节点右子树中方的最左节点（最小值）来代替
完全二叉树：不一定是满二叉树，但是缺失的节点一定是在树的右下侧
满二叉树：除了叶子节点，所有节点既有左孩子又有右孩子
图结构：邻接表和邻接矩阵（建图比较简单，但是可以应用图的存储结构的一些性质做一些很好的应用）
抽象数据结构：类似于接口的思想