视频感想

昨天晚上看了关于“都市信息网”项目开发视频，给人总体感觉差强人意，学到了一些知识，记录如下：

1、页面结构：

在页面结构的定义上，将页面分成多部分，例如页头，页尾，左侧栏和右主栏。在每个栏中导入需要的JSP文件。

2、关于controller：

要让controller实现RequestAware和ResponseAware。然后使用继承。

3、关于DAO层的设计

遗憾的是都市信息在DAO层的设计上，是一个败笔。在controller里面使用sql语句。不利于各个层次的独立。

4、关于TreeMap

在该项目中，使用map多使用TreeMap，查一下TreeMap是什么东西吧：

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by aComparator provided at map creation time, depending on which constructor is used.

哦，是一个基于红黑树的Map。

什么是红黑树。

红黑树（Red-Black Tree）是二叉搜索树（Binary Search Tree）的一种改进。我们知道二叉搜索树在最坏的情况下可能会变成一个链表（当所有节点按从小到大的顺序依次插入后）。而红黑树在每一次插入或删除节点之后都会花O（log N）的时间来对树的结构作修改，以保持树的平衡。也就是说，红黑树的查找方法与二叉搜索树完全一样；插入和删除节点的的方法前半部分节与二叉搜索树完全一样，而后半部分添加了一些修改树的结构的操作。
红黑树的每个节点上的属性除了有一个key、3个指针：parent、lchild、rchild以外，还多了一个属性：color。它只能是两种颜色：红或黑。而红黑树除了具有二叉搜索树的所有性质之外，还具有以下4点性质：
1. 根节点是黑色的。
2. 空节点是黑色的（红黑树中，根节点的parent以及所有叶节点lchild、rchild都不指向NULL，而是指向一个定义好的空节点）。
3. 红色节点的父、左子、右子节点都是黑色。
4. 在任何一棵子树中，每一条从根节点向下走到空节点的路径上包含的黑色节点数量都相同。

有了这几条规则，就可以保证整棵树的平衡，也就等于保证了搜索的时间为O（log N）。

但是在插入、删除节点后，就有可能破坏了红黑树的性质。所以我们要做一些操作来把整棵树修补好。下面我就来介绍一下。