把所有的元素按照完全二叉树的方式存储在一个一维数组中并满足Ki<=K2i+1且Ki<=K2i+2（Ki>=K2i+1且Ki>=K2i+2）,这个堆称为最小堆（最大堆）
堆的分类
小堆
任一节点的关键码均小于它左右孩子的关键码，位于堆顶结点的关键码最小
大堆
任一结点的关键码均大于它左右孩子的关键码，位于堆顶结点的关键码最大
堆的性质如果i=0，结点i是根结点，没有双亲结点，否则结点i的双亲结点为（i-1）/2
如果2i+1>n-1,则结点i无左孩子，否则结点i的左孩子为节点2i+1
如果2i+1>n-1,则结点i无左孩子，否则结点i的左孩子为节点2i+2
堆的创建从上向下调整
堆的插入 堆的删除 堆的应用优先级队列
Huffman树 概念路径
路径长度
把带权路径长度最小的树叫做Huffman树
构造huffman树
构造n棵只有根结点的二叉树森林，每棵二叉树都只有一个带有权值的根结点
重复以下步骤，直到F中只剩下一棵树
在二叉树森林中选最小的两个，作为左右子树构建一棵新的二叉树，新二叉树的根结点的权值为左右子树根结点的权值之和
在原来二叉树森林里删除这两棵二叉树
把新的二叉树加入二叉树森林
huffman编码
编码
在数据通信中经常把传输的文字转换成二进制字符0和1组成的二进制串，这叫做编码
等长编码
不等长编码
文件压缩 二叉搜索树 性质如果左子树不为空，则左子树上所有节点的值都小于根结点的值
它的右子树不为空，则右子树上所有节点的值都大于根结点的值
它的左右子树也分别为二叉搜索树
操作
搜索
若根结点不为空
根结点key==要查找的key，返回true
根结点key>查找key，在其左子树查找
根结点key<查找key，在其右子树查找
否则返回false
插入
首先检测这个节点是不是已经存在，要是存在不插入
否则将元素插入到找到的位置
删除
首先判断是否在树中，没有直接返回
有的情况
要删除的节点没有孩子节点
直接删除该结点
要删除的节点只有左孩子
删除该结点并使被删除结点的双亲结点指向被删除结点的左孩子结点
要删除的节点只有右孩子
删除该结点并使被删除结点的双亲结点指向被删除结点的右孩子结点
要删除的节点有左、右孩子结点
在它的右子树中寻找中序下的第一个结点（关键码最小），用它的值填补到被删除节点中，再来处理该结点的删除问题
二叉搜索树性能分析
最坏情况下，平均查找长度为O(n)一般情况下平均长度为O(lgn)
AVL树 AVL树性质它的左右子树都是AVL树
左子树和右子树高度之差（简称平衡因子）的绝对值不超过1（-1、0、1）
如果一棵树是高度平衡的，它就是AVL树。如果它有n个节点，其高度可保持在0(lgn)，平均搜索复杂度O(lgn)
平衡化旋转左单旋
右单旋
左右双旋
右左双旋
AVL树的插入如果是空树，插入后即为根结点，插入后直接返回true
如果树不空，寻找插入位置，若在查找过程中找到key，则插入失败直接返回false
插入节点
更新平衡因子，对树进行调整
AVL树的删除
被删除结点只有左孩子
parent的平衡因子为1或者-1，parent高度不变，则从parent到根所有结点高度均不变，不用调整
被删除结点只有右孩子
parent的平衡因子变成0，虽然以parent为根的子树平衡，其高度减1，但需要检查parent的双亲结点的平衡性
被删除结点左右孩子都有
变为删除中序遍历下的第一个结点q
结点parent的平衡因子为2或者-2，则较矮子数缩短，parent发生不平衡，需要进行平衡化旋转
parent较高子树的根为q
如果q的平衡因子为0，执行单循环恢复parent
如果q的平衡因子与parent平衡因子（正负）号相同，则执行一个单循环恢复parent
如果q的平衡因子与parent平衡因子（正负）号相反，则执行一个双旋转恢复parent
红黑树 概念红黑树是一棵二叉搜索树，它在每个节点上增加了一个存储位来表示结点的颜色，保证最长路径不超过最短路径的两倍，近似平衡
性质每个结点不是红色就是黑色
树的根结点是黑色
如果一个结点是红色的，则它的两个孩子结点是黑色的（没有连续的两个红色结点）
对于每个节点，从该结点到其所有后代叶节点的简单路径上，均包含相同数目的黑色结点（每条路径上黑色结点的数量相等）
每个叶子节点都是黑色的（此处的叶子结点指的是空节点）
插入实现若树为空，插入后需将新节点改成黑色
插入结点的父节点为黑色，不违反任何性质，直接插入
情况三
情况四
情况五
删除 运用C++STL库--map/set multimap multiset
Java库
linux 内核
其他一些库
红黑树和AVL树的比较 B树 平衡的多叉树 性质根结点至少有两个孩子
每个非根结点至少有M/2（上取整）个孩子，至多有M个孩子
每个非根结点至少有M/2-1（上取整）个关键字，并且以升序排列
key[i]和key[i+1]之间的孩子结点的值介于key[i]、key[i+1]之间
所有的叶子结点都在同一层
B+树
性质
其定义基本与B树相同
非叶子节点的子树指针与关键字个数相同
非叶子结点的子树指针P[i]，指向关键字值属于[k[i],k[i+1])的子树
为所有叶子节点增加一个链指针
所有关键字都在叶子节点出现
搜索
和B树基本相同
特性
所有关键字都出现在叶子节点的链表中（稠密索引），且链表中的关键字恰好是有序的
不可能在叶子结点命中
非叶子节点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层
更适合文件索引系统
B*树在B+树的非根和非叶子结点之间再增加指向兄弟的指针
子主题 2
哈希 搜索（检索）
在数据元素集合中查找是否存在关键字等于某个给定关键字数据元素的过程
结果
成功
失败
搜索结构
用于搜索的数据集合
搜索的环境
静态环境
在执行插入和删除等操作的前后搜索结构不会发生改变
动态环境
为保持较高的搜索效率，搜索结构在执行插入和删除等操作的前后将自动调整，结构可能会发生改变
查找
静态查找
顺序表
从前往后依次遍历O（n）
有序顺序表
二分查找O（log(n)）
索引顺序表
动态查找
二叉树结构
二叉排序树
平衡二叉树
树结构
B树
B+树
哈希查找
每个元素的关键码和结构中一个唯一的结存储位置相对应
散列方法
插入和查找数据利用哈希函数求出存储位置再存放或者查找
哈希冲突
对于两个数据Ki和Kj（i!=j）,Ki!=Kj,但是有Hash(Ki)==Hash(Kj)
散列函数
哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0-m-1之间
哈希函数计算出来的地址能均匀的分布在整个空间中
哈希函数应该比较简单
常见哈希函数
直接定址法
取关键字的某个线性函数为散列地址
优点：简单均匀
缺点：需要事先直到关键字的分布情况
使用场景：适合查找比较小且连续的情况
除留余数法
设散列中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key)=key%p,p<=m;将关键码转换成哈希地址
平方取中法
假设关键字是1234，平方就是1522756，再抽取中间的三位数227作为散列地址
折叠法
将关键字从左到右分成位数相等的几部分，然后将这几部分叠加求和，并按散列表长，取后几位作为散列地址
随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址
数学分析法