A Strictly Binary Tree is a binary tree where each nonleaf has exactly two children.

A Full Binary Tree of depth k is a binary tree of depth k having 2^k -1 nodes, k>0.

A binary tree with n nodes and depth k is Complete iff its nodes correspond to the nodes numbered 1 to n in the full binary tree of depth k. (definition on pg. 461 of text)

[Another def:] A Complete Binary Tree is a tree in which

1. every leaf is at one or two levels (say k or k+1)
2. if a node has a right descendent at level k+1, all of its left descendents which are leaves are at level k+1 also
3. the tree is full on the level k set of nodes

AVL Trees or Balanced Binary Trees

(1962 Adelson-Velskii and Landis)            check out their notes and java visual

(page 601 in text)

Why balance a binary tree?

To avoid worst case searches

Examples:

more

The order of search in a binary tree is O(n) for a tree with n items!

Balanced trees can improve this to O(log₂n) (even worse case) as well as make insert and delete be O(log₂n). Why?

Simple definition: An AVL tree is a binary tree in which for every node the heights of its two subtrees never differ by more than one.

Recursive Definition: An empty tree is height-balanced. If T is a nonempty binary tree with T_L and T_R as its left and right subtrees respectively, then T is height-balanced iff (1) T_L and T_R are height-balanced and (2) |h_L - h_R| < 1 where h_L and h_R are the heights of T_L and T_R respectively.

A balanced factor is assigned to each node

Definition: The balance factor BF(T) of a node T in a binary tree is defined to be h_L - h_R, where h_L and h_R, respectively, are the left and right subtrees of T. For any node T in an AVL tree, BF(T) = -1,0, or 1.

( -1 is "Right High", 0 is balanced, 1 is "Left High")

Examples of trees with BFs and insert 32 and new BF's.

Let A denote the nearest ancestor to the newly inserted node whose balance factor is either -2 or 2. (in our example, Node A would have been 40). The balance factor of all nodes on the path from A to the newly inserted node was 0 prior to the insertion. (See page 606 for additional useful observations.)
Let X denote the last node encountered that has such a balance factor. The only way the tree can become unbalanced is if the insertion causes BF(X) to change from -1 to -2 or from 1 to 2.

Balance factors examples

Now, do BFs below (notice what changes and what doesn't).

Rotate around x and r. Do BFs again (do!)

Insertion

Fig. 16.3 General Inserts- additions (depending on where) can make one side too heavy

Four kinds of rotations for rebalancing after inserts:

LL and RR are symmetric as are LR and RL.

Notice the word rotation - these trees will rotate.

• LL: new node Y is inserted in the left subtree of the left subtree of A (rotates right/clockwise then flip right))

• LR: new node Y is inserted in the right subtree of the left subtree of A

• RR: new node Y is inserted in the right subtree of the right subtree of A

• RL: new node Y is inserted in the left subtree of the right subtree of A

Follow month insertions (previous text) Months , possibilities , inserting with balancing

Cool, eh! How do they do this?

To carry out rotations, it is necessary to locate the node A around which the rotation is to be performed. This is the nearest ancestor of the newly inserted node whose balance factor becomes +2.

For the nodes balance factor to become +2, its balance factor must have been +1 before the insertion. Therefore, before insertion, the balance factors of all the nodes on the path from A to the new insertion point must have been 0. (Now they have become +1.)

Again, four kinds of rotations for rebalancing after inserts: (pg 609, Fig. 16.4 and 16.5) and Fig. 16.6 steps.

LL and RR are symmetric as are LR and RL.

Consider LL. Tree is left left heavy (i.e., BA are both heavy - rotate right right). Note that before and after rotation the Inorder traversal is B_LBB_RAA_R

LR and RL take these two steps in opposite directions

An intermediate step LR. First step in LR is to rotate left pivoting on the L child of the 2 high node

Do BFs for both trees

Note: from new addition, one works from nearest +2.

After change (balance) nodes not concerned will be the same as before the shift (so don't change those before the nearest +2).

Fig16.7 , Fig16.8 , Fig16.9 Information on deletes and examples of code is also on the web: above mentioned notes, Skiena notes , Data Structures 2 slides

Some neat pages: Another AVL running (java) (WAY cool), C++ notes MITs Red-Black tree notes
Chapter on trees from another (Kruse) book for this course (check out for binary and AVL sample code)