SplayTree Struct Reference

Detailed Description

Self-adjusting tree of caller-owned nodes, with unique keys.

Searches, including unsuccessful searches, may change the root and links. The tree does not allocate or free nodes or keys.

#include <SplayTree.h>

Public Member Functions
	SplayTree ()
	Leave storage uninitialized; call SplayTree_constructor before use. More...
	SplayTree (SplayTree_Compare compare)
	Initialize an empty tree. More...
int	insert (SplayTreeNode *n)
	Insert a node without allocating memory. More...
SplayTreeNode *	find (SplayTreeKey key)
	Find a node and adjust the tree. More...
int	remove (SplayTreeNode *n)
	Unlink a node without freeing it. More...
SplayTreeNode *	getRoot ()

Constructor & Destructor Documentation

SplayTree() [1/2]

SplayTree::SplayTree

(

)

Leave storage uninitialized; call SplayTree_constructor before use.

SplayTree() [2/2]

SplayTree::SplayTree

(

SplayTree_Compare

compare

)

Initialize an empty tree.

Parameters

[in]

compare

Required comparison callback retained by the tree.

Member Function Documentation

find()

SplayTreeNode * SplayTree::find

(

SplayTreeKey

key

)

Find a node and adjust the tree.

Parameters

[in]

key

Search key interpreted by the comparison callback.

Returns

Borrowed matching node, or NULL if no match exists.

getRoot()

SplayTreeNode * SplayTree::getRoot

(

)

Returns

Borrowed current root, or NULL for an empty tree.

insert()

int SplayTree::insert

(

SplayTreeNode *

n

)

Insert a node without allocating memory.

Parameters

[in,out]

n

Initialized, unlinked node.

Returns

Zero on insertion, -1 if the key already exists.

remove()

int SplayTree::remove

(

SplayTreeNode *

n

)

Unlink a node without freeing it.

Parameters

[in,out]

n

Node to remove, identified by both key and pointer.

Returns

Zero on removal, -1 if this node is not in the tree.