前言
程序＝数据结构+算法
最近看数据结构方面的知识，整合记录下来，部分文章是转载的，链接贴后面
哈希Hashing
哈希碰撞
哈希能够将任意长度的数据映射到固定长度的数据。哈希函数返回的即是哈希值，如果两个不同的键得到相同的哈希值，即将这种现象称为碰撞。
链地址法
拉链法：将所有关键字为同义词的记录存储在同一线性链表中.基本思想:将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。Java中HashMap是利用“拉链法”处理HashCode的碰撞问题。
再哈希法
当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。
比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止
开地址法
在开地址法中，当插入新值时，会判断该值对应的哈希桶是否存在，如果存在则根据某种算法依次选择下一个可能的位置，直到找到一个尚未被占用的地址。所谓开地址法也是指某个元素的位置并不永远由其哈希值决定。
Hash Map
Hash Map 是一种能够建立起键与值之间关系的数据结构，Hash Map 能够使用哈希函数将键转化为桶或者槽中的下标，从而优化对于目标值的搜索速度。
重写hashcode和equals
HashCode是使用Key通过Hash函数计算出来的，由于不同的Key，通过此Hash函数可能会算的同样的HashCode，所以此时用了拉链法解决冲突，把HashCode相同的Value连成链表. 但是get的时候根据Key又去桶里找，如果是链表说明是冲突的，此时还需要检测Key是否相同。
键值对存储在HashMap的Entry链表中，链表的节点标识为hashcode，每个键值对都有一个hashcode（可以重复）。
插入新的键值对，查找是否存在时，为了提升效率，会先计算hashcode，在链表上寻找该hashcode的节点，
若无则创建新节点，若存在，则在该节点上的链表**上（拉链法）寻找是否有 **equals的，若有equals的则更新值，若无则创建新节点。
算法
快速查找算法
快速查找法是给基准数据找到其正确索引位置的过程，是分治法思想的一种实现
package com.nrsc.sort;
public class QuickSort {
public static void main(String[] args) {
int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后:");
for (int i : arr) {
System.out.println(i);
}
}
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 找寻基准数据的正确索引
int index = getIndex(arr, low, high);
// 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
//quickSort(arr, 0, index - 1); 之前的版本，这种姿势有很大的性能问题，谢谢大家的建议
quickSort(arr, low, index - 1);
quickSort(arr, index + 1, high);
}
}
private static int getIndex(int[] arr, int low, int high) {
// 基准数据
int tmp = arr[low];
while (low < high) {
// 当队尾的元素大于等于基准数据时,向前挪动high指针
while (low < high && arr[high] >= tmp) {
high--;
}
// 如果队尾元素小于tmp了,需要将其赋值给low
arr[low] = arr[high];
// 当队首元素小于等于tmp时,向前挪动low指针
while (low < high && arr[low] <= tmp) {
low++;
}
// 当队首元素大于tmp时,需要将其赋值给high
arr[high] = arr[low];
}
// 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
// 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
arr[low] = tmp;
return low; // 返回tmp的正确位置
}
}
位运算
位运算即是在位级别进行操作的技术，合适的位运算能够帮助我们得到更快地运算速度与更小的内存使用。
测试第 k 位: s & (1 << k)
设置第 k 位: s |= (1 << k)
第 k 位置零: s &= ~(1 << k)
切换第 k 位值: s = ~(1 << k)
乘以 2n: s << n
除以 2n: s >> n
交集: s & t
并集: s | t
减法: s & ~t
交换 x = x y (y = x)
取出最小非 0 位（Extract lowest set bit）: s & (-s)
取出最小 0 位（Extract lowest unset bit）: ~s & (s + 1)
交换值:
x = y; y = x; x = y;
二叉查找树
二叉排序树，亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。
定义
一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的结点。
查找
步骤：若根结点的关键字值等于查找的关键字，成功。
否则，若小于根结点的关键字值，递归查左子树。
若大于根结点的关键字值，递归查右子树。
若子树为空，查找不成功。
平均情况分析（在成功查找两种的情况下）：
在一般情况下，设 P（n，i）为它的左子树的结点个数为 i 时的平均查找长度。如图的结点个数为 n = 6 且 i = 3; 则 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6
注意：这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。 在一般情况，P（i）为具有 i 个结点二叉分类树的平均查找长度。平均查找长度= 每个结点的深度的总和 / 总结点数
（上图应为左子树P(3)，右子树P(2)）
P(3) = （1+2+2）/ 3 = 5/3
P(2) = （1+2）/ 2 = 3/2∴ P（n,i）= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n
∴ P（n）= P（n,i）/ n <= 2(1+I/n)lnn
因为 2(1+I/n)lnn≈1.38logn 故P(n)=O(logn)
插入结点
树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
插入算法
首先执行查找算法，找出被插结点的父亲结点。
判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。
若二叉树为空。则首先单独生成根结点。
注意：新插入的结点总是叶子结点。
struct BiTree {
int data;
BiTree *lchild;
BiTree *rchild;
};
//在二叉排序树中插入查找关键字key
BiTree* InsertBST(BiTree *t,int key)
{
if (t == NULL)
{
t = new BiTree();
t->lchild = t->rchild = NULL;
t->data = key;
return t;
}
if (key < t->data)
t->lchild = InsertBST(t->lchild, key);
else
t->rchild = InsertBST(t->rchild, key);
return t;
}
//n个数据在数组d中，tree为二叉排序树根
BiTree* CreateBiTree(BiTree *tree, int d[], int n)
{
for (int i = 0; i < n; i++)
tree = InsertBST(tree, d[i]);
}
删除结点
在二叉排序树删去一个结点，分三种情况讨论：
1：若p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则可以直接删除此子结点。
2：若p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点f的左子树或右子树即可，作此修改也不破坏二叉排序树的特性。
3：若p结点的左子树和右子树均不空。在删去p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：
其一是令p的左子树为f的左/右子树，s为p左子树的最右下的结点，而p的右子树为s的右子树；
其二是令p的直接前驱或后继替代p，然后再从二叉排序树中删去它的直接前驱或后继，即让f的左子树成为p左子树的最左下结点，再让f成为p的左右结点的父结点。
当我们删除 30 节点的时候，整个中序遍历的结果中，从 32 开始都往前移动了一位。32 是 30 的后继节点，就是比 30 大的节点中最小的节点。当某个节点存在右节点时，后继结点就是右节点中的最小值，由于左侧节点总比右侧节点和父节点小，所以后继节点一定没有左节点。从这一个特点就能看出来，后继结点有可能存在右节点，也有可能没有任何节点。后继结点还有一个特点，就是他比 30 的左节点大，比 30 所有的右节点都小，因此删除 30 的时候，可以直接将后继结点 32 的值（key）转移到 30 节点上，然后删除后继结点 32。由于后继结点最多只有一个子节点，因此删除后继节点时，图示如下：
在二叉排序树上删除一个结点的算法如下：
删除算法
/**
*方法名称：delete()
*方法描述：删除结点
*@param采用递归的方式进行删除
*@returnString
*@Exception
*/
private void deleteNode(BinarySortTree p)
{
//TODOAuto-generatedmethodstub
if(p!=null)
{
//如果结点有左子树
/*1。若p有左子树，找到其左子树的最右边的叶子结点r，用该叶子结点r来替代p，把r的左孩子
作为r的父亲的右孩子。
2。若p没有左子树，直接用p的右子数取代它。
*/
if(p.lChild!=null)
{
BinarySortTree r=p.lChild;
BinarySortTree prev=p.lChild;
while(r.rChild!=null)
{
prev=r;
r=r.rChild;
}
p.data=r.data;
//若r不是p的左子树,p的左子树不变，r的左子树作为r的父结点的右孩子结点
if(prev!=r)
{
prev.rChild=r.lChild;
}
else
{
//若r是p的左子树，则p的左子树指向r的左子树
p.lChild=r.lChild;
}
}
else
{
p=p.rChild;
}
}
}
性能分析
每个结点的C(i)为该结点的层次数。
最坏情况下，当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为其平均查找长度(n+1)/2(和顺序查找相同）
最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log 2 (n)成正比。
也就是说，最好情况下的算法时间复杂度为O(1)，最坏情况下的算法时间复杂度为O(n)。
参考地址
链接: 数据结构与算法（java）
链接: 二叉查找树 - 删除节点 详解