Keeping binary search tree balanced

Question

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?

• jeff charles: en.wikipedia.org/wiki/Red%E2%80%93black_tree or en.wikipedia.org/wiki/AVL_tree
• user40980: 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.

Answer 1

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