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

手写

avl

段子

树

29 条回复 • 2017-12-26 14:09:20 +08:00

1

raysonx

2016-12-09 16:09:30 +08:00

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

2

raysonx

2016-12-09 16:10:14 +08:00

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

3

simpleapples

2016-12-09 16:19:49 +08:00

看成面试段子手...

4

lantianziyun

2016-12-09 16:24:34 +08:00

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

5

misaka19000

2016-12-09 16:57:32 +08:00 via Android

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

6

hitmanx

2016-12-09 17:18:36 +08:00

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

7

enenaaa

2016-12-09 17:25:08 +08:00

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

8

dtfm

2016-12-09 17:28:03 +08:00

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

9

hitmanx

2016-12-09 18:00:06 +08:00

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

10

fatedier

2016-12-09 18:39:19 +08:00

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

11

peneazy

OP

2016-12-09 19:02:12 +08:00 via Android

@raysonx 算法愉悦身心

12

catror

2016-12-09 19:12:00 +08:00 via Android

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

13

9hills

2016-12-09 23:03:57 +08:00 via iPhone

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

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

14

msg7086

2016-12-10 01:16:12 +08:00

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

15

xiamx

2016-12-10 07:53:06 +08:00 via Android

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

16

q397064399

2016-12-10 07:59:50 +08:00

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

17

linux40

2016-12-10 09:07:00 +08:00 via Android

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

18

aheadlead

2016-12-10 09:33:56 +08:00

@hitmanx 南京 Wind

19

lsmgeb89

2016-12-10 09:45:53 +08:00

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

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

20

q397064399

2016-12-11 07:55:39 +08:00

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

21

farseeraliens

2016-12-11 18:34:54 +08:00 via iPhone

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

22

farseeraliens

2016-12-11 18:35:47 +08:00 via iPhone

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

23

q397064399

2016-12-11 18:57:42 +08:00

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

24

goubenger

2016-12-11 22:42:14 +08:00

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

25

linux40

2016-12-12 09:32:40 +08:00 via Android

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

26

linux40

2016-12-12 09:34:57 +08:00 via Android

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

27

imbahom

2016-12-12 14:24:56 +08:00

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

28

farseeraliens

2017-10-20 13:18:46 +08:00 via iPhone

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

29

linux40

2017-12-26 14:09:20 +08:00 via Android

@farseeraliens merge decrease_key