Lab 8: BSTs and Asymptotics

CS61B

1: BSTMap

在导入lab8包的时候，报错Package name 'lab8' does not correspond to the file path ''.

现在的directory是这样的：

后来删掉了原来的文件目录（即lab8,lab8tester)，把所有java文件移到lab8这个大目录下，再点击红色波浪，按alt+enter,选择：move to package "lab8"， 系统就会自动重新建一个lab8目录，这个目录就是package，注意到它的颜色不是蓝色，而是灰色，左下角还有一个小黑星。注意我在这些操作之间在project structure里面的modules里把lab8整个目录都标记为source蓝色的：

这样package的问题就解决了。

可是好景不长，在我想要运行TestBSTMap的时候，发现报错ClassNotFoundException，然后搜索了一下解决方案，发现要把相应的lab8tester文件夹改成source，即把文件夹变成蓝色，这下我的package lab8tester下面又出现了红色波浪线，到头来还是没有解决package的问题。

接下来我如何处理的，写到了另外一个专门记录ClassNotFoundException的文章里。

通过一番折腾，BSTMap的test是全部通过了，但是我的github目录出了点问题：
我的github目录突然出现了lab8/src这样子中间有“/”的目录，但我指向要lab8这个名字，不想要多余的：

鼠标点在lab8/src这里github提示的是：this path skips through empty directories，但很奇怪，我的lab8文件夹里面明明有不止是src的其他文件夹：idea. ， out这些：

暂时不忙管github目录的问题，继续完成printInOrder()这个方法，查了一下别人写的，基本都是错的，我自己改正确了。但我还是发现自己写recursion包括helper method还根本不成气候，没有很熟练的通用模板，要多练习多总结：

    public void printInOrder() {
        printInOrderHelper(root);
    }
    //不是很会写recursion, 查一下有没有什么通用的方法再多加练习
    private void printInOrderHelper(Node x){
        if (x == null){
            System.out.println("");
        }else if(x.left == null && x.right == null){
            System.out.println(x.key +"," + x.value);
        }else if(x.left != null && x.right == null){
            printInOrderHelper(x.left);
            System.out.println(x.key +"," + x.value);
        }else if(x.left == null & x.right != null){
            System.out.println(x.key +"," + x.value);
            printInOrderHelper(x.right);
        }else{
            printInOrderHelper(x.left);
            System.out.println(x.key +"," + x.value);
            printInOrderHelper(x.right);
        }
    }

通过测试：

2: So... How Fast Is It?

Extra: Modify the testing classes so that they also compare the performance of your class to the built-in HashMap class, which uses an alternate technique for implementing maps (called hashing) that we'll develop next week.

InsertRandomSpeedTest:

InsertOrderSpeedTest: