算法2

一.计算两个点的最小路径(Dijkstra算法)
二.计算图上任意点到其他点的最小路径(Floyd算法)
三.最小生成树算法
四.贪心算法
五.排序算法
六.查找算法

六.查找算法

• 查找分类：
  只做查找操作的查找表叫做静态查找表；
  在查找过程中，同时插入查找表中不存在的元素，或者删除已经存在的元素，叫做动态查找表。

1.顺序表查找

/*顺序表查找*/
-(void)seq_search
{
    int arr[]={32,14,7,9,5,27,56,18};
    for(int i=0;i<8;i++)
    {
        int t=arr[i];
        if(t==5)
        {
            printf("%d",i);
            break;
        }
    }
}

2.有序表查找

• 算法思路：
  有序表查找可以使用二分法进行查找，从中间找一个数，如果查找的数据大于该数，从右边继续查找，不然从左边继续查找。

/*有序表查找*/
-(void)sort_search:(int)key
{
    int arr[]={1,3,5,8,13,27,56,77};
    int low=0;
    int high=7;
    
    while(low<=high)
    {
        int mid=(low+high)/2;
        int temp=arr[mid];
        if(temp==key)
        {
            printf("%d",mid);
            break;
        }else if(temp>key)
        {
            high=mid-1;
        }else
        {
            low=mid+1;
        }
    }
    
}

• 优化思路：
  1.一个1-10000的间隔1的有序表，查找3和9999的位置，显然用二分查找会效率低，我们应该让mid更靠近真实位置。
  这种方式叫做插值查找，但是如果数据间隔相对离散，一样会降低效率。

//利用插值查找优化mid值
int mid=low+(high-low)*(key-arr[low])/(arr[high]-arr[low]);

2.添加线性索引
索引就是把一个关键字和对应记录关联的过程。

• 稠密索引：每个记录对应一个索引项。
• 分块索引：多个记录对应一个索引项，块内可以无序，块间有序(为了进行有序查找)，
• 倒排索引：记录号表存储具有相同次关键字的所有记录的记录号(可以是指向记录的指针或者是该记录的主关键字)。

3.二叉排序树

• 由来：
  如果用线性结构做一个有序的动态查找表，那么进行插入和删除都会影响到其他数据的位置，这样会影响到效率，所以想到二叉排序树这种结构。

• 概念：
  又称为二叉查找树，它满足一下性质：
  若它的左子树不空，则左子树上所有节点的值均小于它的根结构的值；
  若它的右子树不空，则右子树上所有节点的值均大于它的根结构的值；
  它的左右子树也分别为二叉排序树。
  eg：这是一颗二叉查找树，把这颗二叉查找树进行中序遍历(左-根-右)就可以进行有序输出。

  
  1.png

• 初始化和中序遍历
  使用Objective-C进行模拟树的数据结构

@interface TreeNode : NSObject
@property(nonatomic,assign)int data;
@property(nonatomic,strong)TreeNode* leftNode;
@property(nonatomic,strong)TreeNode* rightNode;
-(instancetype)initWithData:(int)data andLeft:(TreeNode*)left andRight:(TreeNode*)right;
@end

二叉查找树的初始化构建(也可通过插入法，后面会说)和中序遍历

/*二叉查找树构建*/
-(TreeNode*)buildTree
{
    TreeNode * node1=[[TreeNode alloc]initWithData:37 andLeft:nil andRight:nil];
    TreeNode * node2=[[TreeNode alloc]initWithData:35 andLeft:nil andRight:node1];
    TreeNode * node3=[[TreeNode alloc]initWithData:51 andLeft:nil andRight:nil];
    TreeNode * node4=[[TreeNode alloc]initWithData:47 andLeft:node2 andRight:node3];
    TreeNode * node5=[[TreeNode alloc]initWithData:58 andLeft:node4 andRight:nil];
    TreeNode * node6=[[TreeNode alloc]initWithData:93 andLeft:nil andRight:nil];
    TreeNode * node7=[[TreeNode alloc]initWithData:99 andLeft:node6 andRight:nil];
    TreeNode * node8=[[TreeNode alloc]initWithData:73 andLeft:nil andRight:nil];
    TreeNode * node9=[[TreeNode alloc]initWithData:88 andLeft:node8 andRight:node7];
    TreeNode * tree=[[TreeNode alloc]initWithData:62 andLeft:node5 andRight:node9];
    return tree;
}

/*二叉查找树中序遍历*/
-(void)traverseTree:(TreeNode*)tree
{
    if(tree==nil)
        return;
    [self traverseTree:tree.leftNode];
    printf("%d ",tree.data);
    [self traverseTree:tree.rightNode];
}

• 二叉查找树的查找
  算法思路：
  从根节点开始，进行比较，如果相等则找到；如果大于，则从右子树开始递归比较；如果小于，则从左子树开始递归比较；直到子树为空还没找到，那么就没有找到该值。

/*二叉查找树查找*/
-(void)tree_search:(TreeNode*)tree andKey:(int)key
{
    if(tree==nil)
    {
        printf("没有找到%d",key);
        return;
    }
    if(tree.data==key)
    {
        printf("找到%d",key);
    }else if(tree.data>key)
    {
        [self tree_search:tree.leftNode andKey:key];
    }else
    {
        [self tree_search:tree.rightNode andKey:key];
    }
}

• 二叉树的数据插入
  当没有查找到该数据的情况下，把数据插入二叉查找树中。
  算法思路：
  通过不断深入比较，找到没有左/右叶子的节点，如果大于此时根节点插入右节点，否认插入到左节点；如果是左右都有的节点肯定可以继续比较，不会插入。

  
  1.png

/*二叉查找树插入*/
-(void)tree_insert:(TreeNode*)tree andKey:(int)key
{
    //构建插入节点
    TreeNode * node=[[TreeNode alloc]initWithData:key andLeft:nil andRight:nil];
    while(tree)
    {
        if(tree.data<key)
        {
            if(tree.rightNode==nil)
            {
                tree.rightNode=node;
                break;
            }else
            {
                tree=tree.rightNode;
            }
        }else
        {
            if(tree.leftNode==nil)
            {
                tree.leftNode=node;
                break;
            }else
            {
                tree=tree.leftNode;
            }
        }
    }
}

使用插入法构建一颗二叉查找树：

    TreeNode * tree=[[TreeNode alloc]initWithData:50 andLeft:nil andRight:nil];
    int arr[10]={30,88,75,74,21,42,57,12,99,66};
    printf("插入前:");
    [self traverseTree:tree];
    for(int i=0;i<10;i++)
    {
        [self tree_insert:tree andKey:arr[i]];
    }
    printf("插入后:");
    [self traverseTree:tree];

• 二叉树的数据删除
  当查找到该数据的情况下，需要把该数据从二叉查找树中移除。
  算法思路：
  需要分类进行梳理：
  如果删除的是只有左子树或者只有右子树，甚至都没有的节点，只需要将该节点的父节点重新指向该左/右节点；

  
  1.png
  

  eg:删除58这个节点，影响的是其中黄色节点，62节点左子树指向47节点就行了。

  
  2.png
  如果删除的是既有左子树又有右子树的节点，需要调整的节点就比较多了。
  eg:删除47这个节点。
  1.png
  a.首先考虑的是该节点的位置被谁替代，最合理的数是最接近该数的那个数，也就是中序遍历有序表该数字的前一个或者后一个。
  那么这个数如果找到呢，如果是该数的前驱节点，需要找到左子树最大的那个数，如果是后驱节点，需要找到右子树最小的那个数。图中以前驱节点为例子，47的前驱节点是37。
  b.找到该前驱节点后，把47的父节点58左子树修改为该前驱节点37；同时调整删除节点47的右子树为该前驱节点37的右子树；前驱节点37的左子树变成它的根节点(前驱节点根节点)35的右子树；前驱节点的左子树变成删除节点左子树。如下图2
  

  c.还有一种情况，就是前驱节点就是删除的左子树根节点(该左子树没有右子树)，那么直接修改删除节点父节点的指向就行。

  
  3.png
  d.如果删除节点在右边同左边的原理一样。

我们发现需要在之前的树数据结构中添加父节点更容易解决。

@interface TreeNode : NSObject
@property(nonatomic,assign)int data;
@property(nonatomic,strong)TreeNode* leftNode;
@property(nonatomic,strong)TreeNode* rightNode;
@property(nonatomic,strong)TreeNode* parent;
-(instancetype)initWithData:(int)data andLeft:(TreeNode*)left andRight:(TreeNode*)right;
@end

-(TreeNode*)buildTree
{
    TreeNode * node1=[[TreeNode alloc]initWithData:37 andLeft:nil andRight:nil];
    TreeNode * node2=[[TreeNode alloc]initWithData:35 andLeft:nil andRight:node1];
    TreeNode * node3=[[TreeNode alloc]initWithData:51 andLeft:nil andRight:nil];
    TreeNode * node4=[[TreeNode alloc]initWithData:47 andLeft:node2 andRight:node3];
    TreeNode * node5=[[TreeNode alloc]initWithData:58 andLeft:node4 andRight:nil];
    TreeNode * node6=[[TreeNode alloc]initWithData:93 andLeft:nil andRight:nil];
    TreeNode * node7=[[TreeNode alloc]initWithData:99 andLeft:node6 andRight:nil];
    TreeNode * node8=[[TreeNode alloc]initWithData:73 andLeft:nil andRight:nil];
    TreeNode * node9=[[TreeNode alloc]initWithData:88 andLeft:node8 andRight:node7];
    TreeNode * tree=[[TreeNode alloc]initWithData:62 andLeft:node5 andRight:node9];
    
    node9.parent=tree;
    node8.parent=node9;
    node7.parent=node9;
    node6.parent=node7;
    node5.parent=tree;
    node4.parent=node5;
    node3.parent=node4;
    node2.parent=node4;
    node1.parent=node2;
    
    return tree;
}

先递归找到删除的节点再进行删除节点算法

/*二叉查找树删除*/
-(void)tree_delete:(TreeNode*)tree andKey:(int)key
{
    if(tree==nil)
        return;
    
    if(tree.data==key)
    {
        [self deleteNode:tree];
    }else if(tree.data>key)
    {
        [self tree_delete:tree.leftNode andKey:key];
    }else
    {
        [self tree_delete:tree.rightNode andKey:key];
    }
}

/*删除节点后对数进行调整*/
-(void)deleteNode:(TreeNode*)node
{
    //左右子树有一个为空的情况
    if(node.rightNode==nil||node.leftNode==nil)
    {
        if(node.parent.leftNode.data==node.data)
        {
            TreeNode * leftTree=node.leftNode;
            node.parent.leftNode=leftTree;
        }else
        {
            TreeNode * rightTree=node.rightNode;
            node.parent.rightNode=rightTree;
        }
    }
    //左右子树都不为空的情况
    else
    {
        TreeNode * leftTree=node.leftNode;
        //记录前驱节点
        TreeNode * maxPreNode=node.leftNode;
        //记录前驱节点的根节点
        TreeNode * premaxPreNode=maxPreNode;
        while (maxPreNode.rightNode) {
            premaxPreNode=maxPreNode;
            maxPreNode=maxPreNode.rightNode;
        }
        //删除的节点是父节点的左子树根节点
        if(node.parent.leftNode.data==node.data)
        {
            if(leftTree==maxPreNode)
            {
                node.parent.leftNode=maxPreNode;
                maxPreNode.rightNode=node.rightNode;
            }else
            {
                node.parent.leftNode=maxPreNode;
                maxPreNode.rightNode=node.rightNode;
                leftTree.rightNode=maxPreNode.leftNode;
                maxPreNode.leftNode=node.leftNode;
            }
        }
        //删除的节点是父节点的右子树根节点
        else if(node.parent.rightNode.data==node.data)
        {
            if(leftTree==maxPreNode)
            {
                node.parent.rightNode=maxPreNode;
                maxPreNode.rightNode=node.rightNode;
            }else
            {
                node.parent.rightNode=maxPreNode;
                maxPreNode.rightNode=node.rightNode;
                leftTree.rightNode=maxPreNode.leftNode;
                maxPreNode.leftNode=node.leftNode;
            }
        }
        //删除的节点是根节点
        else
        {
            if(leftTree==maxPreNode)
            {
                maxPreNode.rightNode=node.rightNode;
                node.leftNode=nil;
                node.rightNode=nil;
            }else
            {
                maxPreNode.rightNode=node.rightNode;
                leftTree.rightNode=maxPreNode.leftNode;
                maxPreNode.leftNode=node.leftNode;
                node.leftNode=nil;
                node.rightNode=nil;
            }
        }
        
    }
} 

有点绕，有点绕，掌握思路更重要!
其实还没有优化，因为如果是一个[1,2,3,4,5,6,7,8]这样的数据序列构建成二叉查找树，那么就会变成一颗斜数，全部都在右分支，那么查找效率和线性表没有区别了，所以需要调整为二叉平衡树才能提升查找效率。

4.二叉平衡树，红黑树

• 基本概念：
  平衡二叉树，又称AVL树，它是一种特殊的二叉排序树。AVL树或者是一棵空树，或者是具有以下性质的二叉树：
  a.左子树和右子树都是平衡二叉树；
  b.左子树和右子树的深度（高度）之差的绝对值不超过1。
  当插入数据的时候，不满足平衡二叉树时，进行调整，为了更高效的查找。

• 推演过程：
  引入平衡因子BF的概念，每个节点的平衡因子是它的左子树的深度-右子树的深度，加入新的节点后，如果平衡因子>1或者<-1的情况下，需要进行二叉平衡树的调整。
  调整的方式，就是对节点进行适当的旋转。
  前人摘树后人乘凉，根据所有可能出现的情况，一共分为四种：
  左旋转；右旋转；左右旋转；右左旋转。
  eg：左旋转，右旋转
  

  1.png
  插入节点1，此时节点5的BF=2，那么对节点5进行右旋转。

//当前节点右旋转
-(TreeNode*)rightRotate:(TreeNode*)tree
{
    TreeNode * tl=tree.leftNode;
    //左孩子的右子树赋值给根节点的左子树
    tree.leftNode=tl.rightNode;
    //左孩子的右节点变成当前节点
    tl.rightNode=tree;
    //父节点改变指向为左节点
    if(tree.data==tree.parent.leftNode.data)
    {
        tree.parent.leftNode=tl;
    }else
    {
        tree.parent.rightNode=tl;
    }
    tl.parent=tree.parent;
    //调整BF
    tree.BF=0;
    tl.BF-=1;
    //返回左子树为最新的当前节点
    return tl;
}

调整完成后：

2.png

同理，插入2的时候进行平衡二叉树调整：

3.png
4.png

左旋转同右旋转道理相同，方向相反而已：

//根节点左旋转
-(TreeNode*)leftRotate:(TreeNode*)tree
{
    TreeNode * tr=tree.rightNode;
    tree.rightNode=tr.leftNode;
    tr.leftNode=tree;
    if(tree.data==tree.parent.leftNode.data)
    {
        tree.parent.leftNode=tr;
    }else
    {
        tree.parent.rightNode=tr;
    }
    tr.parent=tree.parent;
    //调整BF
    tree.BF=0;
    tr.BF+=1;
    return tr;
}

eg：左右旋转，右左旋转
当旋转节点BF和需要旋转方向的子节点符号不同时，需要先进行子节点的相反旋转，然后再进行该节点的旋转。

5.png
节点5的BF=2，需要右旋转，但是左孩子2的BF=-1，需要先让2进行左旋转，再让5进行右旋转。
左旋转：
6.png
右旋转：
7.png

//左子树左旋转根节点右旋转-左右旋转
-(TreeNode*)leftRightRotate:(TreeNode*)tree
{
    TreeNode * tl=tree.leftNode;
    [self leftRotate:tl];
    return [self rightRotate:tree];
}

右左旋转同左右旋转道理相同，方向相反而已：

//右子树右旋转根节点左旋转-右左旋转
-(TreeNode*)rightLeftRotate:(TreeNode*)tree
{
    TreeNode * tr=tree.rightNode;
    [self rightRotate:tr];
    return [self leftRotate:tree];
}

• 优化的平衡二叉树插入算法：

/*二叉平衡树插入*/
-(TreeNode*)balancetree_insert:(TreeNode*)tree andKey:(int)key
{
    //构建插入节点
    if(tree==nil)
    {
        TreeNode * node=[[TreeNode alloc]initWithData:key andLeft:nil andRight:nil];
        node.BF=0;
        return node;
    }else if(tree.data<key)
    {
        //递归查找进行合适点的数据的插入
        TreeNode * tempNode=[self balancetree_insert:tree.rightNode andKey:key];
        tree.rightNode=tempNode;
        tempNode.parent=tree;
        //如果新插入的节点没有经过旋转调整，则不需要再对BF进行调整了
        if(tree==tempNode)
            tree.BF-=1;
        //进行旋转调整
        if(tree.BF>1)
        {
            if(tree.rightNode.BF<0)
            {
                tree=[self rightLeftRotate:tree];
            }else
            {
                tree=[self leftRotate:tree];
            }
        }else if(tree.BF<-1)
        {
            if(tree.leftNode.BF>0)
            {
                tree=[self leftRightRotate:tree];
            }else
            {
                tree=[self rightRotate:tree];
            }
        }
        return tree;
    }else
    {
        TreeNode * tempNode=[self balancetree_insert:tree.leftNode andKey:key];
        tree.leftNode=tempNode;
        tempNode.parent=tree;
        if(tree==tempNode)
            tree.BF+=1;
        if(tree.BF>1)
        {
            if(tree.leftNode.BF<0)
            {
                tree=[self leftRightRotate:tree];
            }else
            {
                tree=[self rightRotate:tree];
            }
        }else if(tree.BF<-1)
        {
            if(tree.leftNode.BF>0)
            {
                tree=[self rightLeftRotate:tree];
            }else
            {
                tree=[self leftRotate:tree];
            }
        }
        return tree;
    }
}

测试一下：

        TreeNode * tree=[[TreeNode alloc]initWithData:50 andLeft:nil andRight:nil];
        tree.BF=0;
        int arr[10]={30,88,75,74,21,42,57,12,99,66};
        printf("插入前:");
        [self traverseTree:tree];
        for(int i=0;i<10;i++)
        {
            [self balancetree_insert:tree andKey:arr[i]];
        }
        printf("插入后:");
        [self traverseTree:tree];

我们发现，平衡二叉树进行查找的时候效率很高，但是进行插入和删除的时候，需要进行平衡因子的判断以及旋转，这样会降低一定的效率，红黑树就是效率更高进行插入和删除的一颗弱平衡二叉树。
[http://www.360doc.com/content/18/0904/19/25944647_783893127.shtml]

5.多路查找树(B树)，B+树

2-3树

• 是一颗特殊的多路查找树，其中每个节点都具有2个孩子(节点)或者3个孩子(节点)；
  1个节点包含1个元素和2个孩子或者0个孩子；
  2个节点包含2个元素(1小1大)和3个孩子或者0个孩子，第一个孩子小于小值，第二个孩子的值介于大小值之间，第三个孩子大于大值。
  eg：

  
  屏幕快照 2019-05-25 下午5.21.06.png

B树

• B树是一种平衡的多路查找树，2-3树就是B树的特例，其中节点的最大孩子数目称为B树的阶，2-3树就是3阶B树。
  一颗m阶的B树满足如下属性：
  a.每一个非根的分支节点都有k-1个元素和k个孩子，其中m/2<=k<=m。
  b.其中一个孩子的数值介于父节点对应两个元素值中间。
  eg：
  n个关键字m阶的B数，最小的情况下，每个节点有m/2-1个元素和m/2个孩子，那么
  (m/2-1)+(m/2-1)2次方+(m/2-1)3次方+.....(m/2-1)k次方=n，比较k次需要log(m/2)n次；
  最大的情况下，每个节点有m-1个元素和m个孩子，那么
  (m-1)+(m-1)2次方+(m-1)3次方+.....(m-1)k次方=n，比较k次需要log(m)n次；

• 对于海量数据查询的情况下，比平衡二叉树能存储更多的数据，如果数据无法在内存中存储，存储到外存中，则B树的结构更合理。

  
  屏幕快照 2019-05-25 下午5.53.14.png
  

  粉色记录该节点元素个数。

• 不方便的是，如果我们要进行顺序查找，那么中序遍历，但是如果每个节点都不在同一个硬盘空间，那么根节点就会递归好多次，效率降低，所以此时B+树就诞生了。

B+树

• 是应文件系统所需而出的一种B树的变形树，根节点中的元素分布在子树中再出现一个，这些子树中的就是关键字。
  区别于B树的地方是：
  a.有n颗子树的节点中包含n个关键字
  b.所有的叶子节点包含全部关键字信息以及指向包含这些关键字记录的指针，叶子节点本身按照关键字大小的顺序链接。

  
  屏幕快照 2019-05-25 下午5.53.22.png
  

  黄色记录父节点关键字。

• 特点和区别
  B+树相比B树，如果随机查找，那么都是从根节点出发，同基本二叉查找树方式相同。
  但是如果总最小关键字顺序查找，或者找一个区间，我们就可以使用B+树进行根节点查找，找到关键字后，在叶子节点进行顺序查找。

6.散列表(哈希表)

散列表

• 准备
  顺序表查找其实是找到对应索引位置然后根据存储方式，找到对应元素的物理地址，那么如果想根据查找出来的值直接找到对应地址信息，就引入了散列表的概念。
• 概念
  散列技术是记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。
  f称为散列函数，又称为哈希(Hash)函数，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或者哈希表。
• 特点
  散列技术即使一种存储方法，也是一种查找方法；
  散列技术最适合的求解问题是查找与给定值相等的记录，不适合范围查找和模糊查找；

散列函数

• 直接定址法
  取关键字的某个线性函数值为散列地址
  eg：key=1982 addr=2 key=1984 addr=4 addr=key-1980
  这种方式不会产生冲突，但是适合查找表较小且连续的情况，不常用。
• 数字分析法
  抽取部分数据进行位移旋转等操作作为散列地址
  eg:key=18600910351 arr=1035(取后四位并左移1位)
  适合处理关键字位数比较大的数据
• 平方取中法
  关键字平方再抽取中间部分数据作为散列地址
  eg:key=1234，平方就是1522756 ，中间3位就是227
  适合处理位数不大的数据
• 折叠法
  从左到右平分数据然后相加
  eg:key=9876543210 ,三位一分，987+654+321+0=1962作为地址
  适合处理位数大的数据
• 除留余数法
  f(key)=key mod p(p<=m) m是数据个数

可以看出来，基本上不管用什么样的方式都会产生冲突，也就是key1不等于key2，但是f(key1)等于f(key2)的情况。接下来我们来考虑冲突解决办法。

散列冲突解决

• 开放定址法
  f(key)=(f(key)+di) mod m (di=1,2,3,...m-1)
  比如{12,24,30} 12%3=0 存储在0位置，24%3=0 0位置已经存储12了，那么1%3=1存储到1位置。
  优化di，在冲突周围找更合适的位置插入数据
  f(key)=(f(key)+di) mod m (di=1平方,-1平方,2平方-2平方,q平方,-q平方)
• 再散列函数法
  通过不断修改散列函数，相信把全部散列函数都用上，总有一种不冲突的吧。
• 链地址法
  冲突就冲突，把冲突的数据用链表存起来，查找到同一个地址多个数据，再从链表中查找呗。