2

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?

8

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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