red_black_tree.h File Reference

#include "misc.h"
#include "stack.h"

Include dependency graph for red_black_tree.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	rb_red_blk_node
struct	rb_red_blk_tree

Typedefs
typedef struct rb_red_blk_node	rb_red_blk_node
typedef struct rb_red_blk_tree	rb_red_blk_tree

Functions
rb_red_blk_tree *	RBTreeCreate (int(*CompFunc)(const void *, const void *), void(*DestFunc)(void *), void(*InfoDestFunc)(void *), void(*PrintFunc)(const void *), void(*PrintInfo)(void *))
rb_red_blk_node *	RBTreeInsert (rb_red_blk_tree *, void *key, void *info)
void	RBTreePrint (rb_red_blk_tree *)
void	RBDelete (rb_red_blk_tree *, rb_red_blk_node *)
void	RBTreeDestroy (rb_red_blk_tree *)
rb_red_blk_node *	TreePredecessor (rb_red_blk_tree *, rb_red_blk_node *)
rb_red_blk_node *	TreeSuccessor (rb_red_blk_tree *, rb_red_blk_node *)
rb_red_blk_node *	RBExactQuery (rb_red_blk_tree *, void *)
stk_stack *	RBEnumerate (rb_red_blk_tree *tree, void *low, void *high)
void	NullFunction (void *)

Typedef Documentation

typedef struct rb_red_blk_node rb_red_blk_node

typedef struct rb_red_blk_tree rb_red_blk_tree

Function Documentation

void NullFunction

(

void *

)

Definition at line 72 of file misc.c.

void RBDelete	(	rb_red_blk_tree *	,
		rb_red_blk_node *
	)

Definition at line 601 of file red_black_tree.c.

References Assert(), rb_red_blk_tree::DestroyInfo, rb_red_blk_tree::DestroyKey, if(), rb_red_blk_node::info, rb_red_blk_node::key, rb_red_blk_node::left, rb_red_blk_tree::nil, rb_red_blk_node::parent, RBDeleteFixUp(), rb_red_blk_node::red, rb_red_blk_node::right, rb_red_blk_tree::root, and TreeSuccessor().

Referenced by main().

stk_stack* RBEnumerate	(	rb_red_blk_tree *	tree,
		void *	low,
		void *	high
	)

Definition at line 664 of file red_black_tree.c.

References rb_red_blk_tree::Compare, rb_red_blk_node::key, rb_red_blk_node::left, rb_red_blk_tree::nil, NULL, rb_jbuf, rb_red_blk_node::right, rb_red_blk_tree::root, StackCreate(), StackPush(), and TreePredecessor().

Referenced by main().

rb_red_blk_node* RBExactQuery	(	rb_red_blk_tree *	,
		void *
	)

Definition at line 487 of file red_black_tree.c.

References rb_red_blk_tree::Compare, rb_red_blk_node::key, rb_red_blk_node::left, rb_red_blk_tree::nil, rb_red_blk_node::right, and rb_red_blk_tree::root.

Referenced by main().

rb_red_blk_tree* RBTreeCreate	(	int(*)(const void *, const void *)	CompFunc,
		void(*)(void *)	DestFunc,
		void(*)(void *)	InfoDestFunc,
		void(*)(const void *)	PrintFunc,
		void(*)(void *)	PrintInfo
	)

Definition at line 33 of file red_black_tree.c.

References rb_red_blk_tree::Compare, rb_red_blk_tree::DestroyInfo, rb_red_blk_tree::DestroyKey, rb_red_blk_node::key, rb_red_blk_node::left, rb_red_blk_tree::nil, NULL, rb_red_blk_node::parent, rb_red_blk_tree::PrintInfo, rb_red_blk_tree::PrintKey, rb_jbuf, rb_red_blk_node::red, rb_red_blk_node::right, rb_red_blk_tree::root, and SafeMalloc().

Referenced by main().

void RBTreeDestroy

(

rb_red_blk_tree *

)

Definition at line 446 of file red_black_tree.c.

References rb_red_blk_node::left, rb_red_blk_tree::nil, rb_red_blk_tree::root, and TreeDestHelper().

Referenced by main().

rb_red_blk_node* RBTreeInsert	(	rb_red_blk_tree *	,
		void *	key,
		void *	info
	)

Definition at line 242 of file red_black_tree.c.

References Assert(), rb_red_blk_node::info, rb_red_blk_node::key, rb_red_blk_node::left, LeftRotate(), rb_red_blk_tree::nil, NULL, rb_red_blk_node::parent, rb_jbuf, rb_red_blk_node::red, rb_red_blk_node::right, RightRotate(), rb_red_blk_tree::root, SafeMalloc(), and TreeInsertHelp().

Referenced by main().

void RBTreePrint

(

rb_red_blk_tree *

)

Definition at line 468 of file red_black_tree.c.

References InorderTreePrint(), rb_red_blk_node::left, and rb_red_blk_tree::root.

Referenced by main().

rb_red_blk_node* TreePredecessor	(	rb_red_blk_tree *	,
		rb_red_blk_node *
	)

Definition at line 349 of file red_black_tree.c.

References rb_red_blk_node::left, rb_red_blk_tree::nil, rb_red_blk_node::parent, rb_red_blk_node::right, and rb_red_blk_tree::root.

Referenced by main(), and RBEnumerate().

rb_red_blk_node* TreeSuccessor	(	rb_red_blk_tree *	,
		rb_red_blk_node *
	)

Definition at line 314 of file red_black_tree.c.

References rb_red_blk_node::left, rb_red_blk_tree::nil, rb_red_blk_node::parent, rb_red_blk_node::right, and rb_red_blk_tree::root.

Referenced by main(), and RBDelete().