• Choose a category
• All
• Classic-Fiction

By Root 1462 0

search tree and returns a pointer to the data member of its AvlNode structure (see Example 9.5). The operation works by calling lookup recursively to descend through the tree until the desired node is found. At each level, we first check if we have reached the end of a branch. If we reach the end of a branch, the node we are looking for does not exist. Otherwise, we move to either the left or right in the same manner as described for bistree_insert. The recursion terminates once we encounter the desired node, at which point we return 0.

The analysis of searching an AVL tree is the same as for inserting a node. Thus, the runtime complexity of bistree_lookup is O (lg n).

bistree_size

This macro evaluates to the size of a set (see Example 9.4). It works by accessing the size member of the BisTree structure.

The runtime complexity of bistree_size is O (1) because accessing a member of a structure is a simple task that runs in a constant amount of time.

Example 9.5. Implementation of the Binary Search Tree Abstract Datatype

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

* *

* ------------------------------- bistree.c ------------------------------ *

* *

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

#include

#include

#include "bistree.h"

static void destroy_right(BisTree *tree, BiTreeNode *node);

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

* *

* ------------------------------ rotate_left ----------------------------- *

* *

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

static void rotate_left(BiTreeNode **node) {

BiTreeNode *left,

*grandchild;

left = bitree_left(*node);

if (((AvlNode *)bitree_data(left))->factor == AVL_LFT_HEAVY) {

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

* *

* Perform an LL rotation. *

* *

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

bitree_left(*node) = bitree_right(left);

bitree_right(left) = *node;

((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;

((AvlNode *)bitree_data(left))->factor = AVL_BALANCED;

*node = left;

}

else {

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

* *

* Perform an LR rotation. *

* *

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

grandchild = bitree_right(left);

bitree_right(left) = bitree_left(grandchild);

bitree_left(grandchild) = left;

bitree_left(*node) = bitree_right(grandchild);

bitree_right(grandchild) = *node;

switch (((AvlNode *)bitree_data(grandchild))->factor) {

case AVL_LFT_HEAVY:

((AvlNode *)bitree_data(*node))->factor = AVL_RGT_HEAVY;

((AvlNode *)bitree_data(left))->factor = AVL_BALANCED;

break;

case AVL_BALANCED:

((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;

((AvlNode *)bitree_data(left))->factor = AVL_BALANCED;

break;

case AVL_RGT_HEAVY:

((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;

((AvlNode *)bitree_data(left))->factor = AVL_LFT_HEAVY;

break;

}

((AvlNode *)bitree_data(grandchild))->factor = AVL_BALANCED;

*node = grandchild;

}

return;

}

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

* *

* ----------------------------- rotate_right ----------------------------- *

* *

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

static void rotate_right(BiTreeNode **node) {

BiTreeNode *right,

*grandchild;

right = bitree_right(*node);

if (((AvlNode *)bitree_data(right))->factor == AVL_RGT_HEAVY) {

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

* *

* Perform an RR rotation. *

* *

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

bitree_right(*node) = bitree_left(right);

bitree_left(right) = *node;

((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;

((AvlNode *)bitree_data(right))->factor = AVL_BALANCED;

*node = right;