V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
twogoods
V2EX  ›  程序员

你们现在还能写红黑树, b 树的各种操作吗?

  •  
  •   twogoods · 2016-09-25 17:24:49 +08:00 · 10847 次点击
    这是一个创建于 1575 天前的主题,其中的信息可能已经有所发展或是发生改变。
    学生党,在看算法导论,感觉有点晦涩难懂,是不是我太笨了⊙︿⊙,有没有好的教程
    60 条回复    2016-09-27 13:11:44 +08:00
    anexplore
        1
    anexplore   2016-09-25 17:28:50 +08:00
    已经忘记了,也就知道操作的时间复杂度了
    raysonx
        2
    raysonx   2016-09-25 17:34:35 +08:00 via iPad
    b 树需要画画图,红黑树太复杂,得对着文档才能写,
    Tink
        3
    Tink   2016-09-25 17:37:58 +08:00 via iPhone   ❤️ 1
    cant
    20015jjw
        4
    20015jjw   2016-09-25 17:40:56 +08:00   ❤️ 2
    ucsf 的可视化 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html 可能可以帮助理解吧 反正我的数据结构用了一点这个
    messyidea
        5
    messyidea   2016-09-25 17:41:43 +08:00
    可能中文翻译不怎么样,可以看看英文的原版,或者看看别人的博客,比如下面两篇
    http://blog.csdn.net/spch2008/article/details/9338919
    http://blog.csdn.net/spch2008/article/details/9338923
    kingoldlucky
        6
    kingoldlucky   2016-09-25 17:49:53 +08:00
    从来就不能完整写过,不是现在
    livc
        7
    livc   2016-09-25 17:51:53 +08:00
    从未写过
    yidinghe
        8
    yidinghe   2016-09-25 17:52:43 +08:00 via Android
    虽然是计算机专业毕业,但从来就没写过,也不会写。
    Nexvar
        9
    Nexvar   2016-09-25 17:53:44 +08:00
    已经失去这个能力
    Marfal
        10
    Marfal   2016-09-25 17:54:07 +08:00
    @messyidea 醉了,你认为英文版算法导论比中文更易读?

    入门别用算法导论啊。
    Nexvar
        11
    Nexvar   2016-09-25 17:54:10 +08:00
    但要捡起来,也还是比没学过简单
    moyang
        12
    moyang   2016-09-25 17:54:39 +08:00 via Android
    上学的时候实现过一次红黑树,心理阴影
    messyidea
        13
    messyidea   2016-09-25 18:00:10 +08:00
    @Marfal 所以说可能 = =,我有本第二版的中文,记得当时红黑树删除那块实在看不下去了,那些博客容易理解多了
    mko0okmko0
        14
    mko0okmko0   2016-09-25 18:19:31 +08:00
    会用不会写.记住时间复杂度跟用法就好.
    学校考写出红黑没用.除非要先搞学术.
    出社会第一件事情就是活用现有演算法.
    有现成的东西一堆.重点要会用
    Mistwave
        15
    Mistwave   2016-09-25 18:26:37 +08:00 via iPhone
    算导适合算法分析 学算法推荐 sedgewick 的算法第四版 不过这本书覆盖面有限 dp 啥的没讲 看完可以看 数据结构与算法分析: c 语言描述
    Mistwave
        16
    Mistwave   2016-09-25 18:28:21 +08:00 via iPhone
    拿红黑树为例 算法第四版是从 2-3 树的角度切入的 十分好懂
    而且还有配套视频( coursera ) 十分推荐
    TaoQAQ
        17
    TaoQAQ   2016-09-25 18:29:01 +08:00 via Android
    诶,面试怎么办,校招怎么办
    h4x3rotab
        18
    h4x3rotab   2016-09-25 18:32:29 +08:00 via iPhone
    那么多平衡树,知道各个的原理,能写出一两个就好了
    yangff
        19
    yangff   2016-09-25 18:34:25 +08:00
    复盘一下思想,推一推就好了嘛……
    q397064399
        20
    q397064399   2016-09-25 18:47:33 +08:00   ❤️ 3
    重要的是思想以及特性,还有运用场景,一个算法的完整实现,没有 github 面试官 你特么让我怎么写?



    例如
    红黑树 多线程,插入 删除 等操作,都要加锁,这是其数据结构的特性所致,不加锁就会产生竞争
    但是涉及到数据的有序性,你又不能不使用红黑树,我目前没有看到一个数据结构能实现
    快速插入 删除等操作 还能保持有序性,红黑树在这种场景是首选

    HashMap 多线程的话,只要正在读写的那根链表加锁就可以了,其它的链表是完全可以释放给其它线程使用的,
    如果有多线程性能需求的话, HashMap 是首选,另外还要学会针对不同的数据选择 Hash 算法保持桶的板最好平衡

    针对超长且部分有序顺序表, 快速排序并不比归并排序快,


    其它还有一些例子我就不举了,

    新算法的研究从来都不是工程师的事情

    工程师的能力在于了解算法的特性以及大致实现,并在合适的场景选择合适的算法,而不是把每个算法给背下来,你背了那么多算法,让你手写一个 HashMap QuickSort 就一定比 Java util 中的快?
    q397064399
        21
    q397064399   2016-09-25 18:49:59 +08:00
    我上面还是针对转行程序员这行说的,
    科班的兄弟们还是好好刷 CLRS 把证明习题都刷一遍吧,哈哈
    q397064399
        22
    q397064399   2016-09-25 18:51:46 +08:00
    另外一个红黑树 左旋 右旋,旋来旋去头都晕了,你然我手写,我大致能推导出 插入的算法,并手写出来, 删除就别想了,手写的算法 我目前也就只剩 二分 归并 冒泡了
    ibiger
        23
    ibiger   2016-09-25 19:14:55 +08:00
    好像曾经写出过来一样,这知道和会写还有写对,差的不是天上地下吧
    hxtheone
        24
    hxtheone   2016-09-25 19:38:22 +08:00 via iPhone
    一直都不会写
    scnace
        25
    scnace   2016-09-25 19:40:20 +08:00 via Android   ❤️ 4
    看到回复 我就放心了 看来 V 站还是可以继续混下去的😂
    tvallday
        26
    tvallday   2016-09-25 19:47:06 +08:00 via Android
    我原来排序都记不全的,给人培训几个月 java 排序算法之后我靠倒着我都能写出来。要是我写不出来人家根本听不懂。
    iEverX
        27
    iEverX   2016-09-25 20:28:57 +08:00
    从来都不会
    tscat
        28
    tscat   2016-09-25 20:35:01 +08:00
    不要看算法导论,去刷 acm 吧
    kkzxak47
        29
    kkzxak47   2016-09-25 20:42:13 +08:00 via Android
    看一次忘一次
    wangxn
        30
    wangxn   2016-09-25 21:04:36 +08:00 via Android
    从没写过。
    wudanyang
        31
    wudanyang   2016-09-25 21:09:25 +08:00
    看到你们也忘,我就放心了,我以为我脑子有坑呢
    21grams
        32
    21grams   2016-09-25 21:42:19 +08:00 via Android
    会写又如何,工作里绝对用不上
    ivvei
        33
    ivvei   2016-09-25 21:56:50 +08:00   ❤️ 3
    我前段时间去面试,家常拉完之后,对方上来就问红黑树。我当时直接懵逼了啊。按套路不是应该从冒泡排序开始的吗?
    ldz
        34
    ldz   2016-09-25 23:24:29 +08:00
    这个有点复杂
    面试一般不会为这个
    shimanooo
        35
    shimanooo   2016-09-26 00:36:55 +08:00
    红黑树是 2-3 树(实际是 2-3-4 树,和多线程效率有关)的变种实现, B 树是 2-3 树的推广。

    算法导论这部分讲的不好:先告诉你结论,再给你证明。但你终究知其然不知其所以然,不知道这到底是怎么想出来的。

    这部分内容讲的比较好的是这本书
    hxidkd
        36
    hxidkd   2016-09-26 00:41:42 +08:00 via Android
    红黑树的删除真心不记得了…其他的都还行
    magusf
        37
    magusf   2016-09-26 05:47:22 +08:00
    @20015jjw 纠一下错,这是 USF 而不是 UCSF , UCSF 是医学院 :)
    q397064399
        38
    q397064399   2016-09-26 06:14:54 +08:00
    @ivvei 冒泡烂大街了,讲道理的话 不是应该从二分开始的么?
    q397064399
        39
    q397064399   2016-09-26 06:17:09 +08:00
    @shimanooo 这书有中文版,红黑树主讲插入,删除那部分好像跳过了
    ryd994
        40
    ryd994   2016-09-26 06:34:40 +08:00 via Android
    要描述一下基本原理可以,要实现很难
    讲真,突然要我写个没坑的二分我觉得都要费点力气
    主要是实现中还有很多细节问题要处理
    linux40
        41
    linux40   2016-09-26 08:42:43 +08:00 via Android
    b 树不熟,红黑树可以。
    算法导论上红黑树往后的都不行。。。
    tvallday
        42
    tvallday   2016-09-26 08:50:47 +08:00 via iPhone
    @ivvei 冒泡太简单了,我教过没有编程基础的高一学生,从来没碰过排序的,让他自己想一个排序算法出来他都能写个冒泡。这种问题拿来面试太丢人了。
    zky001
        43
    zky001   2016-09-26 09:22:10 +08:00
    只能大概说出来了,手写的话还要一点时间
    cjyang1128
        44
    cjyang1128   2016-09-26 09:41:47 +08:00
    考试前的我是无敌的。。。
    paw
        45
    paw   2016-09-26 09:58:16 +08:00
    上个项目要用到红黑树,直接 google “ rbtree github ” 复制下来改改接口测试下没 BUG ,直接上了

    要我自己写?? 我选择离职
    hackpro
        46
    hackpro   2016-09-26 10:14:17 +08:00
    @shimanooo 高德纳弟子作品 浅显易懂
    lyragosa
        47
    lyragosa   2016-09-26 10:33:22 +08:00
    非科班选手表示我选择死亡。
    gejigeji
        48
    gejigeji   2016-09-26 10:38:25 +08:00
    我也是看的那本“算法”
    dreamtrail
        49
    dreamtrail   2016-09-26 14:35:24 +08:00
    以前能写,过几年就忘了,要写看看书就行了
    noobcode
        50
    noobcode   2016-09-26 16:52:29 +08:00
    两年多码农,从没写过红黑树。。。
    yanchao7511461
        51
    yanchao7511461   2016-09-26 16:56:39 +08:00
    能写个 jb 。。。。。 现在让我阐述算法都够呛了
    xmwd
        52
    xmwd   2016-09-26 16:59:05 +08:00
    《 STL 源码剖析》搭配维基百科,有图就好理解
    ytmsdy
        53
    ytmsdy   2016-09-26 17:04:18 +08:00
    B 树还有可能徒手写出来
    红黑树就要瓦特了
    huntzhan
        54
    huntzhan   2016-09-26 17:10:58 +08:00
    @ytmsdy 我怎么觉得是 B 树更加难写一些......
    ytmsdy
        55
    ytmsdy   2016-09-26 17:13:17 +08:00
    @huntzhan B 树不用旋转,不用调。红黑树要调整,要旋转。
    Magic347
        56
    Magic347   2016-09-26 17:38:44 +08:00
    类似的问题还可以面向:
    splay tree
    avl tree
    dancing links
    etc.
    pybog
        57
    pybog   2016-09-26 18:21:42 +08:00
    从未写过。。做的东西也没有遇到过。。。码农 3 年了快 疲软。
    shihira
        58
    shihira   2016-09-26 19:24:29 +08:00
    刚学数据结构的时候写过一个 C 语言带运行时泛型的,不过没有在生产环境用过。现在要我写估计要两天琢磨琢磨
    ma125125t
        59
    ma125125t   2016-09-26 19:40:08 +08:00
    @tvallday 来,倒着写一个我看看( doge )
    zacard
        60
    zacard   2016-09-27 13:11:44 +08:00
    刚刚之前看 java8 hashmap 源码里出现红黑树,复习了一把。。。
    关于   ·   帮助文档   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   962 人在线   最高记录 5298   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 21:13 · PVG 05:13 · LAX 13:13 · JFK 16:13
    ♥ Do have faith in what you're doing.