---
# System prepended metadata

title: '[Week 10 - Zelf-balancerende bomen (Neppe Plastice Bomen - Radiohoofd (De buigingen))](https://bit.ly/3ymOmoi)'

---

# [Week 10 - Zelf-balancerende bomen (Neppe Plastice Bomen - Radiohoofd (De buigingen))](https://bit.ly/3ymOmoi)

## Team

Team name: fLOP Weebs's
Date: 19 mei

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

## Activities

### Activity 1: Time complexity

 A balanced tree has a minimum of log2(n) levels with n being the amount of nodes in the tree. the result of this formula must be rounded upwards.
 Removal and membership testing have a time complexity of log(n).

### Activity 2: A naive approach

1
```cpp=
int height(const bintree_node* node) {
  if (node == nullptr)
    return -1;
  else
    return std::max(height(node->left()), height(node->right())) + 1;
```

This functies walks over each node in the binary tree recursively. This means that each node is visited.
- The node visits each node, and it's child node(s)
- The time complexity is O(n)



### Activity 3: Remembering tree heights

```cpp=
int calculate_height(const bintree_node* node) {
    if (node == nullptr)
        return -1;
    else
        return std::max(calculate_height(node->left()), calculate_height(node->right())) + 1;
}

void bintree_node::update_height() {
    // Activity 3 ; Neppe plastic bomen - Radiohoofd
    m_height = calculate_height(this);
}
```


### Activity 4: Do it yourself: Balance factors

Left tree:

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

Total balance: 0

Right tree:

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

Total balance: -4

Left tree is balanced.

### Activity 5: Computing the balance factor

```c=
    return calculate_height(this->right()) - calculate_height(this->left());

```

### Activity 6: Balancing acts

Tree C is the correctly restructured tree.

### Activity 7: Implement left rotation

```c=
void bintree_node::rotate_left() {
    if(this->m_left != nullptr){
        return;
    }
    bintree_node* X = this->m_right;
    bintree_node* Y = this->m_left;

    X->m_left = this;
    this->m_right = Y;

    this->m_height = calculate_height(this);
    X->m_height = calculate_height(X);
}
```


### Activity 8: Implement right rotation


```c=
void bintree_node::rotate_right() {
    if(this->m_right != nullptr){
        return;
    }
    bintree_node* X = this->m_left;
    bintree_node* Y = this->m_right;

    X->m_right = this;
    this->m_left = Y;

    this->m_height = calculate_height(this);
    X->m_height = calculate_height(X);
}
```
### Activity 9: Left rotations and balance

| A  | C  | B | D   | E   | Balance after rotation |
|----|----|---|-----|-----|------------------------|
| +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 10: Right rotations and balance

| A  | B  | C   | D   | E | Balance after rotation |
|----|----|-----|-----|---|------------------------|
| -1 | -1 | H   | H-1 | H | +1                     |
| -1 | 0  | H   | H   | H | +2                     |
| -1 | +1 | H-2 | H   | H | +4                     |

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

- We need to perform a right-left rotation if the subtree has a balance factor of -1.
- 0
- 0 or -1


### Activity 12: Fixing left-heavy trees

- We need to perform a left-right rotation if the subtree has a balance factor of +1.
- 0
- 0 or +1

### Activity 13: Rebalancing the tree

```c=
void bintree_node::fix_left_heavy() {
    // Activity 13
    switch (m_left->balance()) {
        case 0:
            rotate_right();
            break;
        case -1:
            rotate_right();
            break;
        case +1:
            m_left->rotate_left();
            rotate_right();
            break;
    }
}
```

```c=
void bintree_node::fix_right_heavy() {
    // Activity 13
    switch (m_right->balance()) {
        case 0:
            rotate_left();
            break;
        case +1:
            m_right->rotate_right();
            rotate_left();
            break;
        case -1:
            rotate_left();
            break;
    }
}
```

## Look back

### What we've learnt

We've learned to work with BSTs and balancing algorithms

### What were the surprises

Everything went extremely smoothly and was fairly straight-forward.

### What problems we've encountered

We didn't encounter many problems.
There was one piece of code we wrote wrongly which we had to fix later on.

### What was or still is unclear

Where and when BSTs are applied in practice.

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

Collaboration went smoothly as always. Our weekly schedules line up perfectly so choosing a time to work was no problem. We know eachother well and we know how and where to help eachother.


