1、前面讨论了静态查找表，它们的特点是，数据是一次性就给好了。

2、而对于动态查找表，数据可以是在查找过程中动态添加、生成的。其实这概念不太严谨。

3、二叉排序树(BST)：左子树上所有结点的值均小于根结点的值；右子树上所有结点的值均大于根结点上的值。

4、二叉排序树的查找过程：
(1)若树为空，直接返回/跳出。
(2)树非空，则
(a)若key==root.data，return true。
(b)若key<root.data, root = root.left。
(c)若key>root.data, root = root.right。
(3)若最后还未找到，返回false。

这个查找可以是递归，也可以不递归

5、当构造BST时，要注意：只有关键字不在BST树中时，才能插入。因此，插入一个元素前要先查找(Search)。

6、中序遍历二叉排序树(BST)可以得到一个关键字有序的序列（升序）。

7、BST树删除结点（同样使用之后的AVL树），假设要删除的结点为p，它的双亲结点为f，并假设p为f的左孩子：
(1)若p为叶子结点，直接删除，并更改它双亲的为null即可。
(2)若p只有左子树或者只有右子树，直接让左、右子树成为f的左子树即可。
(3)若p的左子树和右子树均非空。让p的直接前驱(指中序遍历的前一个元素)替代p，然后删除直接前驱。

8、二叉排序树上查找其关键字个数等于路径长度加1（或者所在层次数）。

9、二叉查找树查找平均O(logn)，最坏O(n)。

10、上面的最坏，就是查找树由于插入顺序而退化成了一条支线（斜向左下或右下）。