Lecture 21: Binary Search Trees

CS61B

提示：可以做一做他们的midterm exam,目前有两个了

BST Property

No duplicate keys allowed:

BST Operations:

Finding a searchKey in a BST

Worst case runtime to complete a search on a "bushy" BST:

Inserting a new key into a BST

Deleting from a BST

三种情况

例子：

BST Performance

数学分析：

deletion需要C(N)~sqrt(N) per operation:

summary:
Binary search tree的insertion和search都很高效：

• “Bushy”trees上面的操作都是对数时间；
• random data的insertion会产生一个“bushy”的tree
  
  • 也就是说，对于任意的数据，put/get的Order of growth都是对数性的；

问题：

• ”Spindly" trees是线性的performance;

• Hibbard deletion（也就是delete掉有两个孩子的node）需要sqrt(N)的order of growth

  

Recommended Problems:

C level
1.What is the best case BST height in terms of N? Worst case?

3.

4.
相关slide:

B LEVEL

solution:

这道题不是很懂：