# 数据结构-红黑树

**Repository Path**: finalize/red-black-tree

## Basic Information

- **Project Name**: 数据结构-红黑树
- **Description**: 数据结构系列-红黑树的C语言实现,使用了分离指针域和数据域的处理,可以扩展为任何类型的红黑树
- **Primary Language**: C
- **License**: GPL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-10-16
- **Last Updated**: 2022-05-23

## Categories & Tags

**Categories**: Uncategorized

**Tags**: 数据结构, 红黑树

## README

# 1. 红黑树

此项目是一个C语言完成的红黑树，包括了[红黑树实现](./RB-Tree/)，[红黑树测试案例](./RB-Tree/testCases/)，[内存管理组件](./MemMana)，以及[测试框架](./TestFrame)组件

项目使用Makefile组织起来，在顶层目录，有两个构建目标，分别是`all`和`test`，前者为正常编译，程序入口点在[main.c](./main.c)，后者为测试程序，入口点在[TestFrame/frameEntry.cpp](./TestFrame/frameEntry.cpp)

另外的目标是`run`和`trun`，这两个目标依赖于上述两个构建目标，只不过是编译+运行

伪目标`clean`，用于清理编译过程产生的中间文件

- [1. 红黑树](#1-红黑树)
  - [1.1. 红黑树实现](#11-红黑树实现)
  - [1.2. 红黑树测试案例](#12-红黑树测试案例)
  - [1.3. 测试框架](#13-测试框架)

## 1.1. 红黑树实现

所有红黑树的代码位于[RB-Tree](./RB-Tree)文件夹下，此实现代码借鉴了部分面向对象的设计，将指针域与数据域分离处理，其中的[base](./RB-Tree/base/)目录下的代码均为处理指针域的代码，而[implement](./RB-Tree/implement/)文件夹下的代码需要“继承”[base](./RB-Tree/base/)目录内的结构体，然后添加自己的数据域，我称之为“实现代码”，所有的增删查改代码均可调用[base](./RB-Tree/base/)内的代码实现，使用者只需维护好自己数据域的比较和内存空间使用即可，各节点之间的指针关系和红黑颜色无需考虑。

提供了实现代码的框架，位于[RB-Tree/RB-Tree-Imp.h](./RB-Tree/RB-Tree-Imp.h)，对于基本数据类型而言，可直接使用`RBT_IMP_REF`和`RBT_IMP_DEF`两个宏定义直接产生对应的实现代码，前者在头文件中使用，产生函数声明，后者在源文件中使用，产生函数定义，并且所有的实现代码均为weak声明，也就是说，如果你对默认函数都处理方式不满意，那么你可以自己写一个同名的函数，此函数会自动替换框架内的函数。

## 1.2. 红黑树测试案例

测试案例为了方便，使用C++进行编写，并且只有文件名符合`tc_*.cpp`格式的文件才会被编译。

目前项目内自带了两个测试案例，分别是[tc_iv](./RB-Tree/testCases/tc_iv.cpp)和[tc_sameKey](./RB-Tree/testCases/tc_sameKey.cpp)，前者进行的是增删查改的测试，后者则是专项测试红黑树处理相同key值是否正确。

两个测试案例依赖于项目自带的内存管理模块，主要用于检查是否存在内存泄露

## 1.3. 测试框架

本项目内实现了一个简单的测试框架，可自动运行测试案例，统计并打印测试结果，并捕获任何测试案例中抛出的异常加以处理，测试案例则需要使用`ExportTestCase`宏，将某个可执行的函数导出为测试案例，支持设置测试案例的优先级以便于控制测试案例的运行顺序，导出的函数会被测试框架回调。