Libuv 源码分析(7):数据结构—复合类型(红黑树、最小二叉堆)

一、概述

Libuv 用到了一些复合类型的数据结构：队列( Queue )、红黑树( Red-Black tree )、最小二叉堆( Binary min heap )等。其中队列和最小二叉堆是以宏的形式实现的。
红黑树主要用于信号处理( Signal Handle )；最小二叉堆主要用于计时器( Timer )。
树和堆的实现不像队列实现那样有特色，甚至很多 Linux/UNIX 操作系统本身就包含实现，故本文主要提供一些树和堆的参考资料的链接。

参考资料

1、Base

• https://en.wikipedia.org/wiki/Binary_tree

2、Tree

• https://en.wikipedia.org/wiki/Binary_search_tree
• https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
• https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
• macOS: #import <Kernel/libkern/tree.h>
• FreeBSD: tree(3) #include <sys/tree.h>
• https://www.freebsd.org/cgi/man.cgi?query=tree&sektion=3

3、Heap

• https://en.wikipedia.org/wiki/Heap_(data_structure)
• https://en.wikipedia.org/wiki/Binary_heap