-
Treap
##前置芝士熟练掌握二叉查找(排序)树的插入、删除、求排名、求某一排名的数、求前驱、求后继等操作。#引言二叉查找树看似可以在 $O(logn)$ 中完成任意上述操作。但若该二叉查找树退化为如下形态: 此时,在此图上操作的时间复杂度仍为 $O(n)$。观察可知:二叉查找树的最优形态是平衡树,故需要一种能维持树的平衡形态的二叉查找树。 #正文Treap又名树堆,是一种利用随机性来维持二叉查找... -
Study note of MATH 521 - Analysis I
Number Systems and Basic Set TheoryLet’s just skip this section first. Basic TopologyCountable Sets::: thmTheorem 1. If there is a surjection $f: A \rightarrow B$, we have$|A| \geq |B|$. If there i...
1