Lecture notes Midterm and Exam

Trees and AVL tress
The height of a node:

- If the node has no children: -1
- If the node is a parent: 0
- Height of a random node is the max height (left subtree , right subtree) + 1
- Balance is (the height of the left subtree – height of the right subtree) is smaller or equal to 1

Check where the biggest height is:

- Left right subtree? Perform a left-right rotation
- Left left subtree? Perform a right rotation
- Right left subtree? Perform a right-left rotation.
- Right right subtree? Perform a left rotation




Trees important points
- A node without children is a leaf (external node)
- Each node with children is an internal node
- The depth of a node is the length of the path from that node to the root
- The height of a node is the length of the longest path from that node to a leaf

A Binary tree: each node has AT MOST 2 children

A full Binary tree: all internal nodes have 2 children OR 0 children. The following holds if the tree is a
binary tree: the amount of leaves = the amount of internal nodes + 1

Running time of 3 traversal algorithms: Big Theta of n. Each node will be visited exactly 2 times ( in
preorder and inorder) and three times in postorder. Total number of inorder and preorder is 2n and
postorder 3n  Theta(n). Each visit is Theta(1)

AVL trees
Height-Balanced property: for every internal node v, the heights of its children differ at most 1

The height of an AVL tree storing n keys = O(log(n))