---
# System prepended metadata

title: Week 10 - Self-balancing trees

---

# Week 10 - Self-balancing trees

## Team

Team name:
Date:

Members
Anton Vorderman
Thom Kistemaker
Nian Luisman

| 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

### Activity 1: Time complexity

aantal levels: <sup>2</sup>log(n+1)
Time complexity: O(<sup>2</sup>log(n+1))

### Activity 2: A naive approach

Visited nodes: n
Time Complexity: O(n)


### Activity 3: Remembering tree heights

```cpp=
void bintree_node::update_height() {
    if (this->m_right == nullptr && this->m_left == nullptr){
        this->m_height = 0;
    }
    else if(this->m_right == nullptr){
        this->m_height = this->m_left->m_height + 1;
    }
    else if(this->m_left == nullptr){
        this->m_height = this->m_right->m_height + 1;
    }
    else {
        this->m_height = std::max(this->m_left->m_height, this->m_right->m_height) + 1;
    }
}
```

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

|Left tree|   |               | |Right tree|    |                |
|----|--------|---------------|-|------|--------|----------------|
|Node| Height | Balance Factor| | Node | Height | Balance Factor |
|A   |3       | -1            | | K    |3       | -2             |
|B   |1       | -1            | | L    |2       | 1              |
|C   |0       | 0             | | M    |0       | 0              |
|D   |2       | -1            | | N    |1       | 0              |
|E   |1       | 0             | | P    |0       | 0              |
|F   |0       | 0             | | Q    |0       | 0              |
|G   |0       | 0             | | R    |0       | 0              |
|H   |0       | 0             |

De linker tree heeft geen balance factor groter dan 1 of kleiner dan -1, en wordt dus gezien als balanced.
De rechter tree heeft een balance factor van -2, en zou dus niet moeten worden beschouwd als balanced.

### Activity 5: Computing the balance factor
```cpp=
int bintree_node::balance() const {
    if(this->m_right == nullptr && this->m_left == nullptr){
        return 0;
    }
    else if(this->m_right == nullptr){
        return -1 - this->m_left->m_height;
    }
    else if(this->m_left == nullptr) {
        return this->m_right->m_height + 1;
    }
    else {
        return this->m_right->m_height - this->m_left->m_height;
    }
}
```
Record your answer here

### Activity 6: Balancing acts

Tree c is correct

### Activity 7: Implement left rotation

```cpp=
void bintree_node::rotate_left() {
    auto r = m_right;
    auto rl = m_right->m_left;
    auto parent = m_parent;
    parent->replace_child(this, r);
    m_right->set_left(this);
    set_right(rl);
    update_height();
    r->update_height();
}
```

### Activity 8: Implement right rotation
```cpp=
void bintree_node::rotate_right() {
    auto l = m_left;
    auto lr = m_left->m_right;
    auto parent = m_parent;
    parent->replace_child(this, l);
    m_left->set_right(this);
    set_left(lr);
    update_height();
    l->update_height();
}
```
### Activity 9: Left rotations and balance

|Balance Factors | |Subtree Heights| | |Balance factor of tree after rotation|
|----|----|---|-----|-----|--------|
| A  | B  | C | D   | E   |        |
| +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   | H+2 |+1      |
### Activity 10: Right rotations and balance

|Balance Factors | |Subtree Heights| | |Balance factor of tree after rotation|
|----|----|-----|-----|-----|--------|
| A  | B  | C   | D   | E   |        |
| -1 | -1 | H   | H-1 | H   |+1      |
| -1 | 0  | H   | H   | H   |+1      |
| -1 | +1 | H-1 | H   | H   |+2      |

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

-right-left rotation when the right child is -1.
-the balance factor for the top node is always 0 after the RL rotation.
the first level sub nodes can be -1, 0 or +1.
-Only a left rotation when the right child is +1. After the left rotation the balance factor of the top node is always 0 and the first level sub nodes can be -1, 0 or +1

### Activity 12: Fixing left-heavy trees

-left-right rotation when the right child is +1.
-the balance factor for the top node is always 0 after the LR rotation.
the first level sub nodes can be -1, 0 or +1.
-Only a right rotation when the left child is -1. After the right rotation the balance factor of the top node is always 0 and the first level sub nodes can be -1, 0 or +1

### Activity 13: Rebalancing the tree



## Look back

### What we've learnt

Self-balancing trees.
Balancing factors
Right and left heavy trees.
Left and right rotations

### What were the surprises

Activity 7 was wel ietsje lastig
Activity 9 & 10 is voor 2 van de 3 nog niet echt duidelijk.

### What problems we've encountered

Het testen van activity 8 had als nummer "7" er bij staan waardoor deze al getest werd zodra we activity 7 af hadden.

Opgave 9 het voorbeeld daarvan had de letters B en C omgewisseld waardoor dit best onduidlijk was.

### What was or still is unclear

Activity 9&10

### How did the group perform?

Samenwerking liep soepel. :)



