哈希算法与二叉树_二叉树哈希

哈希算法

哈希算法的定义

1. Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。
2. 这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

哈希算法的特点

3. Hash算法可以将一个数据转换为一个标志，这个标志和源数据的每一个字节都有十分紧密的关系。Hash算法还具有一个特点，就是很难找到逆向规律。
4. Hash算法是一个广义的算法，也可以认为是一种思想，使用Hash算法可以提高存储空间的利用率，可以提高数据的查询效率，也可以做数字签名来保障数据传递的安全性。所以Hash算法被广泛地应用在互联网应用中。
5. Hash算法也被称为散列算法，Hash算法虽然被称为算法，但实际上它更像是一种思想。Hash算法没有一个固定的公式，只要符合散列思想的算法都可以被称为是Hash算法。

常用的哈希算法

6. 直接寻址法。取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）
7. 数字分析法。分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
8. 平方取中法。取关键字平方后的中间几位作为散列地址。
9. 折叠法。将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。
10. 除留余数法。取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生碰撞。

二叉树

二叉树的定义

11. 二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。

二叉树的类型

12. 完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
13. 满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
14. 平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉树的性质

15. 在非空二叉树中，第i层的结点总数不超过 , i>=1；
16. 深度为h的二叉树最多有个结点(h>=1)，最少有h个结点；
17. 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
18. 具有n个结点的完全二叉树的深度为（注：[ ]表示向下取整）
19. 有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：若I为结点编号则 如果I>1，则其父结点的编号为I/2；
    如果2I<=N，则其左孩子（即左子树的根结点）的编号为2I；若2I>N，则无左孩子；
    如果2I+1<=N，则其右孩子的结点编号为2I+1；若2I+1>N，则无右孩子。
20. 给定N个结点，能构成h(N)种不同的二叉树。
    h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。
21. 设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i

存储结构

顺序存储方式

2345typenode=record
data:datatypel,
r:integer;
end;
vartr:array[1..n]ofnode;
1
2
3
4

链表存储方式

typebtree=^node；
node=record
data:datatye;
lchild,rchild:btree;
end;
1
2
3
4