need code for red-black binary search tree 
Author Message
 need code for red-black binary search tree

        I need to write a body for this generic spec, but am not
quite sure of the best way to do it.  I would be interested to hear
from anyone who has used this technique, and can give me some ideas.

        Thanks in advance


-- Purpose:    This package maintains data items of type ELEMENT_TYPE
--             in a binary, balanced tree using the red-black tree
--             model. With n data items maintained in the tree
--             it provides insert, delete, and search operations
--             with a time complexity of O(lg n) and conducts
--             sorted output via inorder traversal with O(n).

-- NOTES:
--    - The tree will only maintain data items with unique keys.
--    - To modify a data item it first has to be deleted and then
--      reinserted in any modified form.

generic
   type ELEMENT_TYPE is private;
      -- data type for every data item maintained within one node.
   with procedure PRINT_ELEMENT(NODE: in ELEMENT_TYPE);
      -- specifies how the content of one node should be printed
   with function ">"(LEFT, RIGHT: in ELEMENT_TYPE) return BOOLEAN;
      -- specifies the criteria for ordering two data items.
   with function EQUAL(LEFT, RIGHT: in ELEMENT_TYPE) return BOOLEAN;
      -- specifies the criteria for two data items being equal.

package RB_TREE is

   procedure INITIALIZE;
      -- prepares an empty tree. This operation has to be executed
      -- before the tree can be used. If the tree has been used
      -- before, it clears any data that are stored in the tree.

   procedure INSERT(DATA_ITEM: in ELEMENT_TYPE);
      -- inserts a new data item into the tree. if DATA_ITEM already
      -- exists (determined through function EQUAL), it will not be
      -- inserted, i.e the procedure has no effect on the current tree.

   procedure DELETE(DATA_ITEM: in ELEMENT_TYPE);
      -- deletes a data item from the tree if the data item
      -- was found. If the data item was not found in the tree the
      -- procedure has no effect on the current tree.

   procedure SORT_OUTPUT;
      -- prints every node of the tree sequentially in ascending order.

   function SEARCH(DATA_ITEM: in ELEMENT_TYPE) return BOOLEAN;
      -- determines if a certain data item is already contained in the
      -- tree using the criterias set in function EQUAL. If it exists,
      -- SEARCH returns 'true' otherwise it returns 'false.'

end RB_TREE;                    



Sat, 25 May 1996 07:34:41 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. searching trees (AVL, 2-3-4 and red-black trees)

2. Red Black Tree - delete function

3. Program to create Red-Black Trees

4. AVL and red-black trees

5. Red-Black tree in PROLOG

6. Red Black Tree in PROLOG

7. red-black trees in fortran

8. Red - black trees

9. Red-Black-Trees and Fortran 2003 Features

10. Red-Black trees

11. Pls Help! Need binary search tree module

12. Self-Adjusting Binary Search Trees (Splay Trees)

 

 
Powered by phpBB® Forum Software