查找

查找算法中主要涉及三种重要的数据结构来实现字典，即二叉查找树，红黑树，散列表。本章主要介绍这三种重要的数据结构。

一、符号表（字典）

符号表是一种存储键值对的数据结构，主要支持两种操作，插入（put）即将一组新的键值对存入符号表，查找（get）根据给定的键找到相应的值。

二、二叉查找树

二叉查找树（BST）就是一颗二叉树，其中每个节点都包含一个键（实现Comparable）和一个值，且每个节点的键都大于其左子树任意节点的键，且小于右子树任意节点的键。

我们将定义一个私有类来表示二叉查找树的节点，该类包含一个左子节点的连接，一个右子节点的连接，一个键和一个值，和一个节点计数器（该节点计数器表示以该节点为跟节点的二叉树的所有节点数。）

1.查找

二叉查找树的查找有两种结果，如果该树中不包含要查找的内容，则返回null。如果包括要查找的键，则返回该键对应的值。在查找算法中，如果要查找的键大于当前节点的键，则在当前节点的右子树种继续查找，如果要查找的键小于当前节点的键，则在当前节点的左子树中继续查找，如果相等，则代表当前节点即是要查找的节点，返回该节点的值即可，否则则代表要查找的键在当前数中不存在，返回null。以下是代码实现：

1 public Value get(Key key) {

2 return this.get(key, root);

3 }

5 private Value get(Key key, Node node) {

6 if (node == null) {

7 return null;

8 }

10 if (node.key.compareTo(key) < 0) {

11 return get(key, node.rightNode);

12 } else if (node.key.compareTo(key) > 0) {

13 return get(key, node.leftNode);

14 } else {

15 return node.value;

16 }

17 }

插入
二叉查找树的插入算法和查找算法基本一致，都是利用递归的思想实习的。在插入的时候，如果树是空的，则返回包含该键值对的新节点。插入算法实现如下：注意其中递归函数的构造
1 /*二叉查找树插入算法的实现*/
2     public void put(Key key, Value value) {
3         this.put(root, key, value);
4     }
5     private Node put(Node root, Key key, Value value) {
6         if (root == null) {
7             return new Node(key, value, 1);
8         }
9         else if (key.compareTo(root.key) > 0) {
10             root.rightNode = put(root.rightNode, key, value);
11         }
12         else if (key.compareTo(root.key) == 0) {
13             root.value = value;
14             return root;
15         }
16         else {
17             root.leftNode = put(root.leftNode, key, value);
18         }
19         root.N = size(root.leftNode) + size(root.rightNode) + 1;
20         return root;
21     }

在由N个随机键构造的二叉查找树中，查找和插入算法的平觉时间复杂度均为对数级别的2lnN.
有序性相关的
（1）最大键和最小键
如果根节点的左链接为空，则跟节点即为该二叉查找树的最小节点，否则的话该树的最小键就是其左子树的最小键。该句话也间接地描述了获取最小键的方法。即不断的递归获取左子树的最小键。获取最大键的方法和思想与之类似，只是变为遍历右子树。其算法实现如下
1 /*获取二叉树中的最小键*/
2     public Key min() {
3         return this.min(this.root);
4     }
5     private Key min(Node node) {
6         if (node.leftNode == null) {
7             return node.key;
8         } else {
9             return min(node.leftNode);
10         }
11     }

1     /*获取二叉查找树中的最大键*/
2     public Key max() {
3         return this.max(this.root);
4     }
5
6     private Key max(Node node) {
7         if (node.rightNode == null) {
8             return node.key;
9         } else {
10             return max(node.rightNode);
11         }
12     }
删除操作

3.1 删除最大键和删除最小键

二叉查找树中比较麻烦的操作就是删除操作，我们先从删除最大键deleteMax()和删除最小键deleteMin()入手。对于删除最大键，我们可以采取递归的形式，删除二叉树中最右侧的节点，同时把指向该节点的链接指向该节点的左子节点（如果有的话）。对于删除最小键的操作则与之类似。算法实现如下：

1 /*删除二叉树中的最大节点*/

2 public void deleteMax() {

3 this.deleteMax(this.root);

4 }

5 private Node deleteMax(Node node) {

6 if (node.rightNode == null) {

7 return node.leftNode;

8 }

9 node.rightNode = deleteMax(node.rightNode);

10 node.N = size(node.leftNode) + size(node.rightNode) -1;

11 return node;

12 }

3.2删除

二叉查找树的删除操作有一个问题，删除之后的节点是一个空节点，需要用其他的节点来填补，填补算法是什么？T.Hibbard在1962年提出了一个解决此问题的方法。对于要删除的节点X，用来填补该节点的节点必须满足以下条件：填补节点的键必须小于于删除节点右子树所有节点的键同时大于左子树所有节点的键。因此满足条件的节点就是删除节点右子树中最小的节点。因此删除算法分为一下介个步骤：

1 /*根据key删除某个节点*/

2 public Node delete(Key key, Node node) {

3 if (key.compareTo(node.key) > 0) {

4 node.rightNode = delete(key, node.rightNode);

5 }

6 else if (key.compareTo(node.key) < 0) {

7 node.leftNode = delete(key, node.leftNode);

8 } else {

9 if (node.rightNode == null) {

10 return node.leftNode;

11 }

12 if (node.leftNode == null) {

13 return node.rightNode;

14 }

16 Node tempNode = node;

17 node = this.minNode(node.rightNode);

18 node.leftNode = tempNode.leftNode;

19 node.rightNode = this.deleteMax(node.rightNode);

20 }

22 return node;

24 }

三. 平衡查找树

通过二叉查找树我们看到，这种数据结构无论是对于查找还是插入操作，其时间复杂度都能大约维持在O(lgN)。但是在构造二叉查找树的时候，如果按照升序或者逆序的方式插入二叉查找树，那么最后构造成的树是一颗极度不对称的，其查找和插入性能就跟一般的链表无异。因此为了避免这种情况，才引入了平衡查找树这种数据结构。平衡查找树也是一棵二叉查找树，因此他的插入和查找算法的时间复杂度就跟二叉查找树一样，也是O(lgN)，但是在构造构造平衡查找树的时候，为了避免上述极端情况的出现，我们会一边插入元素，一边调整树的结构，以尽量保证树的平衡。

红黑树
红黑树就是一颗二叉查找树，通过对每个节点新增一个颜色的属性，可以是red或black。通过对任何一条从根节点到也在节点的简单路径上的个各个节点上的颜色加以控制，红黑书确保没有一条路径是比其他路径的=长出两倍，因而使近似平衡的。
树种的每个节点包含以下5个属性：parent,left,right,key和color。如果一个节点没有父节点或者没有子节点则该节点相应属性的指针值为NIL。我们可以把NIL看作二叉查找树的叶节点（外部节点）的指针，而把带关键字的节点看作是内部节点。
红黑书有以下性质：
（1）每个节点是红色的或者黑色的
（2）跟节点是黑色的
（3）每个叶节点（NIL）是黑色的
（4）如果一个节点是红色的，那么他的两个子节点是黑色的（因此不存在两个相连的红节点）
（5）对每个节点，从该节点到期后代叶节点的简单路径上，均包含相同数目的黑节点
为了处理红黑书代码中的边界条件，我们使用一个烧饼T.nil来表示红黑书中的叶节点NIL。对于一棵红黑树，哨兵T.nil就是一个颜色为BLACK的普通节点，他的其他属性值可以任意设定，所有的叶节点都指向少哨兵T.nil。
使用哨兵后，就可以将节点x的NIL孩子是为普通的节点。尽管可以为树中的每个节点的NIL节点都定义一个新的节点，但是这样会比较浪费空间，因此我们将所有的叶节点的指针都指向同一个哨兵节点T.nil。
从某个节点x出发（不包含该节点本身），到达任意叶节点一条简单路径经过的黑节点的数目称为该节的黑高。即为bh(X).

定理：一棵含有n个节点的红黑树的高度之多为 2lg(n+1)
由此可见对于一棵红黑书，其各种操作的时间复杂度仍为O(lgN)

1.1 旋转
我们是通过旋转操作来保证红黑树的平衡。
旋转有两种旋转：左旋转和右旋转。以左旋转为例，当在某个节点X上做左旋转时，假设X的右子节点为Y且不为NIL，（X可以是其右子节点部位NIL的任意节点），左旋以X到Y的链接为支轴进行，它使Y变为旋转后的该子树的新的根节点，X是Y的左子节点，Y的左子节点成果为X的右子节点。右旋转的操作则与此类似。