[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（肯定考）

• 掌握四条定义、会判断是否是红黑树

1. Every is either red or black
2. The root and NILs are all black
3. If a node is red, its children should be black.
4. 每一条路径上的黑色的节点个数都相同. Every path from a node to a leaf must contain the same number of black nodes.

如果parent为黑色，直接插入即可；否则根据以下规则进行变换。

               O  grandparent
              / \
      uncle  O   O   parent
                /
              Z

新增的节点都是赋予红色的。（一次变换后，还需要进行检查）

1. Z = root --- recolor (只有这种情况新增节点变颜色)
2. Z.uncle = Red --- recolor（parent+grandparent+uncle）
3. Z.uncle = Black(triangle) --- rotate parent 转到一条线上
4. Z.uncle = Black(line) --- rotate grandparent + recolor（parent+grandparent）

suffix tree

• suffix 有很多

  • s = abaaba$
    • $
    • a$
    • ba$
    • aba$
    • aaba$
    • baaba$
    • abaaba$

• suffix trie 树

  • 可以得到三个信息
    • 有没有
    • 有几个

    • 分别从哪边开始

      
      
      Image.jpg

• 两个字符串判断公共的子串
  • 分别先往子串后面加上符号

  • 最后标上每一层X or Y or XY，找XY层数最多的，字符最长的，把边读出来就是最长子串

    
    
    Image2.jpg

Image3.jpg