Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am educating myself on algorithms and data structures. For that, I am doing a simple program that would read lines like this:

bdhj 168.24
dahf 42.88
dhfa 128.92

First column represents an account name (and it needn't have to be 4 characters), and second represents value to add (or remove if value is negative) to that account. I have a huge test data that I could profile different algorithms. I tried keeping this information in linked list and dynamic arrays and some mixture of that two so far. Although dynamic arrays were good at allowing binary search, inserting elements requires a call to memmove (since I am inserting sorted) and it takes a lot of time. I want to try binary search trees for this program, however, I don't have any idea how to keep search tree balanced. I tried google search, but couldn't find any explanations about a algorithm I could use, or any pointers at all. Could you give pointers and/or sources that I could check?

share|improve this question
    
    
Glance also at a skip list - en.wikipedia.org/wiki/Skip_list . Instead of using an array, it uses a linked list that has multiple 'levels' to it. These levels allow the skip list to do lookups as if it was a balanced binary tree, and the algorithm for lookup, insert, and delete are simpler than those of a binary tree. –  MichaelT May 1 '12 at 14:58

1 Answer 1

up vote 7 down vote accepted

There are some self-balanced trees such as Red-Black tree and AVL tree. For more information see:

Wikipedia: Self-balancing binary search tree

Wikipedia: Red–Black tree

Wikipedia: AVL tree

or Chapter 13 of CRLS book

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.