avl.h 1.4 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243
  1. /* $Id$ */
  2. /* AVL-trees: trees in which the difference in depth
  3. of the left branch and the right branch is at most one.
  4. Information in the nodes is represented by a pointer, which is to
  5. be supplied by the user. The user is also expected to supply a
  6. comparison routine for each AVL tree. This routine is offered two
  7. parameters, both pointers, and is expected to return:
  8. a negative number if the comparison result is <
  9. 0 if the comparison result is =
  10. a positive number if the comparison result is >
  11. */
  12. typedef struct avl_tree *AVL_tree;
  13. /* extern AVL_tree create_avl_tree(int (*cmp)());
  14. Returns a fresh avl_tree structure. 'cmp' will be used as comparison
  15. routine for this tree.
  16. */
  17. extern AVL_tree create_avl_tree();
  18. /* extern add_to_avl_tree(AVL_tree tree, char *n);
  19. Adds the information indicated by 'n' to the avl_tree indicated by 'tree'.
  20. */
  21. extern add_to_avl_tree();
  22. /* extern char *find_ngt(AVL_tree tree, char *n);
  23. Returns the information in the largest node that still compares <= to 'n',
  24. or 0 if not present.
  25. */
  26. extern char *find_ngt();
  27. /* extern char *find_nlt(AVL_tree tree, char *n);
  28. Returns the information in the largest node that still compares >= to 'n',
  29. or 0 if not present.
  30. */
  31. extern char *find_nlt();
  32. /* extern char *find_eq(AVL_tree tree, char *n);
  33. Returns the information in the node that compares equal to 'n',
  34. or 0 if not present.
  35. */
  36. extern char *find_eq();