CHAPTER 7
Balanced Trees
NOTE: The material in this presentation is a compilation from the Zybook of “Principles of Data Structure”, the book “Data Structures and other objects using C++” by Michael Main and Walter Savitvch, and original content from your professor.
By Prof. Rafael Orta, M.S.
NOTE: The material in this presentation is a compilation from the Zybook of “Principles of Data Structure”, the book “Data Structures and other objects using C++” by Michael Main and Walter Savitvch, and original material from your professor.
Last week we covered
Agenda for this week
NOTE: The material in this presentation is a compilation from the Zybook of “Principles of Data Structure”, the book “Data Structures and other objects using C++” by Michael Main and Walter Savitvch, and original material from your professor.
Leonidas Guibas (left) / Robert Sadgewick (right)
In a binary tree, each node has up to two children, known as a left child and a right child. "Binary" means two, referring to the two children.
BST trees values are arranged such as left child has a lower value than the parent and the right child has a higher value than the parent.
Problems with BST
AVL: A height balanced BST
“Balanced BST
An AVL tree is a BST with a height balance property and specific operations to rebalance the tree when a node is inserted or removed. A BST is height balanced if for any node, the heights of the node's left and right subtrees differ by only 0 or 1.
A node's balance factor is the left subtree height minus the right subtree height, which is 1, 0, or -1 in an AVL tree.
Recall that a tree (or subtree) with just one node has height 0. For calculating a balance factor, a non-existent left or right child's subtree's height is said to be -1. “
AVL: A balanced tree
“AVL tree height
Minimizing binary tree height yields fastest searches, insertions, and removals. If nodes are inserted and removed dynamically, maintaining a minimum height tree requires extensive tree rearrangements. In contrast, an AVL tree only requires a few local rotations, so is more computationally efficient, but doesn't guarantee a minimum height. However, theoreticians have shown that an AVL tree's worst case height is no worse than about 1.5x the minimum binary tree height, so the height is still O(log N) where N is the number of nodes. Furthermore, experiments show that AVL tree heights in practice are much closer to the minimum.“
AVL: A balanced tree
“Storing height at each AVL node
An AVL tree implementation can store the subtree height as a member of each node. With the height stored as a member of each node, the balance factor for any node can be computed in O(1) time. When a node is inserted in or removed from an AVL tree, ancestor nodes may need the height value to be recomputed.“
AVL: Rotations
“Tree rotation to keep balance
Inserting an item into an AVL tree may require rearranging the tree to maintain height balance. A rotation is a local rearrangement of a BST that maintains the BST ordering property while rebalancing the tree“.
AVL: Insertions
“Insertions requiring rotations to rebalance
Inserting an item into an AVL tree may cause the tree to become unbalanced. A rotation can rebalance the tree“.
AVL: Insertions
“Sometimes, the imbalance is due to an insertion on the inside of a subtree, rather than on the outside as in previous slide. One rotation won't rebalance. A double rotation is needed. “.
AVL: Insertions
AVL: Removals
“Removing nodes in AVL trees
Given a key, an AVL tree remove operation removes the first-found matching node, restructuring the tree to preserve all AVL tree requirements. Removal begins by removing the node using the standard BST removal algorithm. After removing a node, all ancestors of the removed node, from the nodes' parent up to the root, are rebalanced. A node is rebalanced by first computing the node's balance factor, then performing rotations if the balance factor is 2 or -2. “
BF=1
BF=2
BF=1
BF=-1
BF=0
BF=0
BF=0
BF=0
BF=0
BF=0
BF=0
BF=-1
Now we remove 84
Notice left sub-tree does not change
No need for rebalance
No need for rebalance
AVL: Removals
Red-black tree
“A red-black tree is a BST with two node types, namely red and black, and supporting operations that ensure the tree is balanced when a node is inserted or removed. The below red-black tree's requirements ensure that a tree with N nodes will have a height of O(log N).
Red-black tree: Rotations
“Introduction to rotations
A rotation is a local rearrangement of a BST that maintains the BST ordering property while rebalancing the tree. Rotations are used during the insert and remove operations on a red-black tree to ensure that red-black tree requirements hold. Rotating is said to be done "at" a node. A left rotation at a node causes the node's right child to take the node's place in the tree. A right rotation at a node causes the node's left child to take the node's place in the tree.”
Red-black tree: Rotations
“Right rotation is analogous to left rotation. A right rotation at a node requires the node's left child to be non-null.”
Red-black tree: Insertion
“Given a new node, a red-black tree insert operation inserts the new node in the proper location such that all red-black tree requirements still hold after the insertion completes.”
“The red-black re-balance operation consists of the steps below.
Red-black tree: Insertion
Inserting 44 requires two rotations. The first rotation is a right rotation at the parent, node 55. The second rotation is a left rotation at the grandparent, node 33.
Red-black tree: Removal
“Given a key, a red-black tree remove operation removes the first-found matching node, restructuring the tree to preserve all red-black tree requirements.”
Red-black tree: Removal
Red-black tree: Removal