1. AVL Trees - Rotating the nodes

If the tree is unbalanced, the complexity may increase to O(N).
The method to keep the tree balanced is called node rotation.
AVL Trees are binary search trees that use node rotation upon inserting a new node.
(Adelson-Velskii and Landis)

AVL idea: keep the tree in balance condition - the left and the right subtrees
of each node should differ by at most one level.
It can be proved that if this condition is observed the depth of the tree is O(logN).

Rotation of nodes

When new nodes are inserted the balance condition might be violated.
To restore the balance we rotate the nodes:

When we insert a new node, one of the subtrees may become longer by 2 than the other.
We shall call this subtree - violated subtree, and the node which has this subtree - violated node.
The violated subtree may be left or right subtree of the violated node.
In its turn the violated subtree has a root and two subtrees: left -we'll call it LS, and right - RS.
The new node has been inserted either in LS or in RS.

Two cases are considered:

1. The subtree where the new node is inserted is on the same side as the violated subtree., e.g. the new node has been inserted in LS, and the violated subtree is a left subtree.
2. The subtree where the new node is inserted is on different side, e.g. the new node has been inserted in LS, and the violated subtree is a right subtree.

Example:

Same side:



Different side:



 

Single rotation: to fix the tree in the first case

The violated node has to be lowered, and the root of the violated tree - moved up.



A - the violated node
Tree1 - right subtree that causes the balance violation
B - root of Tree1
Tree2 - its right subtree, where the new node is inserted
C - root of the left subtree of B

Rotate nodes A and B


Nodes whose links are going to change: Parent of A, A, B

Rearrangement of links:

WAS:					BECOMES:


Parent of A				Parent of B
A_right →  B				A_right →  C
B_left  →  C				B_left  →  A

New Tree after rotation



Double rotation



Tree1 - right subtree (the violated tree)
Tree2 - left subtree (the subtree of Tree1 where the new node is inserted)

The sides are different, so we need double rotation.

What happens if we do a single rotation between node A and node B?

Tree2 becomes a right subtree of node A,
the new node (with the additional link) is in Tree2,
and since node A is lowered, the balance is not restored.

The method:


Do a single rotation between node C and node B.
Node C will become the root of Tree1.
As a result Tree2 will change - its depth will be decreased,
at the expense of increasing
the depth of the right subtree of Tree1.

This is now the first case - the violated tree and its subtree with increased depth
will have same side - they are both right subtrees.
We can apply single rotation between the nodes A and C (the new root of Tree1)

1. First rotation between nodes B and C


2. Second rotation between nodes A and C



After this rotation the new node will become right subtree of node A.

• Animation
2. Splay trees

The idea here is that if a node is accessed, probably it will be accessed again
so it is wise to move this node up. Moving up is done through node rotations,
thus dicreasing the depth of the tree and making it more balanced.

3. Multi-way search

In multi-way search, the nodes of the tree contain more than one key. This is another way to decrease the depth of the search tree.

The idea here is:

If the nodes have more than two children, then the tree would have
less levels than if it was a binary tree. Thus if we have N nodes,
the levels in a balanced binary tree are Log₂(N), while the levels in a tree
with m children for a node, m > 2, would be Log_m(N) < Log₂(N).

In this method the nodes may hold one, two or three keys,
and the branching is performed by comparing the key to be found
with the keys stored in a node and finding the interval where the key belongs.
Nodes are used only to contain the keys,
the actual records are stored at the terminal nodes at the bottom of the tree



The nodes are called 2-3-4 way nodes (having 2 links, 3 links and 4 links).

In the example all letters less than E are on the leftmost link,
letters between E and I - along the second link, letters between I and R along the third,
and letters greater than R - along the fourth link - the rightmost one.

Keys within a node are linked in a tree - each node with more than one key contains a tree.

Red-Black trees: The links between the nodes are black, links within a node - red.


4. External search

When there is not enough room to use main memory for the entire tree,
the records are stored on a disk, and the keys only are contained in the main memory.
Keys are usually multi-way keys to increase the branching factor
and to achieve fast access to the records.