---
# System prepended metadata

title: Week 10 - Balanced Binary Trees

---

# Week 10 - Balanced Binary Trees

## Team

Team name:Error
Date:18/05/2022

Members

| Role                                                                                                                                                                       | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon.                                             |Thanh 516467      |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings.                                              |Minh 511907     |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |  Kaloyan 511216     |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data.                                                   |Hoa 487272       |

## Activities
Make sure to have the activities signed off regularly to ensure progress is tracked.

Download the provided project and open it in CLion. **NOTE**: in this week you will have to reuse the code of last week. Follow the instructions given in the `main.cpp` file.

### Activity 1: Time complexity

Tree may have at least log2(n+1) – 1 levels
Worst time complexity:
-	Removal: O(n)
-	Membership testing O(n)


### Activity 2: Remembering tree heights

```c++
void bintree_node::update_height() {
    if(is_leaf()){
        m_height=1;
    }
    else{
        if(has_left_child()&&!has_right_child()){
            m_height=this->m_left->m_height+1;
        }
        else if(has_right_child()&&!has_left_child()){
            m_height=this->m_right->m_height+1;
        }
        else{
            m_height=std::max(m_right->m_height,m_left->m_height)+1;
        }
    }
}
```
### Activity 3: Do it yourself: Balance factors

Left tree (Figure 3a):
| Node | Height | Balance factor |
|------|:------:|:--------------:|
| A    | 3       | 1               |
| B    | 1       | -1               |
| C    | 0       |  0              |
| D    | 2       |-1                |
| E    | 1       | 0               |
| F    | 0       |        0       |
| G    | 0       |        0       |
| H    | 0       |        0       |

Right tree (Figure 3b):
| Node | Height | Balance factor |
|------|:------:|:--------------:|
| K    | 3       | -2               |
| L    | 2       |  1              |
| M    |0        | 0               |
| N    |1        | 0               |
| P    |0        | 0               |
| Q    |0        |0                |
| R    |0        |0                |

### Activity 4: Computing the balance factor

```c++
/// Activity 4: compute & return the balance factor of the tree rooted in this node
int bintree_node::balance() const {
    // TODO: compute balance factor
    if(is_leaf())
        return 0;
    else if(has_left_child()&&!has_right_child())
        return 0-m_left->height();
    else if(has_right_child()&&!has_left_child())
        return m_right->height();
    else
        return m_right->height()-m_left->height();
}

```

### Activity 5: Balancing acts

From figure a, we can conclude that B<=A<=D<=C<=E
In the figure b, C is smaller than D, which is incorrect. In addition, the tree in the figure d is wrong since it displays node A > node D. The only tree preserving right order is tree in the figure c


### Activity 6: Implement left rotation

```c++
void bintree_node::rotate_left() {
    // Week 10 - Activity ?
    auto parent = m_parent;
    auto r = m_right;
    auto rl = m_right->m_left;

    (void) parent;
    (void) r;
    (void) rl;
    // TODO: update linkage (use replace_child, set_left, set_right)
    // TODO: update heights (use update_height, only for some nodes)
    //to rotate the left node, just simply make the child node
    //become parent node of the current node and the left child node
    //of right child node become right child node of current node

    if(m_right->has_left_child())//check if the right child has sub tree
    {
        m_right->replace_child(m_right->m_left,this);
        this->replace_child(r,rl);
    }

    else{
        m_right->set_left(this);
        this->set_right(nullptr);
    }
    m_parent->m_parent=parent;//update parent for the old right child who is now parent of current node after rotating
    parent->replace_child(this,m_parent);//update the child node for old parent node   
    this->update_height();
    r->update_height();
}

```

### Activity 7: Implement right rotation

```c++
void bintree_node::rotate_right() {
    // TODO: update linkage (use replace_child, set_left, set_right)
    // TODO: update heights (use update_height, only for some nodes)
    auto parent = m_parent;
    auto l= m_left;
    auto lr = m_left->m_right;
    if(m_left->has_right_child()){
        m_left->replace_child(m_left->m_right,this);
        this->replace_child(l,lr);
    }
    else{
        m_left->set_right(this);
        this->set_left(nullptr);
    }
    l->m_parent=parent;
    parent->replace_child(this,m_parent);
    this->update_height();
    l->update_height();
}

```

### Activity 8: Left rotations and balance
| A (Balance) | C (Balance) | B Height | D Height | E Height | Balance after rot |
|-------------|:-----------:|:--------:|----------|----------|-------------------|
| +2          |      -1     |    H     | H + 2    |  H + 1   | -1                |
| +2          |      0      |    H     |  H + 1   |  H + 1   |       -1          |
| +2          |      +1     |    H     |  H       |  H + 1   |        +1         |
| +2          |      +2     |    H     |  H       |  H + 2   |        +2         |

### Activity 9: Right rotations and balance
| A (Balance) | B (Balance) | C Height | D Height | E Height | Balance after rot |
|-------------|:-----------:|:--------:|----------|----------|-------------------|
| -1          |      -1     |    H     |  H - 1   |    H     |        +1         |
| -1          |      0      |    H + 1 |  H - 1   |    H     |        +2         |
| -1          |      +1     |    H + 1 |  H       |    H     |        +1         |

### Activity 10: Fixing right-heavy trees using rotation combos

Question 1:
We need to implement the RL rotation for the case where we have +2 for the root and +1 for the right child as the balance after that is not restored and the tree will have a balance +1, which means that is still unbalanced.
Question 2:
The new possibilities for the root's balance is -1 or 0 for perfectly balanced tree or tree that is almost perfectly balanced.
Question 3:
The only possible balance factors after left rotation are -1, 0 and +1.

### Activity 11: Fixing left-heavy trees
Question 1:
For cases -1 and 1. After RR rotation is applied,the new balance factor is +1
Question 2:
The new possibilities for the root's balance is +1 or 0 for perfectly balanced tree or tree that is almost perfectly balanced
Question 3:
The only possible balance factors after left rotation are +1, +2.
### Activity 12: Rebalancing the tree

```c++
/// Activity 12: restores the balance of a left-heavy tree  
void bintree_node::fix_left_heavy() {
    switch (m_left->balance()) {
        case 0:
        case -1:
            rotate_right();
            break;
        case +1:
            m_left->rotate_left();
            rotate_right();
            break;
    }
} 
  
/// Activity 12: restores the balance of a right-heavy tree  
void bintree_node::fix_right_heavy() {
    switch (m_right->balance()) {
        case 0:
        case +1:
            rotate_left();
            break;
        case -1:
            m_right->rotate_right();
            rotate_left();
            break;
    }
}
```

### Activity 13: Verify balance

Record your answer here (include an image of the final tree)
1. The height for the root node in the final tree is 4
2. The balance factor of the root node in the final tree is +0
3. There were 12 times the rotations were performed 
![](https://i.imgur.com/SBZvD6J.png)

## Looking back

### What we've learnt

- Get to know what is a height-balanced tree
- Time complexity of insertion, removal and membership testing 
- Learn to balance a binary tree with implementing rotation

### What were the surprises

Nothing

### What problems we've encountered

Nothing

### What was or still is unclear
Nothing

### How did the group perform?

As good as usual





