레드블랙트리

RedBlackTree.h

#ifndef REDBLACKTREE_H_ #define REDBLACKTREE_H_ #include <stdio.h> #include <stdlib.h> typedef int ElementType; typedef struct tagRBTNode { struct tagRBTNode* Parent; struct tagRBTNode* Left; struct tagRBTNode* Right; enum { RED, BLACK } Color; ElementType Data; }RBTNode; void RBT_DestroyTree(RBTNode* Tree); RBTNode* RBT_CreateNode(ElementType NewData); void RBT_DestroyNode(RBTNode* Node); RBTNode* RBT_SearchNode(RBTNode* Tree, ElementType Target); RBTNode* RBT_SearchMinNode(RBTNode* Tree); void RBT_InsertNode(RBTNode** Tree, RBTNode* NewNode); void RBT_InsertNodeHelper(RBTNode** Tree, RBTNode* NewNode); RBTNode* RBT_RemoveNode(RBTNode** Root, ElementType Data); void RBT_RebuildAfterInsert(RBTNode** Root, RBTNode* NewNode); void RBT_RebuildAfterRemove(RBTNode** Root, RBTNode* Successor); void RBT_PrintTree(RBTNode* Node, int Depth, int BlackCount); void RBT_RotateLeft(RBTNode** Root, RBTNode* Parent); void RBT_RotateRight(RBTNode** Root, RBTNode* Parent); #endif </stdlib.h></stdio.h>

RedBlackTree.c

#include "RedBlackTree.h" extern RBTNode* Nil; void RBT_DestroyTree(RBTNode* Tree) { if(Tree->Right != Nil) RBT_DestroyTree(Tree->Right); if(Tree->Left != Nil) RBT_DestroyTree(Tree->Left); Tree->Left = Nil; Tree->Right = Nil; RBT_DestroyNode(Tree); } RBTNode* RBT_CreateNode(ElementType NewData) { RBTNode* NewNode = (RBTNode*)malloc(sizeof(RBTNode)); NewNode->Parent = NULL; NewNode->Left = NULL; NewNode->Right = NULL; NewNode->Data = NewData; NewNode->Color = BLACK; return NewNode; } void RBT_DestroyNode(RBTNode* Node) { free(Node); } RBTNode* RBT_SearchNode(RBTNode* Tree, ElementType Target) { if(Tree == Nil) return NULL; if(Tree->Data > Target) return RBT_SearchNode(Tree->Left, Target); else if(Tree->Data