home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / lang / c / 11740 < prev    next >
Encoding:
Text File  |  1992-07-29  |  1.4 KB  |  32 lines

  1. Newsgroups: comp.lang.c
  2. Path: sparky!uunet!cs.utexas.edu!tamsun.tamu.edu!venus.tamu.edu!jle9162
  3. From: jle9162@venus.tamu.edu (ECKHARDT, JASON LEE)
  4. Subject: Re: Balancing Binary Search Trees
  5. Message-ID: <29JUL199223244481@venus.tamu.edu>
  6. News-Software: VAX/VMS VNEWS 1.41    
  7. Sender: news@tamsun.tamu.edu (Read News)
  8. Organization: Texas A&M University, Academic Computing Services
  9. References: <1992Jul29.014821.2675@samba.oit.unc.edu>
  10. Distribution: usa
  11. Date: Thu, 30 Jul 1992 04:24:00 GMT
  12. Lines: 18
  13.  
  14. In article <1992Jul29.014821.2675@samba.oit.unc.edu>, Alan.Tai@bbs.oit.unc.edu (Alan Tai) writes...
  15. >I currently have a binary search tree to store an alphabetized list of
  16. >words, but would like it to be optimized for speed of retrieval.  Could
  17. >someone please post some example code for balancing binary trees, or
  18. >even suggest a book that might have this code.  So far, I haven't come
  19. >across any texts that have this, though.  Thanks!> 
  20.  
  21.   An AVL implementation of a binary tree is a good way to keep a close to
  22. perfectly balanced tree at all times.  The insertions and deletions will
  23. be the only algorithms to change. They will be slightly more complex as 
  24. rotations of unbalanced portions of the tree are required. The added complexity
  25. is almost always worth the added speed of searching obtained from a balanced
  26. tree though. 
  27.   Good reference for AVL trees are 'Data Structures and Program design in C'
  28. by Kruse, et al. or Knuth  vol. 3.
  29.  
  30. Hope it helps...jason
  31.  
  32.