---
# System prepended metadata

title: Week 10 - Balanced Binary Trees

---

# Week 10 - Balanced Binary Trees

## Team

Team name:
Date:

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.                                             |      |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings.                                              |      |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |      |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data.                                                   |      |

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

De formule heeft minimaal log2(n) levels. De uitkomst moet je naar beneden afronden en dan krijg je het antwoord. voorbeeld: log2(6) = 2.58496250072, dit rond je af naar twee en dan heb je de minimale aantal levels.

### Activity 2: Remembering tree heights

```c++
void bintree_node::update_height() {  
    // TODO: set m_height to the correct height  
    if(this->m_left && this->m_right) {
        this->m_height = std::max(this->m_left->m_height, this->m_right->m_height) + 1;
    } else if(this->m_left) {
        this->m_height = this->m_left->m_height + 1;
    } else if(this->m_right){
        this->m_height = this->m_right->m_height + 1;
    }
}
```
### 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         |

### Activity 4: Computing the balance factor

```c++
int bintree_node::balance() const {
    // TODO: compute balance factor
    int left = 0;
    int right = 0;
    if(this->m_left != NULL) left = this->m_left->m_height;
    if(this->m_right != NULL) right = this->m_right->m_height;
    auto balance = right - left;
    return balance;
}
```

### Activity 5: Balancing acts

C is correct omdat deze tree aan alle voorwaarden voldoet.

### Activity 6: Implement left rotation

```c++
void bintree_node::rotate_left() {  
    auto parent = m_parent;  
    auto r = m_right;  
    auto rl = m_right->m_left;  
    // TODO: update linkage (use replace_child, set_left, set_right)  
    // TODO: update heights (use update_height, only for some nodes)  
}
```

```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)
    m_parent = r;
    m_parent->set_left(parent);
    m_parent->m_left->set_right(rl);
    // TODO: update heights (use update_height, only for some nodes)
    m_parent->update_height();
    m_left->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;

    (void) parent;
    (void) l;
    (void) lr;
    // TODO: update linkage (use replace_child, set_left, set_right)

    set_left(lr);
    parent->replace_child(this, l);
    l->set_right(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+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       |  0                 |

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

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

1. bij +1 en 0 moet je right-left toepassen.
2. Bij RL krijg je altijd balance-factor 0.
3. Daar komt balance 0 uit

### Activity 11: Fixing left-heavy trees
1. bij -1 en 0 moet je left-right toepassen.
2. Bij LR krijg je balance-factor 0.
3. Daar komt balance 0 uit

### 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:  
        case +1:  
            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:  
        case -1:  
            break;  
    }  
}
```

### Activity 13: Verify balance

Record your answer here (include an image of the final tree)


## Looking back

### What we've learnt

Formulate at least one lesson learned.

### What were the surprises

Fill in...

### What problems we've encountered

Fill in...

### What was or still is unclear

Fill in...

### How did the group perform?

How was the collaboration? What were the reasons for hick-ups? What worked well? What can be improved next time?





