---
# System prepended metadata

title: Week 10 - Balanced Binary Trees

---

# Week 10 - Balanced Binary Trees

## Team

Team name: Academy Award Winning, Choccy Milk Drinking, Argonian Maid Reading, Cross Dressing SIMPS In Yugoslavia With Honda Accords On The Quest For Feet

Date: 25/04/2022
yes(66%)

Members
Mihnea:            Mihnea Bastea       (514541)
Vlad:              Vladislav Serafimov (509761)
Steve:             Stephen Cruz Wright (521476)

| Role                                                                                                                                                                          | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon.                                             |   Mihnea   |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings.                                              |   Vlad   |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data.                                                   |   Steve   |

## 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

The minimum number of levels is |log_2⁡(n+1)|-1.
The worst-case time complexity of removal and membership testing is O(n).

### Activity 2: Remembering tree heights

```c++=
void bintree_node::update_height() {
    auto left_height = has_left_child()? m_left->m_height : 0;
    auto right_height = has_right_child()? m_right->m_height: 0;
    m_height = 1 + std::max(left_height, right_height);
}
```
### Activity 3: Do it yourself: Balance factors

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

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

Therefore we can conclude that the left tree is balanced as the balance factor is not more or less than 1

### Activity 4: Computing the balance factor

```c++=
int bintree_node::balance() const {  
    // TODO: compute balance factor  
    return (has_right_child()? m_right->m_height: 0) - (has_left_child()? m_left->m_height : 0);

}
```

### Activity 5: Balancing acts

b)
B ≤ A ≤ C ≤ D and D ≤ E
This is not the case with a therefore this is not a viable tree

c)
B ≤ A ≤ D ≤ C and C ≤ E
This is also the case with a) therefore this is a viable tree

d)
B ≤ D ≤ A ≤ C and C ≤ E
This is also the case with a) if A == D therefore this is also a viable tree

### Activity 6: Implement left rotation

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

    r->set_left(this);
    set_right(rl);
    parent->replace_child(this, r);

    update_height();
    r->update_height();
}

```

### Activity 7: Implement right rotation

```c++=
void bintree_node::rotate_right() {
    auto parent = m_parent;
    auto l = m_left;
    auto lr = m_left->m_right;

    l->set_right(this);
    set_left(lr);
    parent->replace_child(this, l);

    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 + 1    | H        | -2                |
| +2          |      0      |    H     | H + 1    | H + 1    | -1                |
| +2          |     +1      |    H     | H        | H + 1    | 0                 |
| +2          |     +2      |    H     | H - 1    | H + 1    | 1         1       |

### 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        | H        | +1                |
| -1          |     +1      |    H     | H + 1    | H        | +2                |
```c++
bintree_node *bintree_node::remove() {
    if (is_leaf()) {
    } else if (has_right_child()) {
    } else if (has_left_child()) {
    } else {
    }
}
```


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

• For which of the three cases do we need to perform a right-left rotation?
-1

• For the case where an RL rotation is applied, what are the possible balance factors of the
tree after the RL rotation?
0 or +1

• For the cases where only a left rotation is applied, what are the possible balance factors of
the tree after the left rotation?
+1 or +2

### Activity 11: Fixing left-heavy trees

• For which of the three cases do we need to perform a left-right rotation?
+1

• For the case where an LR rotation is applied, what are the possible balance factors of the
tree after that rotation combo?
0 or -1

• For the cases where only a right rotation is applied, what are the possible balance factors
of the tree after the rotation?
-1 or -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

* What is the height of the (root node of the) final tree?
4

* What is the balance factor of the (root node of the) final tree?
0

* How many rotations (left or right) were performed during the insertion of the 15 values?
7


Image of the final tree:
![](https://i.imgur.com/2DAbE97.png)



## Looking back

### What we've learnt

Balancing binary trees.

### What were the surprises

binary trees are even more annoying than we thought.

### What problems we've encountered

programs wouldnt work due to stupid mistakes.

### What was or still is unclear

why the programs wouldnt work due to stupid mistakes.

### How did the group perform?

gg wp
