Algorithms – Keeping a Binary Search Tree Balanced

algorithmsbinary treecdata structures

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

Related Topic