AA-Tree
[Generic Data Structures]

Collaboration diagram for AA-Tree:

An implementation of an AA-Tree -- a balanced binary tree. More...


Files

file  aatree.c
 Cop-out implementation of an AA-tree.
file  aatree.h
 Interface to an AA-tree.

Data Structures

struct  AANode_t
 The node data used to track the structure of an AA-Tree. More...
struct  AATreeRemovalData_t
 Used by AATreeRemove() to store data used to remove items from the tree. More...

Defines

#define AA_ROOT_NODE   (&aaTerminatorNode)
 A pointer to the initial root node; if it is the root node of a tree, then the tree is empty.
#define AATreeIsEmpty(tree)   ((tree) == &aaTerminatorNode)
 Evaluates to true if the given tree is empty.
#define AATreeRemove(tree, key)
 Removes an item from the given tree.

Typedefs

typedef AANode_t AANode
typedef Uint16 AATreeKeyLevelType
 The data type used to identify the items in the AA-Tree.
typedef AATreeRemovalData_t AATreeRemovalData

Functions

AANode_AATreeRemove (AANode *tree, AATreeRemovalData *rd)
 Implements the recursive removal algorithim; removes and deallocates the node with the given key.
AANodeAATreeAdd (AANode **tree, AATreeKeyLevelType key)
 Adds a node to the indicated tree.
void AATreeDestroy (AANode *tree)
 Deallocates all AANodes that comprise a tree.
AANodeAATreeFind (AANode *tree, AATreeKeyLevelType key)
 Finds a node in the tree.

Variables

AANode aaTerminatorNode
 The node used to indicate that a particular branch is empty.

Detailed Description

An implementation of an AA-Tree -- a balanced binary tree.

AA-Trees are simplified Red-Black trees with an easier implementation.

Bug:
The tree is broken. Nodes do not continue to track the same item. If the item contains the key value, like MsgDescr, eventually AATreeFind() will return a node who's key field is correct, but the data item will have a different key value indicating that the node's data has incorrectly changed.
This AA-Tree implementation lacks a data type that represents the tree as a whole. This was done as a way to improve efficiency a little, although it may make using this implementation a little more confusing, so maybe I'll change that in the future. For now, a tree is represented only by a pointer to its root node. New, empty trees should have a pointer to AA_ROOT_NODE as thier root node.

The implementation does not manage memory for any data being tracked by a tree. However, it does dynamically allocate and deallocate the AANode structures that make up the trees.


Define Documentation

#define AA_ROOT_NODE   (&aaTerminatorNode)

A pointer to the initial root node; if it is the root node of a tree, then the tree is empty.

Definition at line 130 of file aatree.h.

Referenced by CancelAllMessages(), and MessageUninit().

#define AATreeIsEmpty ( tree   )     ((tree) == &aaTerminatorNode)

Evaluates to true if the given tree is empty.

Parameters:
tree A pointer to the root node of the tree to check.
Returns:
True if the tree is empty, false if there is something within the tree.
Author:
Jeff Jackowski

Definition at line 139 of file aatree.h.

#define AATreeRemove ( tree,
key   ) 

Value:

if ((tree) != &aaTerminatorNode) { \
    AANode *newRoot;  \
    AATreeRemovalData rd = { NULL, &aaTerminatorNode, key }; \
    if ((newRoot = _AATreeRemove(tree, &rd)) != NULL) tree = newRoot; \
}
Removes an item from the given tree.

This is a macro implementation that has a little code to start the removal operationn to avoid putting that code in a really small function. I just didn't feel like making that function.

Parameters:
tree A pointer to the root node of a tree. This pointer will be altered to point to the new root node.
key The key that identifies the item to remove from the tree. The corresponding node will be deallocated.
Author:
Jeff Jackowski

Definition at line 211 of file aatree.h.

Referenced by Send().


Typedef Documentation

typedef struct AANode_t AANode

Definition at line 73 of file aatree.h.

typedef Uint16 AATreeKeyLevelType

The data type used to identify the items in the AA-Tree.

This must be an integer type. A 16-bit value was selected because it works well for Tank!

Definition at line 71 of file aatree.h.

typedef struct AATreeRemovalData_t AATreeRemovalData

Definition at line 163 of file aatree.h.


Function Documentation

AANode* _AATreeRemove ( AANode tree,
AATreeRemovalData rd 
)

Implements the recursive removal algorithim; removes and deallocates the node with the given key.

For internal use only.

Use the AATreeRemove() macro instead of calling this function directly.

Parameters:
tree A pointer to the next branch of the tree to work with.
rd Removal scope data.
Returns:
The new value for the passed in tree pointer, or NULL if the node sought is not in the tree.
Author:
Jeff Jackowski

Definition at line 67 of file aatree.c.

References aaTerminatorNode, Vector_t::array, copout, Vector_t::items, AATreeRemovalData_t::key, AANode_t::key, and Vector_t::VectorRemove.

AANode* AATreeAdd ( AANode **  tree,
AATreeKeyLevelType  key 
)

Adds a node to the indicated tree.

Parameters:
tree A pointer to the root node of the tree that will be given the new item. This pointer will be changed to the new root node. In case of error, it will remain unchanged.
key The key of the node to add.
Returns:
A pointer to the added node, or NULL if the node could not be added. The node's key field will be filled out. The data / index field will be uninitialized.
Author:
Jeff Jackowski

Definition at line 49 of file aatree.c.

References Vector_t::array, copout, AANode_t::key, Vector_t::VectorAdd(), and Vector_t::VectorInit().

Referenced by AddMessage().

Here is the call graph for this function:

void AATreeDestroy ( AANode tree  ) 

Deallocates all AANodes that comprise a tree.

Warning:
The root node of the tree will not be valid after this function returns.
Parameters:
tree The root node of the tree to deallocate. The tree must not already be empty. The root node will not be valid after this function returns.
Author:
Jeff Jackowski

Definition at line 89 of file aatree.c.

References copout, treeExit(), TRUE, and Vector_t::VectorClear().

Referenced by CancelAllMessages(), and MessageUninit().

Here is the call graph for this function:

AANode* AATreeFind ( AANode tree,
AATreeKeyLevelType  key 
)

Finds a node in the tree.

Parameters:
tree A pointer to the root node of the tree to search.
key The key identifying the node to find.
Returns:
A pointer to the sought after node, or NULL if the node is not in the tree.
Author:
Jeff Jackowski

Definition at line 37 of file aatree.c.

References Vector_t::array, copout, Vector_t::items, and AANode_t::key.

Referenced by HandleAck(), and ServiceMessages().


Variable Documentation

AANode aaTerminatorNode

The node used to indicate that a particular branch is empty.

This is used in place of NULL to simplify the code, and defined only once to avoid having multiple copies.

Note:
This is not defined as a const type becuase the code will still run assignments that change values within the terminator, although only to the value that is already there. It simplifies the code to able to use assignments in this way.

Definition at line 34 of file aatree.c.

Referenced by _AATreeRemove().


Generated on Mon May 28 04:41:41 2007 for Retro Tank Super Attack by  doxygen 1.5.2