7. 数据结构—复合类型(红黑树、最小二叉堆)

声明

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

一、概述 Libuv 用到了一些复合类型的数据结构：队列 (Queue)、红黑树( Red-Black tree )、最小二叉堆( Binary min heap ) 等。

一、概述

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