[Coursera] Algorithms, Part Ⅰ (Week 5)

请教一下各位，为什么红黑树一定要向某个方向倾斜？left-leaning可以保证最长路径不超过最短路径长度的二倍，但是如果不专门调整倾斜方向的话，red link既可以在左侧也可以在右侧出现，平衡性不是更好吗？
莫非是因为代码实现更加简洁？Sedgewick 2007年做的改进就是添加了left-leaning特性才实现的？

FindNearest 总说我多用了 distanceSquaredTo
无论如何 就差这一点扣分了…………求指教
private void findNearest(Node x, Point2D p) {
                if (x == null) return;
                if (x.rect.distanceSquaredTo(p) >= nearestDistance) {
                        return ;
                }
                double distance = p.distanceSquaredTo(x.p);
                if (distance < nearestDistance) {
                        nearestDistance = distance;
                        currentNearestPoint = x.p;
                }
                findNearest(x.lb, p);
                findNearest(x.rt, p);
        }

ohmystill 发表于 2013-11-11 11:53
FindNearest 总说我多用了 distanceSquaredTo
无论如何 就差这一点扣分了…………求指教
private void fi ...

记得这个作业我好像没用recursion,是不是因为用了递归的关系所以会多次计算distanceSquaredTo啊？不好意思实在不记得了。。因为程序在另一台电脑上所以现在查不了。等我能用另一台电脑的时候告诉你我怎么写的-_-!!

anonym 发表于 2013-11-1 03:50
请教一下各位，为什么红黑树一定要向某个方向倾斜？left-leaning可以保证最长路径不超过最短路径长度的二倍 ...

这个问题好难。。。你可以在coursera的forum里问问这个问题啊~~

lvluolan 发表于 2013-11-12 00:42
记得这个作业我好像没用recursion,是不是因为用了递归的关系所以会多次计算distanceSquaredTo啊？不好意思 ...

好的 没事 等用那台电脑时候 再说哦 多谢啦