A balanced tree is a tree where all the sub-trees (of any node) are approximately the same height/depth.
A self-balancing tree re-balances anytime a node is added or removed from the tree (so tree balance is always maintained).
If a tree is not balanced, in the worst-case (e.g., let's say we get pre-sorted data), the tree can become an "effective" linked list which would push the search times back to O(n).
Left -- A binary tree that is effectively a linked list (occurs if data is pre-sorted)
Right -- A balanced binary tree
We know a sub-tree must be of at least height=3 to
be out of balance. Therefore we can focus on this:
50
\
\
\
80
/
/
/
70
Note that this sketch may be a sub-tree on the tree --
in other words it is not necessarily the root of the tree.
Assuming we just inserted 70, then, relative to the
grandparent 50, we call 80 the parent, and 70 the child.
We'll also use parent-child generally in discussion.
We call this a right-left insert.
As the references tell us, for a right-left insert,
we do a right-left rotation which means:
1. Run a right rotation on the child (e.g., 80)
2. Then run a left rotation on the grandparent (e.g., 50)
Right-Left Rotation
#1 - Right Rotation of Child Node (80)
50 50
\ \
\ \
\ \
80 =====> 70
/ \
/ \
/ \
70 80
#2 - Left Rotation of Grandparent Node (50)
50
\ 70
\ / \
\ =====> / \
70 / \
\ 50 80
\
\
80
A couple pointers
1. Height and Balance Factor and isBalanced
It works nicely to keep a height ivar on every
node (updating it on add/remove).
Then we can easily compute a balance factor as:
right node height - left node height
Thus we have a method:
isBalanced
"returns true if absolute value of balance factor is <= 1"
2. As Balanced
This is a handy helper method (on the node class):
private BSTNode<T> asBalancedForInsert(boolean childInsertedLeft,
BSTNode<T> aNode,
Comparator<T> sortFct)
"return this node as a balanced node"
Your method parameters may vary depending on the algos you come up with
You then call this from the nodes and return the balanced node. The sender
must replace it's left or right with this balanced node. And special care
must be taken for the root node (the BST manages the root).
The beauty of these trees is that the logic looks pretty simple (by diagram)
but they really challenge our code tinkering, testing, and debugging skills.