rbtree.h File Reference

Red-black tree. More...

#include "st/logger/except.h"
#include "vx/graph.h"
#include <stdint.h>

Include dependency graph for rbtree.h:

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

Go to the source code of this file.

Enumerations
enum	StBstOrder { ST_BST_INORDER = 0 , ST_BST_PREORDER , ST_BST_POSTORDER }
	Nodes order for a binary search tree. More...
enum	StBstChild { ST_BST_LEFT = 0 , ST_BST_RIGHT , ST_BST_N_CHILDREN }
	Indices for children in a binary search tree. More...

Functions
	VX_GRAPH (struct StRbNode, ST_BST_N_CHILDREN, union {intptr_t parcol;int32_t align;})
	This is a macro definition of the struct StRbNode type.
static struct StRbNode *	st_rb_left (struct StRbNode *node)
	Get the left child of the given node.
static struct StRbNode *	st_rb_right (struct StRbNode *node)
	Get the right child of the given node.
struct StRbNode *	st_rb_link (struct StRbNode *node, struct StRbNode *parent)
	Prepare a node for insertion in a red-black tree.
struct StRbNode *	st_rb_insrebal (struct StRbNode *root, struct StRbNode *node)
	Insert a node in a red-black tree and rebalance the tree.
struct StRbNode *	st_rb_parent (struct StRbNode *node)
	Get the parent of the red-black tree node.
struct StRbNode *	st_rb_first (struct StRbNode *node, enum StBstOrder order)
	Get the first node of the red-black tree for the given BST order.
struct StRbNode *	st_rb_next (struct StRbNode *node, enum StBstOrder order)
	Get the next node for the current red-black tree node and the BST order.

Detailed Description

Red-black tree.

Enumeration Type Documentation

StBstChild

enum StBstChild

Indices for children in a binary search tree.

Enumerator
ST_BST_LEFT	left child.
ST_BST_RIGHT	right child.
ST_BST_N_CHILDREN	number of children.

StBstOrder

enum StBstOrder

Nodes order for a binary search tree.

Enumerator
ST_BST_INORDER	in-order.
ST_BST_PREORDER	pre-order.
ST_BST_POSTORDER	post-order.

Function Documentation

st_rb_first()

struct StRbNode * st_rb_first	(	struct StRbNode *	node,
		enum StBstOrder	order
	)

Get the first node of the red-black tree for the given BST order.

Parameters

[in]	node	Any node from the red-black tree.
[in]	order	The order: BST_INORDER, BST_PREORDER or BST_POSTORDER.

Returns

The first node.

st_rb_insrebal()

struct StRbNode * st_rb_insrebal	(	struct StRbNode *	root,
		struct StRbNode *	node
	)

Insert a node in a red-black tree and rebalance the tree.

Parameters

[in,out]	root	The root of the red-black tree.
[in,out]	node	The inserted node.

Returns

The new root.

Note

Prepare node with st_rb_link() before insertion.

See also

st_rb_link().

st_rb_left()

static inline struct StRbNode * st_rb_left ( struct StRbNode *  node )

inlinestatic

Get the left child of the given node.

Parameters

[in]

node

The node.

Returns

The left child.

st_rb_link()

struct StRbNode * st_rb_link	(	struct StRbNode *	node,
		struct StRbNode *	parent
	)

Prepare a node for insertion in a red-black tree.

Parameters

[in,out]	node	The node prepared for insertion.
[in]	parent	The parent node.

This will paint node red and set its parent pointer to parent. This will also ensure that the left and right pointers of node are NULL. After preparing the node for insertion, insert it with st_rb_insrebal().

See also

st_rb_insrebal().

Returns

The prepared node.

st_rb_next()

struct StRbNode * st_rb_next	(	struct StRbNode *	node,
		enum StBstOrder	order
	)

Get the next node for the current red-black tree node and the BST order.

Parameters

[in]	node	The current red-black tree node.
[in]	order	The order: BST_INORDER, BST_PREORDER or BST_POSTORDER.

Returns

The next node.

st_rb_parent()

struct StRbNode * st_rb_parent

(

struct StRbNode *

node

)

Get the parent of the red-black tree node.

Parameters

[in]

node

The red-black tree node.

Returns

The parent.

st_rb_right()

static inline struct StRbNode * st_rb_right ( struct StRbNode *  node )

inlinestatic

Get the right child of the given node.

Parameters

[in]

node

The node.

Returns

The right child.