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?
Best Answer
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