为啥大家的面试段子都是手写红黑树，而不是手写 AVL 树或堆树一类的

[raysonx]

紅黑樹插入和刪除對要處理的各種情況相對 AVL 樹多得多，我覺得大多數人如果不是天天折騰這個，徒手擼一個紅黑樹還是很困難的（比如我）。

[raysonx]

紅黑樹原理不複雜，但是要處理的各種細節多得要死要死。

[simpleapples]

看成面试段子手...

[lantianziyun]

面试杀手锏，完全不会写红黑树的飘过。

[misaka19000]

红黑树规则比较多，不好好理顺的话会吐血的
话说这东西我都要背下来才能手写，你们一般是怎么搞才能不靠死记硬背而把各种情况都搞定？

[hitmanx]

红黑树一般存在于段子里和吹牛里，我是不太相信什么公司会考手写红黑树之类的，哪怕是 google 。

[enenaaa]

@hitmanx google 那段子不是面试者自己爆出来的吗。 老实说如果不是事先准备，能当场正确写出红黑树平衡算法的 google 员工，我想也不多。

[dtfm]

@hitmanx 我在网上看见过百度某年笔试题中似乎有过，但不清楚这是真来自百度笔试题还是网友瞎编的，但确实我也不认为大多数程序员能笔试手写出能跑的红黑树，写个二分查找意思意思就行了。

[hitmanx]

@enenaaa 我看过有人（好像是老外）写的关于应聘 google 的文章。印象比较深的就是讲其中一个优秀的应届生面试 google 失败，他自觉得算法准备得很好，比如准备了红黑树的几种旋转。但是被作者批了，大概意思是除了前几天刚学过红黑树的在校生，不会有人能清晰地记得红黑树的所有旋转方法，包括 google 自己的员工。而且作为一道面试题，这也不是很合适，因为不是在 20-30 分钟内就能凭借自己能力推导出来的。拿这个筛选，最后考察的不是能力，而是有没有“准备过”，这和面试筛选的初衷有点背道而驰。所以我觉得即使要考核，更可能的并不是直接上来就问红黑树，而是一道包装过的，表面上看上去根本不像红黑树的红黑树题。

[fatedier]

@hitmanx 说的很对呀，我觉得问一下红黑树和 AVL 树各自特点就好了，其实就是看一下对方的学习态度。

[peneazy]

@raysonx 算法愉悦身心

[catror]

面试手写过最复杂的是堆排序

[9hills]

因为要挑一个面试时大部分人写不出来(比如我)却都知道很基本的原理的

用来衬托面试者的眼高手低，形成戏剧性的落差，别的东西没有这个效果。

[msg7086]

面试题应该要弱化准备过程，而强化思考过程。

[xiamx]

跟面试官的经历有关，有些学校只讲红黑树， 2-3 树，不讲其他的

[q397064399]

这有什么难的
Map map = new TreeMap();
手动斜眼，已经写完了

[linux40]

我也觉得堆比红黑树难。。。

[aheadlead]

@hitmanx 南京 Wind

[lsmgeb89]

都是段子而已，面红黑树有什么意义？

真的要写的话，也是对着论文抄算法，没有意义。

[q397064399]

@lsmgeb89 应该面一下 多线程红黑树 如何加锁 解锁
提升容器吞吐能力

[farseeraliens]

@q397064399 多线程不适合用树吧……

[farseeraliens]

@linux40 c++stl 有现成的，并不难

[q397064399]

@farseeraliens
你考虑下，红黑树的插入 是可以加锁的，
插入时 只要当前节点的黑父是锁住的，就可以保证整体有序
读的话，就肯定会出现丢失的情况，

[goubenger]

真不是段子，不要小看小公司的面试，手写红黑树手写哈希表我都遇到过！

[linux40]

@farseeraliens 别说自带的那个残废。

[linux40]

@farseeraliens 顺便说夸张点，自带的那个我闭着眼睛都能写出来。

[imbahom]

通常，有面试官问我红黑数这种问题。
我一般扭头就走。
不是因为，这个职位用不到还问这个。
而是因为。
我 tmd 真的不会

[farseeraliens]

@linux40 能说一下 stl 的堆有什么问题吗？

[linux40]

@farseeraliens merge decrease_key