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