Assignment8.5

Binary Search Tree

学完了二叉查找树, 该自己动手写一写.
理论很简单. 能写出来是很重要的.
二叉查找树是平衡树(红黑树, AVL树等)的基础.其重要程度不亚于排序.
估计时间(5h)

Part I: 
        void add(int key); // 添加元素
        int min();
        int max();
        int size();
        int height(); 
 
在树上的 前序, 中序, 后序 遍历算法.
        
Part II: 
        void del(int key);  // 删除元素

Part III: 
        /******************************
         *  Rank and selection
         *****************************/
        int select(int k);  // 取出第K大的元素
        int rank(int key);  // 元素key在集合里面排多大

建议步骤:

1. 若已经明白题目需求,跳过该步, 否则粗略扫一边TA代码. 不要在意实现细节
2. 实现PartI 测试PartI. 实现数上的前序,中序遍历
3. 按照上面依次实现PartII, PartIII

这次因为比较基础, 思考难度小, 主要是考验编码能力.
而实践这种东西不是你抄别人一遍, 就会了.
所以希望大家自己踩一遍坑,再去参考别人或者TA代码. 这样才能体会为什么要这样写.

TA 实现的版本, https://github.com/ds-sww/codebase/pull/391/files
里面有简单的插入和删除的测试, 可以参考一下.