专栏首页工具类数据结构和算法浅读

数据结构和算法浅读

前言

程序=数据结构+算法 最近看数据结构方面的知识,整合记录下来,部分文章是转载的,链接贴后面

哈希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的则更新值,若无则创建新节点。

位运算

位运算即是在位级别进行操作的技术,合适的位运算能够帮助我们得到更快地运算速度与更小的内存使用。 测试第 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) 链接: 二叉查找树 - 删除节点 详解

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 服务器直接输入字符串代码执行方法测试

    我们在写代码的过程中时常要调试,但线上的服务器打包部署运行很费时,或者需要在线上查看数据,可以直接在服务器上输入需要执行的代码

    深雾
  • 对接常用的工具方法,request转map,转签名字符串等

    深雾
  • bat脚本简化操作

    一些常用的操作可以封装成脚本,将excel文件转json文件,策划更新配置文件后,需要给客户端导表,hhh感觉我又在干运维的活。

    深雾
  • 数据结构简单要点总结(转)

    栈是只能在一端进行插入和删除的线性表。 (别看只是个定义,非常重要,已经道出了运算方法:只能在一端插入和删除。)

    Locker
  • 17张图带你解析红黑树的原理!保证你能看懂!

    由于红黑树本质上就是一棵二叉查找树,所以在了解红黑树之前,咱们先来看下二叉查找树。

    程序员追风
  • 30 张图带你彻底理解红黑树

    本文将通过图文的方式讲解红黑树的知识点,并且不会涉及到任何代码,相信我,在懂得红黑树实现原理前,看代码会一头雾水的,当原理懂了,代码也就按部就班写而已,没任何难...

    智能算法
  • 《大话数据结构》(二)

    1.树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中:(1)有且仅有一个特定的称为根(Root)的结点;(2)当n>1时,其余...

    硬核项目经理
  • 什么是红黑树?

    当在10亿数据中只需要进行10几次比较就能查找到目标时,不禁感叹编程之魅力!人类之伟大呀! —— 学红黑树有感。

    小东啊
  • 「学习笔记」树和二叉树

    由 n(n ≧ 0)个结点组成的有序集合,n = 0 时称为空二叉树;n > 0 的二叉树是由一个根节点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。...

    FoamValue
  • BTree,B-Tree,B+Tree,B*Tree都是什么

           3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;

    阳光岛主

扫码关注云+社区

领取腾讯云代金券