本来是用表格做的，可他该死的东西不支持。内容才是重要的东西，形式粗糙点就算了。

1 特殊运算符
() 圆括号
[] 下标运算符
-> 指向结构体成员运算符
.  结构体成员运算符

2 单目运算符
!  逻辑非
~  按位取反
++ 自增
-- 自减
-  负号
() 类型转换
*  指针
&  地址
sizeof 长度

3 2次运算符
* 乘法
/ 除法
% 求余

4 1次运算符
+ 加法
- 减法

5 移位运算符
<< 左移
>> 右移

6 关系运算符1
< <= > >=

7 关系运算符2
== 等于
!= 不等于

8 按位与 
&

9 按位异或 
^

10 按位或
|

11 逻辑与
&&

12 逻辑或
||

13 条件运算符 
?:

14 赋值运算符
= += -= *= /=
%= >>= <<=
&= ^= != 

15 逗号运算符
,

(a,b)树
多叉树的一种描述方式是(a,b)树，其定义如下。
设a和b是整数且a≥2，2a-l≤b。则一棵(a,b)树T满足下述条件：
1 T的所有叶结点在同一层上；
2 对任意的非叶结点v∈T都有ρ(v)≤b；
3 除根外的任意非叶结点v满足ρ(v)≥a；
4 设r是T的根结点，则ρ(r)≥2。
其中ρ(v)是结点v的次数。

B树
对于(a,b)树，若a=|b/2|，则称为B树。
一棵m序(阶)非空B树定义如下：
1 所有叶结点在同一层上，B树是平衡树；
2 除根节点外的任意节点有m/2棵子树到m棵子树；
3 根节点是一个叶节点或至少有两棵子树。
其中||代表向上取整。

下图为一棵3阶B树。每个节点最多有m=3棵子树，m-1=2个关键码。


B+树
一棵m序(阶)非空B+树定义如下：
1 树中每个非叶结点最多有m棵子树；
2 根节点(非叶节点)至少有2棵子树。除根节点外，其他的非叶节点至少有|m/2|棵子树。有n棵子树的非叶节点有n-1个关键码；
3 所有的叶节点都在同一层上，包含了全部关键码及指向相应数据对象存放地址的指针，且叶节点本身按关键码从小到大顺序链接；
4 每个叶节点中的子树棵数n可以多于m，可以少于m，视关键码字节数及对象地址指针字节数而定。若节点可容纳最大关键码数为m1，则指针对象的地址指针也有m1个，因此节点中的子树棵数n应满足n∈[|m1/2|, m1]。
其中||代表向上取整。

下图为一棵4阶B+树。每个非叶节点最多有m=4棵子树，每个叶节点最多可容纳m1=5个关键码。

通常B+树有两个头指针：一个指向B+树的根节点，用于从根节点开始的随机搜索；一个指向关键码最小的叶节点，用于从叶节点链表开始的顺序搜索。

B+树与B树的最显著的区别在于：
1 B+树只在叶结点存储记录。
2 B+树内部节点与叶节点在结构上有着显著的区别：内部节点存储关键码引导索引和指向相应子树的指针；叶结点存储实际记录。
3 m阶B+树中的叶子节点可能存储大于或者小于m个记录。
4 B+树的叶节点通常链接起来以便于检索。

B+树内部节点结构(4阶B+树)


B+树叶节点结构(m1=3)


带重复键的B+树
内部节点关键码存储子树中的第一个新关键码。


下图为一棵4阶B+树，叶节点m1=3。

下面我们将以此图为初始状态图解B+树的插入和删除操作。

B+树插入
插入40之初
叶节点插入关键码40，使得叶节点关键码个数大于3。
分裂叶节点为[31,37]和[40,41]。


插入40之后
内部节点中插入指向新叶节点块中的第一个关键码40，使得内部节点子树个数大于4。
分裂内部节点为[23,31]和[40,41]，将新内部节点块中第一个关键码提到父节点中。


B+树删除
删除7
叶节点关键码个数小于2个，合并到相邻兄弟叶节点[2,3,5,11]。
叶节点关键码个数大于3个，分裂为[2,3]和[5,11]，并更新内部父节点关键码。


删除11之初
叶节点关键码个数小于2个，合并到相邻兄弟叶节点[2,3,5]。
叶节点块减少1个，更新内部父节点关键码减少1个。


删除11之后
内部节点子树个数小于2，向父节点借关键码13以及相邻兄弟内部节点的子树。
将兄弟内部节点块中第一个关键码提到父节点中。


B+树的插入和删除操作是节点内部的分裂与合并操作。需要注意的是叶节点和内部节点在操作上的区别。

小结
B+树可以看作是B树的一种变形，在实现文件系统索引方面比B树使用得更为普遍，另外很多数据库都使用B+树算法处理索引。

2-3-4 Tree
2-3-4树满足其节点或者是空节点或者是下面三种节点类型之一：1键2分支节点(2-node)，2键3分支节点(3-node)，3键4分支节点(4-node)。平衡的2-3-4树满足从根节点开始到所有空节点距离相等。


2-3-4 Tree 插入
新键值插入2-3-4树，需将键值插入到叶节点。下图详细说明了插入键值时节点类型的变化和拆分操作。

插入C后，节点由2-node节点变为3-node节点。插入H后，节点由3-node节点变为4-node节点。若插入I，则需先对4-node节点做拆分，将中间键值上提到父节点，然后再插入I。

下图按照ASERCHINGX顺序构建2-3-4 Tree


2-3-4 Tree 性能
N个节点的2-3-4树，搜索节点最多需要访问lgN+1个节点；插入一个节点平均需要拆分少于一个节点，最坏情况下需要拆分lgN+1个节点。

Red Black Tree
2-3-4树插入操作在描述上很好理解，但在实现上却很复杂。这是因为2-3-4树需要维护三种类型的节点，以及相对应的众多复杂的情况。为解决此问题，基本思想是使用简单的结构代替2-3-4树，而这种结构就是在标准BST的基础上加入相邻节点间链的属性，将其分为red-link和black-link，即Red Black Tree(红黑树)。


red-link(粗线)表示节点内部的连接，从而代替2-3-4树中的3-node和4-node。black-link(细线)表示2-3-4树实际节点间的链。


节点类实现
public class RBTNode {
 int key;
 Object value;
 boolean red;      //红节点标记
 RBTNode left;
 RBTNode right;
 public RBTNode(int x, Object obj) {
  this.key = x;
  this.value = obj;
  this.red = true;
  this.left = null;
  this.right = null;
 }
}
在实现上，我们将red-link和black-link表示为节点的属性。

插入节点
红黑树新节点插入时与BST相同，新插入的节点为红节点。插入后需要沿插入路径的逆向顺序进行相关节点拆分和红黑属性调整。拆分和调整原则如下图所示：

1 2-node节点连接4-node节点，拆分转换成3-node节点连接2个2-node节点。
a 转换过程中，表示4-node节点的2个红子节点转换为黑节点，父节点转换为红节点。
2 3-node节点连接4-node节点，拆分转换成4-node节点连接2个2-node节点。
a 转换过程中红节点不相连，仅转换节点红黑属性。
b 转换过程中红节点相连，成直线形，转换节点属性后还要进行左旋转或右旋转操作。
c 转换过程中红节点相连，成折线形，转换节点属性后还要进行左右双转或右左双转操作。

下图按照ASERCHINGX顺序构建Red Black Tree


判断红节点
private boolean red(RBTNode x) {
 if (x == null)
  return false;
 else
  return x.red;
}

旋转操作
private RBTNode rotL(RBTNode h) {
 RBTNode x = h.right;
 h.right = x.left;
 x.left = h;
 return x;
}
private RBTNode rotR(RBTNode h) {
 RBTNode x = h.left;
 h.left = x.right;
 x.right = h;
 return x;
}

插入算法
public void insert(int x, Object obj) {
 root = insert(root, x, obj, false);
 root.red = false;
}
private RBTNode insert(RBTNode h, int x, Object obj, boolean sw) {
 if (h == null) {
  h = new RBTNode(x, obj);
  return h;
 }
 if (red(h.left) && red(h.right)) {
  h.red = true;
  h.left.red = false;
  h.right.red = false;
 }
 if (x < h.key) {
  h.left = insert(h.left, x, obj, false);
  if (red(h) && red(h.left) && sw) {
   h = rotR(h);
  }
  if (red(h.left) && red(h.left.left)) {
   h = rotR(h);
   h.red = false;
   h.right.red = true;
  }
 } else {
  h.right = insert(h.right, x, obj, true);
  if (red(h) && red(h.right) && !sw) {
   h = rotL(h);
  }
  if (red(h.right) && red(h.right.right)) {
   h = rotL(h);
   h.red = false;
   h.left.red = true;
  }
 }
 return h;
}

一颗平衡的红黑树满足在所有从根到叶的路径上不存在两个相邻的红节点且黑节点数目相同。

小结
一颗N个节点的红黑树，搜索操作需要平均1.002lgN次比较，最坏情况下少于2lgN+2次比较。红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保，且他的统计性能要好于AVL树，因此，红黑树在很多地方都有应用。

我们曾在解决BST平衡性问题时引入了旋转操作和RootInsert，但其并没有使BST达到真正的平衡。于1962年，G.M.Adelson-Velskii和Y.M.Landis提出了AVL树。AVL树又称高度平衡二叉搜索树，具有下列性质：每个节点左、右子树深度之差的绝对值不超过1。节点右子树深度与左子树深度之差定义为该节点的平衡因子，AVL中每个节点的平衡因子只能是1、0或－1。



节点类实现
public class AVLNode {
 int key;
 Object value;
 AVLNode left;
 AVLNode right;
 int balance;        //平衡因子
 public AVLNode(int key, Object value) {
  this.key = key;
  this.value = value;
  this.left = null;
  this.right = null;
  this.balance = 0;
 }
}

左右旋转操作
private AVLNode rotL(AVLNode h) {
 AVLNode x = h.right;
 h.right = x.left;
 x.left = h;
 return x;
}
private AVLNode rotR(AVLNode h) {
 AVLNode x = h.left;
 h.left = x.right;
 x.right = h;
 return x;
}

插入节点
新节点插入后，需要对AVL树沿节点插入路径的逆向顺序进行平衡性调整：旋转相关节点，并修改相关节点平衡因子。其过程中，当节点子树高度与插入前一致时，则停止调整。

1 当前节点平衡因子为1，新节点插入到节点右子树。

a 若右子树平衡因子为1，图(b)中C节点。进行左旋转操作。


b 若右子树平衡因子为-1，图(b)中C节点。进行先右后左两次旋转操作。


private AVLNode iBalanceR(AVLNode h) {
 AVLNode rightsub = h.right;
 switch (rightsub.balance) {
 case 1:
  h.balance = 0;
  rightsub.balance = 0;
  h = rotL(h);
  check = false;
  break;
 case 0:
  break;
 case -1:
  AVLNode leftsub = rightsub.left;
  switch (leftsub.balance) {
  case 1:
   h.balance = -1;
   rightsub.balance = 0;
   break;
  case 0:
   h.balance = 0;
   rightsub.balance = 0;
   break;
  case -1:
   h.balance = 0;
   rightsub.balance = 1;
   break;
  }
  leftsub.balance = 0;
  h.right = rotR(rightsub);
  h = rotL(h);
  check = false;
  break;
 }
 return h;
}

2 当前节点平衡因子为-1，新节点插入到节点左子树。

a 若左子树平衡因子为-1，图(b)中B节点。进行右旋转操作。


b 若左子树平衡因子为1，图(b)中B节点。进行先左后右两次旋转操作。


private AVLNode iBalanceL(AVLNode h) {
 AVLNode leftsub = h.left;
 switch (leftsub.balance) {
 case -1:
  h.balance = 0;
  leftsub.balance = 0;
  h = rotR(h);
  check = false;
  break;
 case 0:
  break;
 case 1:
  AVLNode rightsub = leftsub.right;
  switch (rightsub.balance) {
  case -1:
   h.balance = 1;
   leftsub.balance = 0;
   break;
  case 0:
   h.balance = 0;
   leftsub.balance = 0;
   break;
  case 1:
   h.balance = 0;
   leftsub.balance = -1;
   break;
  }
  rightsub.balance = 0;
  h.left = rotL(leftsub);
  h = rotR(h);
  check = false;
  break;
 }
 return h;
}

节点插入算法如下，成员变量check标记节点子树高度与插入前是否不一致。
public void insert(int key, Object obj) {
 check = false;
 root = insert(root, key, obj);
}
private AVLNode insert(AVLNode h, int key, Object obj) {
 if (h == null) {
  h = new AVLNode(key, obj);
  check = true;
 } else if (key < h.key) {
  h.left = insert(h.left, key, obj);
  if (check) {
   switch (h.balance) {
   case -1:
    h = iBalanceL(h);
    break;
   case 0:
    h.balance = -1;
    break;
   case 1:
    h.balance = 0;
    check = false;
    break;
   }
  }
 } else if (key > h.key) {
  h.right = insert(h.right, key, obj);
  if (check) {
   switch (h.balance) {
   case -1:
    h.balance = 0;
    check = false;
    break;
   case 0:
    h.balance = 1;
    break;
   case 1:
    h = iBalanceR(h);
    break;
   }
  }
 }
 return h;
}

删除节点
1 搜索被删除节点
节点删除时需要先找到被删除节点x。若x最多只有一个子女，则可直接删除x，并将x的单一子女提到节点x的位置。若x有两个子女，则需在x的左子树中找到x的前继节点y，先将x与y进行交换再删除x。

2 调整AVL平衡性
对AVL树沿节点删除路径(包括寻找前继节点的路径)的逆向顺序进行平衡性调整：旋转相关节点，并修改相关节点平衡因子。其过程中，当节点子树高度与删除前一致时，则停止调整。调整算法与插入算法极为相似。

仅以删除节点在左子树一侧进行图解说明
a 不旋转

b 左单旋

c 右左双旋


private AVLNode rBalanceL(AVLNode h) {
 switch (h.balance) {
 case -1:
  h.balance = 0;
  break;
 case 0:
  h.balance = 1;
  check = false;
  break;
 case 1:
  AVLNode rightsub = h.right;
  switch (rightsub.balance) {
  case 1:
   h.balance = 0;
   rightsub.balance = 0;
   h = rotL(h);
   break;
  case 0:
   h.balance = 1;
   rightsub.balance = -1;
   h = rotL(h);
   check = false;
   break;
  case -1:
   AVLNode leftsub = rightsub.left;
   switch (leftsub.balance) {
   case -1:
    h.balance = 0;
    rightsub.balance = 1;
    break;
   case 0:
    h.balance = 0;
    rightsub.balance = 0;
    break;
   case 1:
    h.balance = -1;
    rightsub.balance = 0;
    break;
   }
   leftsub.balance = 0;
   h.right = rotR(rightsub);
   h = rotL(h);
   break;
  }
  break;
 }
 return h;
}

相应删除到右子树的调整算法
private AVLNode rBalanceR(AVLNode h) {
 switch (h.balance) {
 case 1:
  h.balance = 0;
  break;
 case 0:
  h.balance = -1;
  check = false;
  break;
 case -1:
  AVLNode leftsub = h.left;
  switch (leftsub.balance) {
  case -1:
   h.balance = 0;
   leftsub.balance = 0;
   h = rotR(h);
   break;
  case 0:
   h.balance = -1;
   leftsub.balance = 1;
   h = rotR(h);
   check = false;
   break;
  case 1:
   AVLNode rightsub = leftsub.right;
   switch (rightsub.balance) {
   case -1:
    h.balance = 1;
    leftsub.balance = 0;
    break;
   case 0:
    h.balance = 0;
    leftsub.balance = 0;
    break;
   case 1:
    h.balance = 0;
    leftsub.balance = -1;
    break;
   }
   rightsub.balance = 0;
   h.left = rotL(leftsub);
   h = rotR(h);
   break;
  }
  break;
 }
 return h;
}

搜索x前继节点
private AVLNode finepred(AVLNode h, AVLNode x) {
 if (h.right != null) {
  h.right = finepred(h.right, x);
  if (check)
   h = rBalanceR(h);
 } else {
  x.value = h.value;
  x.key = h.key;
  h = h.left;
  check = true;
 }
 return h;
}

节点删除算法如下，成员变量check标记节点子树高度与删除前是否不一致。
public void remove(int key) {
 check = false;
 root = remove(root, key);
}
private AVLNode remove(AVLNode h, int key) {
 if (h == null) {
  return h;
 } else if (key == h.key) {
  if (h.left == null) {
   h = h.right;
   check = true;
  } else if (h.right == null) {
   h = h.left;
   check = true;
  } else {
   h.left = finepred(h.left, h);
   if (check)
    h = rBalanceL(h);
  }
 } else if (key < h.key) {
  h.left = remove(h.left, key);
  if (check)
   h = rBalanceL(h);
 } else if (key > h.key) {
  h.right = remove(h.right, key);
  if (check)
   h = rBalanceR(h);
 }
 return h;
}

小结
一颗N个节点的AVL树，其高度可保持在log2(N)，平均搜索长度也可保持在log2(N)。AVL树通常用于构造后不经常改动的静态字典，或适合于组织在内存中的较小的目录。对于存放在外存中的较大的目录，如文件系统，就不适合用AVL树，而应采用B+树。

Trie作为基数搜索(Radix-Search)中结构与性能较好的一种，通常作为设计实现高效搜索算法的基础。与DST相同，Trie使用键值Key作为向导进行搜索。而不同的是，Trie保存了键值间相互的顺序关系，且将键值存储于树底层的叶节点。



下面我们使用字母做键值（5位二进制表示），说明节点的插入和搜索算法。
A 00001
S 10011
E 00101
R 10010
C 00011
H 01000
I 01001
N 01110

节点类实现
public class TrieNode {
 int key;
 Object value;
 TrieNode left;
 TrieNode right;
 public TrieNode() {
  this.key = -1;
  this.value = null;
  this.left = null;
  this.right = null;
 }
 public TrieNode(int key, Object value) {
  this.key = key;
  this.value = value;
  this.left = null;
  this.right = null;
 }
}

插入节点
Trie的树形结构与节点插入的先后顺序无关。这是因为新节点插入时，根据键值选择分支，将节点存储于第一个可完全区别于其他键值的分支叶节点，并相应的调整其他节点位置。

下图按照ASERCHIN顺序构建Trie



public int digit(int key, int bit) {
 return (key - 64) >> (4 - bit) & 1;
}
private TrieNode split(TrieNode p, TrieNode q, int d) {
 TrieNode t = new TrieNode();
 int v = p.key, w = q.key;
 switch (digit(v, d) * 2 + digit(w, d)) {
 case 0:
  t.left = split(p, q, d + 1);
  break;
 case 1:
  t.left = p;
  t.right = q;
  break;
 case 2:
  t.right = p;
  t.left = q;
  break;
 case 3:
  t.right = split(p, q, d + 1);
  break;
 }
 return t;
}
public void insert(int key, Object obj) {
 root = insert(root, new TrieNode(key, obj), 0);
}
private TrieNode insert(TrieNode h, TrieNode x, int d) {
 if (h == null) {
  h = x;
  return h;
 }
 if (h.left == null && h.right == null) {
  h = split(x, h, d);
  return h;
 }
 if (digit(x.key, d) == 0)
  h.left = insert(h.left, x, d + 1);
 else
  h.right = insert(h.right, x, d + 1); return h;
}
注：split方法用于调整当前插入节点与原有节点间的冲突，将两节点进行区分。

搜索节点
public Object search(int key) {
 return search(root, key, 0);
}
private Object search(TrieNode h, int key, int d) {
 if (h == null)
  return null;
 if (h.left == null && h.right == null)
  return (h.key == key) ? h.value : null;
 if (digit(key, d) == 0)
  return search(h.left, key, d + 1);
 else
  return search(h.right, key, d + 1);
}

小结
在N个键值节点的Trie中，插入和搜索随机键值需要平均lgN次比较，其时间效率与DST一样出色。当然，Trie同样存在着一些问题，以及改进版本Patricia Tries，有兴趣大家可以去看。

怎样有效存储Strings？
首先，我们可以用哈希表存储。但这样会失去string相互间的顺序信息，即便可以很快地对string进行访问。其次，我们可以用BST。这样就保存了string间的顺序信息，而且访问速度也过得去。再有，我们可以用DST。虽然需要大量的空间存储键值每一个基位，但访问速度却非常快。

TST
结合BST的空间性能和DST的时间性能，Jon Louis Bentley和James Bob Sedgewick提出了TST(Ternary Search Tree)的结构和相关算法。
下面我们以如下字符串序列说明TST与BST和DST的结构关系
as, at, be, by, he, in, is, it, of, on, or, to.

1 BST结构存储

虽然使用了很少的节点进行存储，但访问如at,he这样的底层节点确要经过很多次比较。

2 DST结构存储

访问速度虽然大大提高了，但若存储一个基于字母表的字符串序列，难道我们还要为每个节点扩展26个子节点么？

3 TST结构存储

TST是一颗三叉树，满足对于每个节点，当前子键小于该节点子键存储于左子树，大于该节点子键存储于右子树，string的下一个子建存储于中子树。

节点类实现
public class TSTNode {
 char splitchar; //字符串中的字符(子键)
 TSTNode left;
 TSTNode right;
 TSTNode middle;
 boolean last;   //是否字符串最后一个字符
 public TSTNode(char c) {
  this.splitchar = c;
  this.left = null;
  this.right = null;
  this.middle = null;
  this.last = false;
 }
}

插入节点
public void insert(String s) {
 if (s == null)
  return;
 root = insert(root, s, 0);
}
private TSTNode insert(TSTNode h, String s, int d) {
 char c = s.charAt(d);
 if (h == null)
  h = new TSTNode(c);
 if (d == s.length() - 1) {
  h.last = true;
  return h;
 }
 if (c < h.splitchar)
  h.left = insert(h.left, s, d);
 else if (c > h.splitchar)
  h.right = insert(h.right, s, d);
 else
  h.middle = insert(h.middle, s, d + 1);
 return h;
}

搜索节点
public boolean search(String s) {
 TSTNode p = root;
 int d = 0;
 while (p != null) {
  char c = s.charAt(d);
  if (c < p.splitchar)
   p = p.left;
  else if (c > p.splitchar)
   p = p.right;
  else {
   if (d == s.length() - 1)
    return p.last;
   d++;
   p = p.middle;
  }
 }
 return false;
}

小结
结合了BST和DST特性的TST，具有很好的时间和空间性能。与哈希表相比，大大加快了不成功搜索速度，且树的生长与收缩性能都很出色。而且，TST还支持高级搜索，比如partial-match(匹配.a.a.a形字符串)和near-neighbor(形似字符串)，有兴趣的话大家可以去看看。

参考文献
Ternary Search Trees, Dr. Dobb's Journal April 1998.

数字搜索树(DST)是基数搜索(Radix-Search)中简单基础的一种。其插入和搜索算法相似于BST，区别在于DST比较键值Key时仅比较选定的几位，而非全键值比较。

下面我们使用字母做键值（5位二进制表示），说明节点的插入和搜索算法。
A 00001
S 10011
E 00101
R 10010
C 00011
H 01000
I 01001
N 01110
G 00111
X 11000
M 01101
P 10000
L 01100

节点类实现
public class DSTNode {
 int key;
 Object value;
 DSTNode left;
 DSTNode right;
 public DSTNode(int key, Object value) {
  this.key = key;
  this.value = value;
  this.left = null;
  this.right = null;
 }
}

键值Key第bit位
public int digit(int key, int bit) {
 return (key - 64) >> (4 - bit) & 1;
}

插入节点
除根节点外，DST节点插入按照二进制基数从左到右顺序，0选择左子树1选择右子树，插入到叶节点。

下图按照ASERCHING顺序构建DST

public void insert(int key, Object obj) {
 root = insert(root, key, obj, 0);
}
private DSTNode insert(DSTNode h, int key, Object obj, int d) {
 if (h == null) {
  h = new DSTNode(key, obj);
  return h;
 }
 if (digit(key, d) == 0)
  h.left = insert(h.left, key, obj, d + 1);
 else
  h.right = insert(h.right, key, obj, d + 1);
 return h;
}

搜索节点
从根节点开始，根据二进制基数从左到右顺序，0选择左子树1选择右子树，搜索键值为Key的节点。
public Object search(int key) {
 return search(root, key, 0);
}
private Object search(DSTNode h, int key, int d) {
 if (h == null)
  return null;
 if (h.key == key)
  return h.value;
 if (digit(key, d) == 0)
  return search(h.left, key, d + 1);
 else
  return search(h.right, key, d + 1);
}

小结
DST的插入和搜索操作需要平均lgN次比较，最坏情况下约2lgN次比较。DST是我感觉最没什么可写的。因为在实际应用中，直接使用DST的情况很少，而大多数情况是利用DST的思想去构造或完善其他搜索策略。

考虑到马上就要研三，包括自己在内的很多同学和朋友都开始找工作了，又考虑到数据结构是基础，所以准备写点数据结构相关的东西。权当复习和攒人品了。

计划先写写以下几种树形结构（前几个是基础的树结构，后几个是平衡树结构）：
BST (Binary Search Tree)
DST (Digital Search Tree)
TST (Ternary Search Tree)
Trie
AVL
2-3-4 Tree & Red Black Tree
B(B+) Tree

BST(Binary Search Tree)
二叉搜索树BST是一颗二叉树，满足所有节点键值Key大于（或等于）其所有左子树节点键值，并小于（或等于）其所有右子树节点键值。

节点类实现
public class BSTNode {
 int key;
 Object value;
 BSTNode left;
 BSTNode right;
 public BSTNode(int key, Object value) {
  this.key = key;
  this.value = value;
  this.left = null;
  this.right = null;
 }
}

插入节点
下图按照ASERCHIN顺序构建BST

public void insert(int key, Object obj) {
 BSTNode x = new BSTNode(key, obj);
 if (root == null) {
  root = x;
 } else {
  BSTNode p = root;
  for (BSTNode q = p; q != null; p = (q != null) ? q : p) {
   q = (key < q.key) ? q.left : q.right;
  }
  if (key < p.key)
   p.left = x;
  else
   p.right = x;
 }
}

排序节点
BST的结构自动保存了所有节点的顺序关系，对一个BST使用中序遍历即可得到其所有节点的排序。
public void show() {
 show(root);
}
private void show(BSTNode h) {
 if (h == null)
  return;
 show(h.left);
 System.out.println(h.key + " -> " + h.value);
 show(h.right);
}

问题
通过上面的例子我们可以看出BST的一个明显问题：平衡性。为了解决这个问题，我们引入两种操作。

左旋转
将当前节点的右节点和当前节点做左旋转，进行交换。

private BSTNode rotL(BSTNode h) {
 BSTNode x = h.right;
 h.right = x.left;
 x.left = h;
 return x;
}

右旋转
将当前节点的左节点和当前节点做右旋转，进行交换。

private BSTNode rotR(BSTNode h) {
 BSTNode x = h.left;
 h.left = x.right;
 x.right = h;
 return x;
}

根插入
采用根插入代替原先的插入，可以较有效的解决BST平衡性问题。其思路就是若将节点插入到当前节点左子树则对当前节点进行右旋转，反之则进行左旋转。

public void rootinsert(int key, Object obj) {
 root = rootinsert(root, key, obj);
}
private BSTNode rootinsert(BSTNode h, int key, Object obj) {
 if (h == null) {
  h = new BSTNode(key, obj);
  return h;
 }
 if (key < h.key) {
  h.left = rootinsert(h.left, key, obj);
  h = rotR(h);
 } else {
  h.right = rootinsert(h.right, key, obj);
  h = rotL(h);
 }
 return h;
}

小结
BST具有很好的时间和空间效率，应用很广范。关于BST的介绍，我只写了很基础的部分。其实有些操作还是很值得琢磨的，如旋转。还有就是BST的思想，左中右的关系有时候是不一定要在树形结构中体现的。希望对大家有所帮助。

浮点数运算在程序设计中存在着各式各样的陷阱。我们应该知道浮点数在计算机中通常采用二进制浮点数算法表示，并由IEEE754对其做出了详细的规定。下面我们就开始学习一下二进制浮点数算法。

1 IEEE754
在IEEE754中，共指定了三种浮点数的格式（类型）。分别为：
Single(Fortran's REAL*4, C's float), (Obligatory),
Double(Fortran's REAL*8, C's double), (Ubiquitous),
Double-Extended(Fortran REAL*10+, C's long double), ( Optional ).
每一种格式都定义有NaN（非数字）、±∞（无限）和该格式有限实数集的表示：2^(k+1-N)*n。
其中带符号有效数字n和无符号指数k取值参考为：
K+1 Exponent bits: 1–2^K< k <2^K，  Significant bits: -2^N< n <2^N
-------------------------------------------------------------------
Format              Bytes             K+1               N
Single                4                8                24
Double                8                11               53
Double-Extended       ≥10             ≥15            ≥64
-------------------------------------------------------------------
K+1表示为指数位，N表示为有效数字位（Nth位为最高位，做为小数点前而省略）

他们的存储格式可以如下概括：
-------------------------------------------------------------------------
类型       存储格式                                          指数偏移量
REAL*4 　　1位符号位(s)、8位指数(e)，23位尾数(m,共32位) 　127(7FH)
REAL*8 　　1位符号位(s)、11位指数(e)，52位尾数(m,共64位)　1023(3FFH)
REAL*10　　1位符号位(s)、15位指数(e)，64位尾数(m,共80位)　16383(3FFFH)
-------------------------------------------------------------------------
可以看到，无论哪种格式，存储时都分为三个部分：
a 符号位（Sign） ：0代表正，1代表为负，
b 指数部分（Exponent）：用于存储科学计数法中的指数数据，并且采用移位存储，
c 尾数部分（Mantissa）：尾数部分，表示有效数字。

2 二进制浮点数取值划分
--------------------------------------------------------------------------
Number Type|Sign|    Exponent    | Nth bit |   N-1 bits of Significand
NaNs       |  ? |binary 111...111|    1    |         binary 1xxx...xxx
SNaNs      |  ? |binary 111...111|    1    | nonzero binary 0xxx...xxx
Infinities | ± |binary 111...111|    1    |              0
Normals    | ± |    k-1+2^K     |    1    |nonnegative n–2^(N-1)<2^(N-1)
Subnormals | ± |      0         |    0    |     positive n<2^(N-1)
Zeros      | ± |      0         |    0    |              0
--------------------------------------------------------------------------
其中有效数字n为脱离符号位后结果。

光看这个表抽象得很，我们还是以REAL*4为例，采用Java的float类型具体说明一下。
------------------------------------------------------------------------------------
类型          16进制           精确数值               说明                 Java输出
Zeros       0x00000000            +0                   正零                      0.0
Subnormals  0x00000001      2^(-23)*2^(-126)         MIN_VALUE               1.4E-45
Subnormals  0x007fffff    (1-2^(-23))*2^(-126)                         1.1754942E-38
Normals     0x00800000          2^(-126)             MIN_NORMAL       1.17549435E-38
Normals     0x7f7fffff     (2-2^(-23))*2^(127)       MAX_VALUE          3.4028235E38
Infinities  0x7f800000                           POSITIVE_INFINITY          Infinity
SNaNs       0x7f800001                                  NaN                      NaN
NaNs        0x7fffffff                                  NaN                      NaN
Zeros       0x80000000            -0                   负零                     -0.0
Subnormals  0x80000001     -2^(-23)*2^(-126)        -MIN_VALUE              -1.4E-45
Subnormals  0x807fffff   -(1-2^(-23))*2^(-126)                        -1.1754942E-38
Normals     0x80800000         -2^(-126)            -MIN_NORMAL      -1.17549435E-38
Normals     0xff7fffff    -(2-2^(-23))*2^(127)      -MAX_VALUE         -3.4028235E38
Infinities  0xff800000                           NEGATIVE_INFINITY         -Infinity
SNaNs       0xff800001                                  NaN                      NaN
NaNs        0xffffffff                                  NaN                      NaN
------------------------------------------------------------------------------------

3 浮点格式转换
a 二进制浮点数转十进制（二进制浮点数符号位S，指数E，尾数M；数值V）：
V = (-1)^s * 2^E * M

当指数E为全0时：E=1-(2^K-1)， M=m
即在REAL*4时：E=1-(2^(8-1)-1)=1-127=-126
V=(-1)^s*2^(-126)*m

当E不为全0且不为全1时：E=e值-(2^K-1)， M=1+m
即在REAL *4时：E=e值-(2^(8-1)-1)= e值-127
V=(-1)^s*2^(e值-127)*(1+m)

注：指数E为全0时表示纯小数，Nth位为0。

b 十进制转二进制浮点数
首先确定十进制浮点数在该精度表示范围内。
将整数部分和小数部分分别转换为二进制：整数部分采用除2取余，小数部分采用乘2取整。
将转换结果进行规格化：移动小数点p位至二进制最高位后（左移p取正，右移p取负且最多移2^K-2位）。
将整数部分q舍去，取小数部分前N-1位（后补0）作为尾数部分。
将p+q+126转换为二进制做指数。
符号位按正数取0负数取1。
合成符号位、指数部分和尾数部分得到二进制浮点数表示。

4 转换举例（转载）
0x00280000（REAL*4）
转换成二进制
00000000001010000000000000000000
符号位 指数部分（8位） 尾数部分
0 00000000 01010000000000000000000
符号位=0；因指数部分=0，则：尾数部分M为m：
0.01010000000000000000000=0.3125
该浮点数的十进制为：
(-1)^0*2^(-126)*0.3125 = 3.6734198463196484624023016788195e-39

0xC04E000000000000（REAL*8）
转换成二进制
1100000001001110000000000000000000000000000000000000000000000000
符号位 指数部分（11位） 尾数部分
1 10000000100 1110000000000000000000000000000000000000000000000000
符号位=1；指数=1028，因指数部分不为全'0'且不为全'1'，则：尾数部分M为1+m：
1.1110000000000000000000000000000000000000000000000000=1.875
该浮点数的十进制为：
(-1)^1*2^(1028-1023)*1.875 = -60

26.0
十进制26.0转换成二进制
11010.0
规格化二进制数
1.10100*2^4
计算指数
4+127=131
符号位 指数部分 尾数部分
0 10000011 10100000000000000000000
以单精度（REAL*4）浮点格式存储该数
0100 0001 1101 0000 0000 0000 0000 0000
0x41D0 0000

0.75
十进制0.75转换成二进制
0.11
规格化二进制数
1.1*2^-1
计算指数
-1+127=126
符号位 指数部分 尾数部分
0 01111110 10000000000000000000000
以单精度（REAL*4）浮点格式存储该数
0011 1111 0100 0000 0000 0000 0000 0000
0x3F40 0000

-2.5
十进制-2.5转换成二进制
-10.1
规格化二进制数
-1.01*2^1
计算指数
1+127=128
符号位 指数部分 尾数部分
1 10000000 01000000000000000000000
以单精度（REAL*4）浮点格式存储该数
1100 0000 0010 0000 0000 0000 0000 0000
0xC020 0000

密码学的历史还是很久的，我所比较感兴趣的是那个二战期间德国发明的密码机Enigma(我的java相关日志里有一篇关于Enigma的文章，就是用个简单的算法小模拟了一下他)。不管怎么说，密码学还是很重要的！目前主要用于数据加密，身份验证，数字签名，数据完整性验证等等等，总之很多方面了。用途较广泛的密码学算法主要是：对称加密算法，非对称加密算法和散列算法。

1 对称加密采用了对称密码编码技术，它的特点是文件加密和解密使用相同的密钥，即加密密钥也可以用作解密密钥。这种方法在密码学中叫做对称加密算法，对称加密算法使用起来简单快捷，密钥较短，且破译困难，除了数据加密标准（DES），另一个对称密钥加密系统系统是国际数据加密算法（IDEA），它比DNS的加密性好，而且对计算机功能要求也没有那么高。IDEA加密标准由PGP（Pretty Good Privacy）系统使用。

常见的有：
DES（Data Encryption Standard）：数据加密标准，速度较快，适用于加密大量数据的场合。
3DES（Triple DES）：是基于DES，对一块数据用三个不同的密钥进行三次加密，强度更高。
AES（Advanced Encryption Standard）：高级加密标准，是下一代的加密算法标准，速度快，安全级别高；

2 与对称加密算法不同，非对称加密算法需要两个密钥：公开密钥（publickey）和私有密钥（privatekey）。公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。 

常见的有：
RSA：由 RSA 公司发明，是一个支持变长密钥的公共密钥算法，需要加密的文件块的长度也是可变的；
DSA（Digital Signature Algorithm）：数字签名算法，是一种标准的 DSS（数字签名标准）；
ECC（Elliptic Curves Cryptography）：椭圆曲线密码编码学。

3 散列是信息的提炼，通常其长度要比信息小得多，且为一个固定长度。加密性强的散列一定是不可逆的，这就意味着通过散列结果，无法推出任何部分的原始信息。任何输入信息的变化，哪怕仅一位，都将导致散列结果的明显变化，这称之为雪崩效应。散列还应该是防冲突的，即找不出具有相同散列结果的两条信息。具有这些特性的散列结果就可以用于验证信息是否被修改。

常见的有：
MD5（Message Digest Algorithm 5）：是RSA数据安全公司开发的一种单向散列算法。
SHA（Secure Hash Algorithm）：可以对任意长度的数据运算生成一个160位的数值。

4 应用举例
保密通信：保密通信是密码学产生的动因。使用公私钥密码体制进行保密通信时，信息接收者只有知道对应的密钥才可以解密该信息。

数字签名：数字签名技术可以代替传统的手写签名，而且从安全的角度考虑，数字签名具有很好的防伪造功能。在政府机关、军事领域、商业领域有广泛的应用环境。

秘密共享：秘密共享技术是指将一个秘密信息利用密码技术分拆成n个称为共享因子的信息，分发给n个成员，只有k(k≤n)个合法成员的共享因子才可以恢复该秘密信息，其中任何一个或m(m≤k)个成员合作都不知道该秘密信息。利用秘密共享技术可以控制任何需要多个人共同控制的秘密信息、命令等。

认证功能：在公开的信道上进行敏感信息的传输，采用签名技术实现对消息的真实性、完整性进行验证，通过验证公钥证书实现对通信主体的身份验证。

密钥管理：密钥是保密系统中更为脆弱而重要的环节，公钥密码体制是解决密钥管理工作的有力工具；利用公钥密码体制进行密钥协商和产生，保密通信双方不需要事先共享秘密信息；利用公钥密码体制进行密钥分发、保护、密钥托管、密钥恢复等。

另外，我从网上看到了一个关于非对称加密和散列应用结合的例子，写得很详细，值得一看：
A欲传（信息）给B，但又怕B不确信该信息是A发的。  
1 A选计算（信息）的HASH值，如用MD5方式计算,得到：[MD5（信息）]
2 然后用自已的私钥加密HASH值，得到：[私钥（MD5（信息））]
3 最后将信息与密文一起传给B：传给B：[（信息） + 私钥（MD5（信息））]
B接到：[（信息） + 私钥（MD5（信息））]
1 先用相同的HASH算法算出（信息）的HASH值，这里也使用MD5方式得到：[MD5（信息）!]  
2 再用A的公钥解密[私钥（MD5（信息））]
[公钥(私钥（MD5（信息））)] = [（MD5（信息）]
  如能解开,证明该[私钥（MD5（信息））]是A发送的
3 再比效[MD5（信息）!]与[（MD5（信息）]
  如果相同,表示（信息）在传递过程中没有被他人修改过

PS：我们在具体应用密码学算法的时候可以根据需要综合使用多种算法，以达到完美的功能和更佳的效果。

附上简短的RSA代码示例
using System;

using System.Collections.Generic;

using System.Text;

using System.IO;

using System.Security.Cryptography;

namespace Com.Trial

{

    public class RSAExample

    {

        public RSAExample()

        {

        }

        //读取私钥信息

        private void ReadPrivateKey(RSACryptoServiceProvider rsa)

        {

            StreamReader reader = new StreamReader("PublicAndPrivateKey.xml");

            string PPKey = reader.ReadToEnd();

            rsa.FromXmlString(PPKey);

            reader.Close();

        }

        //读取公钥信息

        private void ReadPublicKey(RSACryptoServiceProvider rsa)

        {

            StreamReader reader = new StreamReader("PublicKey.xml");

            string PKey = reader.ReadToEnd();

            rsa.FromXmlString(PKey);

            reader.Close();

        }

        //公钥加密

        public byte[] RSAEncrypt(byte[] dataToEncrypt)

        {

            try

            {

                RSACryptoServiceProvider rsa = new RSACryptoServiceProvider();

                ReadPublicKey(rsa);

                byte[] EncryptedData = rsa.Encrypt(dataToEncrypt, false);

                return EncryptedData;

            }

            catch (CryptographicException e)

            {

                Console.WriteLine(e.Message);

                return null;

            }

        }

        //私钥解密

        public byte[] RSADecrypt(byte[] dataToEncrypt)

        {

            try

            {

                RSACryptoServiceProvider rsa = new RSACryptoServiceProvider();

                ReadPrivateKey(rsa);

                byte[] DecryptedData = rsa.Decrypt(dataToEncrypt, false);

                return DecryptedData;

            }

            catch (CryptographicException e)

            {

                Console.WriteLine(e.Message);

                return null;

            }

        }

        //私钥签名

        public byte[] SignData(byte[] DataToVerify)

        {

            try

            {

                RSACryptoServiceProvider RSAalg = new RSACryptoServiceProvider();

                ReadPrivateKey(RSAalg);

                return RSAalg.SignData(DataToVerify, new SHA1CryptoServiceProvider());

            }

            catch (CryptographicException e)

            {

                Console.WriteLine(e.Message);

                return null;

            }

        }

        //公钥验证

        public bool VerifyData(byte[] DataToVerify, byte[] SignedData)

        {

            try

            {

                RSACryptoServiceProvider RSAalg = new RSACryptoServiceProvider();

                ReadPublicKey(RSAalg);

                return RSAalg.VerifyData(DataToVerify, new SHA1CryptoServiceProvider(), SignedData);

            }

            catch (CryptographicException e)

            {

                Console.WriteLine(e.Message);

                return false;

            }

        }

        //生成密钥对

        public void GenerateKeys()

        {

            RSACryptoServiceProvider rsa = new RSACryptoServiceProvider();

            StreamWriter writer = null;

            //保存私钥

            string PPKeyXml;

            writer = new StreamWriter("PublicAndPrivateKey.xml");

            PPKeyXml = rsa.ToXmlString(true);

            writer.Write(PPKeyXml);

            writer.Close();

            //保存公钥

            string PKeyXml;

            writer = new StreamWriter("PublicKey.xml");

            PKeyXml = rsa.ToXmlString(false);

            writer.Write(PKeyXml);

            writer.Close();

        }

    }

}