可参考：http://dongxicheng.org/structure/trietree/
http://www.cnblogs.com/v-July-v/archive/2011/10/22/2316412.html
1、 概述
Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。
Trie一词来自retrieve，发音为/tri:/ “tree”，也有人读为/traɪ/ “try”。
Trie树可以利用字符串的公共前缀来节约存储空间。如下图所示，该trie树用10个节点保存了6个字符串tea，ten，to，in，inn，int：
位运算不管是在Java语言，还是在C语言中，或者其他语言，都是经常会用到的，所以本文也就不固定以某种语言来举例子了，原始点就从0、1开始。位运算主要包括按位与(&)、按位或(|)、按位异或(^)、取反(~)、左移(<<)、右移(>>)这几种，其中除了取反(~)以外，其他的都是二目运算符，即要求运算符左右两侧均有一个运算量。
1、补码
在总结按位运算前，有必要先介绍下补码的知识，我们知道当将一个十进制正整数转换为二进制数的时候，只需要通过除2取余的方法即可，但是怎么将一个十进制的负整数转换为二进制数呢？其实，负数是以补码的形式表示，其转换方式，简单的一句话就是：先按正数转换，然后取反加1。
要将十进制的-10用二进制表示，先将10用二进制表示： 0000 0000 0000 1010 取反： 1111 1111 1111 0101 加1： 1111 1111 1111 0110 所以，-10的二进制表示就是：1111 1111 1111 0110
2、按位与(&)
参加运算的两个数，换算为二进制(0、1)后，进行与运算。只有当相应位上的数都是1时，该位才取1，否则该为为0。
将10与-10进行按位与(&)运算： 0000 0000 0000 1010 1111 1111 1111 0110 ----------------------- 0000 0000 0000 0010 所以：10 & -10 = 0000 0000 0000 0010
3、按位或(|)
参加运算的两个数，换算为二进制(0、1)后，进行或运算。只要相应位上存在1，那么该位就取1，均不为1，即为0。
将10与-10进行按位或(|)运算： 0000 0000 0000 1010 1111 1111 1111 0110 ----------------------- 1111 1111 1111 1110 所以：10 | -10 = 1111 1111 1111 1110
4、按位异或(^)
参加运算的两个数，换算为二进制(0、1)后，进行异或运算。只有当相应位上的数字不相同时，该为才取1，若相同，即为0。
将10与-10进行按位异或(^)运算： 0000 0000 0000 1010 1111 1111 1111 0110 ----------------------- 1111 1111 1111 1100 所以：10 ^ -10 = 1111 1111 1111 1100
可以看出，任何数与0异或，结果都是其本身。利用异或还可以实现一个很好的交换算法，用于交换两个数，算法如下：
a = a ^ b; b = b ^ a; a = a ^ b;
5、取反(~)
参加运算的两个数，换算为二进制(0、1)后，进行取反运算。每个位上都取相反值，1变成0，0变成1。
对10进行取反(~)运算： 0000 0000 0000 1010 --------------------- 1111 1111 1111 0101 所以：~10 = 1111 1111 1111 0101
6、左移(<<)
参加运算的两个数，换算为二进制(0、1)后，进行左移运算，用来将一个数各二进制位全部向左移动若干位。
对10左移2位(就相当于在右边加2个0)： 0000 0000 0000 1010 -------------------- 0000 0000 0010 1000 所以：10 << 2 = 0000 0000 0010 1000 = 40
注意，观察可以发现，左移一位的结果就是原值乘2，左移两位的结果就是原值乘4。
7、右移(>>)
参加运算的两个数，换算为二进制(0、1)后，进行右移运算，用来将一个数各二进制位全部向右移动若干位。
对10右移2位(就相当于在左边加2个0)： 0000 0000 0000 1010 -------------------- 0000 0000 0000 0010 所以：10 >> 2 = 0000 0000 0000 0010 = 2
注意，观察可以发现，右移一位的结果就是原值除2，左移两位的结果就是原值除4，注意哦，除了以后没有小数位的，都是取整。
下面加一段php代码：
转载自：http://blogread.cn/it/article/7327
十进制转二进制
方法为：十进制数除2取余法，即十进制数除2，余数为权位上的数，得到的商值继续除2，依此步骤继续向下运算直到商为0为止。
（具体用法如下图）
二进制转十进制
方法为：把二进制数按权展开、相加即得十进制数。
（具体用法如下图）
二进制转八进制
方法为：3位二进制数按权展开相加得到1位八进制数。（注意事项，3位二进制转成八进制是从右到左开始转换，不足时补0）。
（具体用法如下图）
八进制转成二进制
方法为：八进制数通过除2取余法，得到二进制数，对每个八进制为3个二进制，不足时在最左边补零。
（具体用法如下图）
二进制转十六进制
方法为：与二进制转八进制方法近似，八进制是取三合一，十六进制是取四合一。（注意事项，4位二进制转成十六进制是从右到左开始转换，不足时补0）。
（具体用法如下图）
十六进制转二进制
方法为：十六进制数通过除2取余法，得到二进制数，对每个十六进制为4个二进制，不足时在最左边补零。
（具体用法如下图）
tip：union all比union多一项功能就是去重，因此union all效率要高于union
UNION 操作符用于合并两个或多个 SELECT 语句的结果集。
请注意，UNION 内部的 SELECT 语句必须拥有相同数量的列。列也必须拥有相似的数据类型。同时，每条 SELECT 语句中的列的顺序必须相同。
SELECT column_name(s) FROM table_name1 UNION SELECT column_name(s) FROM table_name2
注释：默认地，UNION 操作符选取不同的值。如果允许重复的值，请使用 UNION ALL。
SELECT column_name(s) FROM table_name1 UNION ALL SELECT column_name(s) FROM table_name2
另外，UNION 结果集中的列名总是等于 UNION 中第一个 SELECT 语句中的列名。
| E_ID | E_Name |
|---|---|
| 01 | Zhang, Hua |
| 02 | Wang, Wei |
| 03 | Carter, Thomas |
| 04 | Yang, Ming |
| E_ID | E_Name |
|---|---|
| 01 | Adams, John |
| 02 | Bush, George |
| 03 | Carter, Thomas |
| 04 | Gates, Bill |
列出所有在中国和美国的不同的雇员名：
SELECT E_Name FROM Employees_China
UNION
SELECT E_Name FROM Employees_USA
| E_Name |
|---|
| Zhang, Hua |
| Wang, Wei |
| Carter, Thomas |
| Yang, Ming |
| Adams, John |
| Bush, George |
| Gates, Bill |
注释：这个命令无法列出在中国和美国的所有雇员。在上面的例子中，我们有两个名字相同的雇员，他们当中只有一个人被列出来了。UNION 命令只会选取不同的值。
UNION ALL 命令和 UNION 命令几乎是等效的，不过 UNION ALL 命令会列出所有的值。
SQL Statement 1 UNION ALL SQL Statement 2
列出在中国和美国的所有的雇员：
SELECT E_Name FROM Employees_China
UNION ALL
SELECT E_Name FROM Employees_USA
| E_Name |
|---|
| Zhang, Hua |
| Wang, Wei |
| Carter, Thomas |
| Yang, Ming |
| Adams, John |
| Bush, George |
| Carter, Thomas |
| Gates, Bill |
在表中存在至少一个匹配时，INNER JOIN 关键字返回行。
SELECT column_name(s) FROM table_name1 INNER JOIN table_name2 ON table_name1.column_name=table_name2.column_name
注释：INNER JOIN 与 JOIN 是相同的。
“Persons” 表：
| Id_P | LastName | FirstName | Address | City |
|---|---|---|---|---|
| 1 | Adams | John | Oxford Street | London |
| 2 | Bush | George | Fifth Avenue | New York |
| 3 | Carter | Thomas | Changan Street | Beijing |
“Orders” 表：
| Id_O | OrderNo | Id_P |
|---|---|---|
| 1 | 77895 | 3 |
| 2 | 44678 | 3 |
| 3 | 22456 | 1 |
| 4 | 24562 | 1 |
| 5 | 34764 | 65 |
现在，我们希望列出所有人的定购。
您可以使用下面的 SELECT 语句：
SELECT Persons.LastName, Persons.FirstName, Orders.OrderNo FROM Persons INNER JOIN Orders ON Persons.Id_P=Orders.Id_P ORDER BY Persons.LastName
结果集：
| LastName | FirstName | OrderNo |
|---|---|---|
| Adams | John | 22456 |
| Adams | John | 24562 |
| Carter | Thomas | 77895 |
| Carter | Thomas | 44678 |
INNER JOIN 关键字在表中存在至少一个匹配时返回行。如果 “Persons” 中的行在 “Orders” 中没有匹配，就不会列出这些行。
cross join就是不加条件限制，inner join的on还是加了条件限制的
cross join 是笛卡尔积
In MySQL the CROSS JOIN produced a result set which is the product of rows of two associated tables when no WHERE clause is used with CROSS JOIN.
In this join the result set appeared by multiplying each row of the first table with all rows in the second table if no condition introduced with CROSS JOIN..
This kind of result is called as Cartesian Product.
In MySQL the CROSS JOIN behaves like JOIN and INNER JOIN of without using any condition.
In standard SQL the difference between INNER JOIN and CROSS JOIN is ON clause can be used with INNER JOIN on the other hand ON clause can’t be used with CROSS JOIN.
MySQL CROSS JOIN Syntax :
table_references:
escaped_table_reference [, escaped_table_reference] ...
escaped_table_reference:
table_reference
| { OJ table_reference }
table_reference:
table_factor
| join_table
table_factor:
tbl_name [PARTITION (partition_names)]
[[AS] alias] [index_hint_list]
| table_subquery [AS] alias
| ( table_references )
join_table:
table_reference [INNER | CROSS] JOIN table_factor [join_condition]
| table_reference STRAIGHT_JOIN table_factor
| table_reference STRAIGHT_JOIN table_factor ON conditional_expr
| table_reference {LEFT|RIGHT} [OUTER] JOIN table_reference join_condition
| table_reference NATURAL [{LEFT|RIGHT} [OUTER]] JOIN table_factor
join_condition:
ON conditional_expr
| USING (column_list)
index_hint_list:
index_hint [, index_hint] ...
index_hint:
USE {INDEX|KEY}
[FOR {JOIN|ORDER BY|GROUP BY}] ([index_list])
| IGNORE {INDEX|KEY}
[FOR {JOIN|ORDER BY|GROUP BY}] (index_list)
| FORCE {INDEX|KEY}
[FOR {JOIN|ORDER BY|GROUP BY}] (index_list)
index_list:
index_name [, index_name] ...
In the following example a Cartesian Product have retrieved.
Sample tables :
Output :
+------+-------+-------+------+-------+ | id | bval1 | bval2 | id | aval1 | +------+-------+-------+------+-------+ | 701 | 405 | 16 | 1 | 405 | | 704 | 409 | 14 | 1 | 405 | | 706 | 403 | 13 | 1 | 405 | | 709 | 401 | 12 | 1 | 405 | | 701 | 405 | 16 | 2 | 401 | | 704 | 409 | 14 | 2 | 401 | | 706 | 403 | 13 | 2 | 401 | | 709 | 401 | 12 | 2 | 401 | | 701 | 405 | 16 | 3 | 200 | | 704 | 409 | 14 | 3 | 200 | | 706 | 403 | 13 | 3 | 200 | | 709 | 401 | 12 | 3 | 200 | | 701 | 405 | 16 | 4 | 400 | | 704 | 409 | 14 | 4 | 400 | | 706 | 403 | 13 | 4 | 400 | | 709 | 401 | 12 | 4 | 400 | +------+-------+-------+------+-------+ 16 rows in set (0.05 sec)
In the following example, at first cross join between table112 and table133 have completed then executes the left join according to the specified condition.
Output :
+------+-------+------+-------+-------+------+-------+ | id | aval1 | id | bval1 | bval2 | id | cval1 | +------+-------+------+-------+-------+------+-------+ | 1 | 405 | 701 | 405 | 16 | 1 | 16 | | 1 | 405 | 704 | 409 | 14 | 1 | 16 | | 1 | 405 | 706 | 403 | 13 | 1 | 16 | | 1 | 405 | 709 | 401 | 12 | 1 | 16 | | 2 | 401 | 701 | 405 | 16 | 2 | 12 | | 2 | 401 | 704 | 409 | 14 | 2 | 12 | | 2 | 401 | 706 | 403 | 13 | 2 | 12 | | 2 | 401 | 709 | 401 | 12 | 2 | 12 | | 3 | 200 | 701 | 405 | 16 | 3 | 17 | | 3 | 200 | 704 | 409 | 14 | 3 | 17 | | 3 | 200 | 706 | 403 | 13 | 3 | 17 | | 3 | 200 | 709 | 401 | 12 | 3 | 17 | | 4 | 400 | NULL | NULL | NULL | NULL | NULL | +------+-------+------+-------+-------+------+-------+ 13 rows in set (0.00 sec)
In the following example, CROSS JOIN have been executed with WHERE clause and it is similar to the INNER JOIN with ON clause.
Output :
mysql> select table111.*,table113.*
-> from table111
-> cross join table113
-> where table111.id=table113.id;
+------+-------+------+-------+
| id | aval1 | id | cval1 |
+------+-------+------+-------+
| 3 | 200 | 3 | 17 |
| 2 | 401 | 2 | 12 |
| 1 | 405 | 1 | 16 |
+------+-------+------+-------+
3 rows in set (0.05 sec)
只要其中某个表存在匹配，FULL JOIN 关键字就会返回行。
SELECT column_name(s) FROM table_name1 FULL JOIN table_name2 ON table_name1.column_name=table_name2.column_name
注释：在某些数据库中， FULL JOIN 称为 FULL OUTER JOIN。
“Persons” 表：
| Id_P | LastName | FirstName | Address | City |
|---|---|---|---|---|
| 1 | Adams | John | Oxford Street | London |
| 2 | Bush | George | Fifth Avenue | New York |
| 3 | Carter | Thomas | Changan Street | Beijing |
“Orders” 表：
| Id_O | OrderNo | Id_P |
|---|---|---|
| 1 | 77895 | 3 |
| 2 | 44678 | 3 |
| 3 | 22456 | 1 |
| 4 | 24562 | 1 |
| 5 | 34764 | 65 |
现在，我们希望列出所有的人，以及他们的定单，以及所有的定单，以及定购它们的人。
您可以使用下面的 SELECT 语句：
SELECT Persons.LastName, Persons.FirstName, Orders.OrderNo FROM Persons FULL JOIN Orders ON Persons.Id_P=Orders.Id_P ORDER BY Persons.LastName
结果集：
| LastName | FirstName | OrderNo |
|---|---|---|
| Adams | John | 22456 |
| Adams | John | 24562 |
| Carter | Thomas | 77895 |
| Carter | Thomas | 44678 |
| Bush | George | |
| 34764 |
FULL JOIN 关键字会从左表 (Persons) 和右表 (Orders) 那里返回所有的行。如果 “Persons” 中的行在表 “Orders” 中没有匹配，或者如果 “Orders” 中的行在表 “Persons” 中没有匹配，这些行同样会列出。
RIGHT JOIN 关键字会右表 (table_name2) 那里返回所有的行，即使在左表 (table_name1) 中没有匹配的行。
SELECT column_name(s) FROM table_name1 RIGHT JOIN table_name2 ON table_name1.column_name=table_name2.column_name
注释：在某些数据库中， RIGHT JOIN 称为 RIGHT OUTER JOIN。
“Persons” 表：
| Id_P | LastName | FirstName | Address | City |
|---|---|---|---|---|
| 1 | Adams | John | Oxford Street | London |
| 2 | Bush | George | Fifth Avenue | New York |
| 3 | Carter | Thomas | Changan Street | Beijing |
“Orders” 表：
| Id_O | OrderNo | Id_P |
|---|---|---|
| 1 | 77895 | 3 |
| 2 | 44678 | 3 |
| 3 | 22456 | 1 |
| 4 | 24562 | 1 |
| 5 | 34764 | 65 |
现在，我们希望列出所有的定单，以及定购它们的人 – 如果有的话。
您可以使用下面的 SELECT 语句：
SELECT Persons.LastName, Persons.FirstName, Orders.OrderNo FROM Persons RIGHT JOIN Orders ON Persons.Id_P=Orders.Id_P ORDER BY Persons.LastName
结果集：
| LastName | FirstName | OrderNo |
|---|---|---|
| Adams | John | 22456 |
| Adams | John | 24562 |
| Carter | Thomas | 77895 |
| Carter | Thomas | 44678 |
| 34764 |
RIGHT JOIN 关键字会从右表 (Orders) 那里返回所有的行，即使在左表 (Persons) 中没有匹配的行。