算法2

2019-05-20  本文已影响0人  宙斯YY

一.计算两个点的最小路径(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;
        }
    }
    
}

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

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

3.二叉排序树
@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];
    }
}

/*二叉查找树插入*/
-(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];

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

@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.二叉平衡树，红黑树

//当前节点右旋转
-(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树

B树

B+树

6.散列表(哈希表)

散列表

散列函数

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

散列冲突解决

上一篇下一篇

猜你喜欢

热点阅读