[toc]
Lecture 7-8
P4.Binary tree
- 二叉树的基本操作
P5.Binary search tree
- 什么是balance search tree、大小关系、给出一个不平衡的->平衡
- 练习题：p28
P20.Tree balance
- 如何判断一棵树是否平衡
- We say that a binary tree is balanced if the height difference between the right and left subtree of all its nodes is not greater than one.
P29.Inserting
- 要会操作
P30.Splay trees（肯定考）
- 考步骤、会插入删除
threes types of rotations(题目中会给出)
[图片上传失败...(image-6fde52-1547562446283)]
- 在zig-zig中先转哪个得先看清楚
P58.Red-black trees（肯定考）
- 掌握四条定义、会判断是否是红黑树
- Every is either red or black
- The root and NILs are all black
- If a node is red, its children should be black.
- 每一条路径上的黑色的节点个数都相同. Every path from a node to a leaf must contain the same number of black nodes.
如果parent为黑色，直接插入即可；否则根据以下规则进行变换。
O grandparent
/ \
uncle O O parent
/
Z
新增的节点都是赋予红色的。（一次变换后，还需要进行检查）
- Z = root --- recolor (只有这种情况新增节点变颜色)
- Z.uncle = Red --- recolor（parent+grandparent+uncle）
- Z.uncle = Black(triangle) --- rotate parent 转到一条线上
- Z.uncle = Black(line) --- rotate grandparent + recolor（parent+grandparent）
suffix tree
-
suffix 有很多
- s = abaaba$
- $
- a$
- ba$
- aba$
- aaba$
- baaba$
- abaaba$
- s = abaaba$
-
suffix trie 树
- 可以得到三个信息
- 有没有
- 有几个
-
分别从哪边开始
Image.jpg
- 可以得到三个信息
- 两个字符串判断公共的子串
- 分别先往子串后面加上符号
-
最后标上每一层X or Y or XY，找XY层数最多的，字符最长的，把边读出来就是最长子串
Image2.jpg
Image3.jpg
