红黑树(六)之 参考资料

前面几章对红黑树进行了比较全面的介绍,包括红黑树的理论以及C/C++/Java的实现。这部分将我学习红黑树期间的一些参考资料和代码分享出来,供大家参考。

参考说明

在写红黑树这几篇文章的过程中,参考了许多资料:主要有《算法导论》、《数据结构与算法分析-C语言描述》以及网上的一些文章;此外,还参考了"Linux内核中的红黑树源码"、"JDK中的红黑树源码"、"STL中的红黑树源码"。

1. Linux内核中的红黑树源码

在"红黑树(三)之 Linux内核中红黑树的经典实现"这篇文章中,我已经将Linux内核中的红黑树源码移植出来了,供大家参考。若你想自己亲自研究,可以获取Linux内核源码后再进行查阅。
(01) Linux内核源码下载地址:https://www.kernel.org/
(02) 头文件路径:include/linux/rbtree.h
(03) 实现文件路径:lib/rbtree.c

2. JDK中的红黑树源码

JDK中的红黑树在实现TreeMap和TreeSet时有用到。在我以前写的"Java 集合系列"的"Java 集合系列12之 TreeMap详细介绍(源码解析)和使用示例"中有介绍过。如果你想一探究竟,参考查看JDK源码。

(01) JDK的源码可以通过解压"JDK包中的src.zip"获取。当然,你也可以通过openjdk来查看JDK源码。
(02) TreeMap的路径:java/util/TreeMap.java

3. STL中的红黑树源码

这部分我没有仔细研究。若你感兴趣,可以研究之后,再来分享给大家。

ubuntu下STL中红黑树的源码路径:/usr/include/c++/4.6/ext/pb_ds/detail/rb_tree_map
说明:上面是我自己使用的ubuntu(12.04版本)下STL源码路径,不同的系统可能略有不同。"/usr/include/c++/4.6/"是g++4.6的路径,而"ext/pb_ds/detail/rb_tree_map
"则是红黑树源码路径。

by skywang
Previous     Next