Balancing Binary Search Trees

[Daskill]

I'm having trouble grasping the theory of balancing binary search trees and I was wondering if someone in the know could explain it to me?

[WingedPanther]

There's an important question before I attempt to address the question: Are you talking about height balancing or balancing for optimal searching or something else?

[Daskill]

It doesn't say specifically, but I think it's height-balancing.

[WingedPanther]

OK, I'll have to do a little research (I haven't specifically studied the topic, but tend to pick these things up quickly). I'll try to have something later today.

[Daskill]

You're very kind, thank you.

[WingedPanther]

Wikipedia has a nice article on AVL trees (balanced binary trees) and an excellent diagram of the reassignments needed to shift it into balance. It's a pretty simple matter of shuffling some pointers around.

[John]

It should be noted that an AVL Tree is a specific type of Binary Search Tree (which itself is a specific type of a Binary Tree). Generally speaking, a Binary Search Tree makes no restriction on its hight; A BST only has an order property and it requires that the left child is less than its parent and the right child is greater than its parent. So in the best case scenario, a BST it could be logarithmic in size or in the worst case it could be linear in size. An AVL tree prevents the worst case scenario, and is thus a bit more complicated.