红黑树采用什么数据结构算法?

jjww · 发表于 2003-10-8 20:50:49

thanks very much！

_z_ · 发表于 2003-10-8 21:01:41

不客气，还不知道这个是不是你要的呢

jjww · 发表于 2003-10-8 21:42:37

是的，thx

daemonx · 发表于 2003-10-9 10:44:04

红黑书是平衡二叉树的变种实现，用计算机实现起来比较容易
原则是：
1.红节点不能指向红节点；
2.黑节点指向红节点的路径不计入树高
3.每个节点的子孙若不完整需要用虚拟黑节点补齐
在插入删除的操作中可以通过调整相关节点的红黑属性以达到树的平衡

jamesxuruo · 发表于 2003-10-9 21:24:45

首先在vm_area_struct中倒是用到了avl树(我学数据结构时用的是英文版的),你看一看清华大学出版社的数据结构(黄皮)里关于avl的阐述,不过上面各位我认为没有必要说得如此详细,只要将出处讲出来就可以了,当然你所指的红黑树我没在代码中碰到,数据结构也很久没看,忘光了

不过avl树是很好的设计,清华的那本书会给你满意的答复

daemonx · 发表于 2003-10-10 10:11:36

回楼上
清华的数据结构里面没有讲红黑树

rick_xbx · 发表于 2003-12-4 21:56:23

请问为什么要用红黑树？记得2.4.18的时候还是avl树。

		自动登录	找回密码
密码			注册