delete(A):
exchange A[1], A[n]
n = n - 1
max_heapify(A, 1)
树
基本
树的前序遍历
树的中序遍历
树的后序遍历
树的dfs非递归写法
树的bfs非递归写法
二叉树
已知前序和后序能不能构建二叉树 不能,“根左右”和“左右根”无法判断左右子树
什么是二叉搜索树 1)二叉查找树可以是一棵空树 2)或者是具有下列性质的二叉树
若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值
它的左、右子树也分别为二叉排序树。
二叉搜索树的优点 1) 有链表的快速插入与删除操作的特点 2) 有数组快速查找的优势
如何对二叉搜索树进行节点删除
如何对二叉搜索树进行节点插入
如何对二叉搜索树进行节点的查找
什么是完全二叉树
什么是平衡二叉树
一个具有N个节点的完全二叉树深度是多少,叶子节点是多少
红黑树
什么是红黑树
红黑树的特点
其他
什么是前缀树
散列表(哈希)
什么是散列表 就是哈希表,是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。也就是说,把关键字映射到一个表中的位置来直接访问记录,以加快访问速度。我们将关键字称为 Key,把对应的记录称为 Value,通过 Key 访问一个映射表来得到 Value 的地址。而这个映射表,也叫作散列函数或者哈希函数,存放记录的数组叫作散列表。 散列表有两种用法:一种是 Key 的值与 Value 的值一样,一般我们称这种情况的结构为 Set(集合);而如果 Key 和 Value 所对应的内容不一样时,那么我们称这种情况为 Map,也就是人们俗称的键值对集合。
散列表的存储 以chaining解决碰撞为例
散列表读取的时间复杂度 O(1+α),α为装载因子,
α
=
n
m
\alpha=\frac{n}{m}
α=mn,
n
n
n表示key个数,
m
m
m表示slot个数
常见的散列表哈希函数 1)直接寻址法 取关键字或关键字的某个线性函数值为散列地址。 2)数字分析法 通过对数据的分析,发现数据中冲突较少的部分,并构造散列地址。例如同学们的学号,通常同一届学生的学号,其中前面的部分差别不太大,所以用后面的部分来构造散列地址。 3)平方取中法 当无法确定关键字里哪几位的分布相对比较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为散列地址。这是因为:计算平方之后的中间几位和关键字中的每一位都相关,所以不同的关键字会以较高的概率产生不同的散列地址。 4)取随机数法 使用一个随机函数,取关键字的随机值作为散列地址,这种方式通常用于关键字长度不同的场合。 5)除留取余法 取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要,一般取素数或者直接用 n。 6)Multiplication Method
h
(
k
)
=
(
A
⋅
k
m
o
d
2
w
)
r
s
h
(
w
−
r
)
h(k)=(A\cdot k\mod 2^w) rsh (w-r)
h(k)=(A⋅kmod2w)rsh(w−r)
A
A
A 一般为一个不接近
2
w
−
1
2^{w-1}
2w−1 和
2
w
2^w
2w,且位于他俩之间的奇数
w
w
w 表示计算机中一个字的长度为
w
w
w 位,哈希表大小(槽位数)
m
=
2
r
m=2^r
m=2r,
r
s
h
rsh
rsh 表示右移操作
开放寻址法的问题 在做删除操作的时候,需要特殊设计,比如将
k
k
k 通过哈希函数投影到
x
x
x,随后发现在
x
x
x 处有冲突,因此根据探测再哈希投影到
x
′
x'
x′,后期删除操作时,删除了位于
x
x
x 位置的记录,那么再次搜索
k
k
k 时,会发现
x
x
x 处不存在记录,从而不进行探测,进而认为
k
k
k 记录不存在
# 用广度优先的方式寻找从s开始所有的reachable nodes
def BFS(s, Adf):
level = {s: 0} # 字典,存储所有节点都是s在几个move下reach得到的
parent = {s: None} # 字典,存储每个节点的parent
i = 1
frontier = [s] # i-1 move 的情况下可以reach的node
while frontier:
next = [] # i move 的情况下可以reach的node
for u in frontier:
for v in Adj[u]:
if v not in level:
level[v] = i
parent[v] = u
next.append(v)
frontier = next
i += 1
图的DFS搜索
# 用深度优先的方式寻找从s开始所有的reachable nodes
parent = {s: None}
def dfs_visit(V, Adf, s):
for v in Adj[s]:
if v not in parent:
parent[v] = s
dfs_visit(V, Adj, v)
# 用深度优先的方式遍历全图
def dfs(V, Adf):
parent = {}
for s in V:
if s not in parent:
parent[s] = None
dfs_visit(V, Adf, s)
其他
如何交换两个数字的值但不申请额外的空间 用异或
a = a ^ b
b = a ^ b // a = a^b^b
a = a ^ b // b = a^b^a