• Choose a category
• All
• Classic-Fiction

By Root 1478 0

keeping a binary search tree balanced requires that each node store more than just the data placed in the tree, a structure, AvlNode, is defined for each node to contain (see Example 9.4). An AvlNode structure consists of three members: data is the data stored in the node, hidden is a member used to mark a node when it is removed, and factor is the node's balance factor. The implementation presented here also uses identifiers to represent the possible values for balance factors. Example 9.4 equates AVL_LEFT_HEAVY to 1, AVL_BALANCED to 0, and AVL_RGT_HEAVY to -1.

Example 9.4. Header for the Binary Search Tree Abstract Datatype

/*****************************************************************************

* *

* ------------------------------- bistree.h ------------------------------ *

* *

*****************************************************************************/

#ifndef BISTREE_H

#define BISTREE_H

#include "bitree.h"

/*****************************************************************************

* *

* Define balance factors for AVL trees. *

* *

*****************************************************************************/

#define AVL_LFT_HEAVY 1

#define AVL_BALANCED 0

#define AVL_RGT_HEAVY -1

/*****************************************************************************

* *

* Define a structure for nodes in AVL trees. *

* *

*****************************************************************************/

typedef struct AvlNode_ {

void *data;

int hidden;

int factor;

} AvlNode;

/*****************************************************************************

* *

* Implement binary search trees as binary trees. *

* *

*****************************************************************************/

typedef BiTree BisTree;

/*****************************************************************************

* *

* --------------------------- Public Interface --------------------------- *

* *

*****************************************************************************/

void bistree_init(BisTree *tree, int (*compare)(const void *key1, const void

*key2), void (*destroy)(void *data));

void bistree_destroy(BisTree *tree);

int bistree_insert(BisTree *tree, const void *data);

int bistree_remove(BisTree *tree, const void *data);

int bistree_lookup(BisTree *tree, void **data);

#define bistree_size(tree) ((tree)->size)

#endif

bistree_init

The bistree_init operation initializes a binary search tree so that it can be used in other operations (see Example 9.5). Since a binary search tree is a binary tree, we call bitree_init to initialize it. The compare member is set to compare by hand because this member is not used by binary trees and therefore is not set by bitree_init.

The runtime complexity of bistree_init is the same as bitree_init, or O (1).

bistree_destroy

The bistree_destroy operation destroys a binary search tree (see Example 9.5). To do this, we employ the support of two additional functions, destroy_left and destroy_right, which recursively destroy the left and right subtrees beneath a node. These functions work similarly to the bitree_rem_left and bitree_rem_right functions defined previously for binary trees. Separate functions are required for binary search trees so that we can destroy the data referenced by a node's AvlNode structure as well as free the AvlNode structure itself.

The runtime complexity of bistree_destroy is the same as bitree_destroy, or O (n), where n is the number of nodes in the tree.

bistree_insert

The bistree_insert operation inserts a node into a binary search tree (see Example 9.5). The operation works by recursively calling insert to descend to the point at which the actual insertion should be made. Once we insert the node, we update balance factors on our way back up the tree as the recursion unwinds. If, in so doing, any balance factor reaches ±2, we perform a rotation.

We begin by checking whether we are inserting a node into an empty tree. If this is the case, we simply insert the node and set its balance