---
# System prepended metadata

title: Week 10 - Balanced Binary Trees

---

# Week 10 - Balanced Binary Trees

## Team

Team name:
Date: 18-6-2022

Members:
Jesse Dijksma

| 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

Each node can have 2 sub-nodes. This means that the minimum amount of levels a tree needs can be derived from the formula: Log2(n) + 1

Worst Time complexity for removal of an element in a BST = O(n)

### Activity 2: Remembering tree heights

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

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

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

figure 3.a = height balanced (net balance = 0)

### Activity 4: Computing the balance factor

```c++
int bintree_node::balance() const {
    auto left_height = 0;
    auto right_height = 0;
    if(has_left_child()) left_height = m_left->height();
    if(has_right_child()) right_height = m_right->height();
    return right_height-left_height;
}
```

### Activity 5: Balancing acts

figure 4.C is correct

4.b: claims C < D which is incorrect.
4.c: correct
4.d: claims D ≤ A ≤ C when it is A ≤ D ≤ C

### Activity 6: Implement left rotation

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

  
    m_right->set_left(this);
    set_right(rl);
    m_parent->update_height();
}
```

### Activity 7: Implement right rotation

```c++
void bintree_node::rotate_right() {
    auto parent = m_parent;
    auto l = m_left;                       //Right node
    auto lr = m_left->m_right;              //Left Node of Right node

    l->set_right(this);
    set_left(lr);
    m_parent->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+1        |H+2          |  0                 |
| +2          |      +2     |    H      |    H+1      |    H+3      |           +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        |  H        |  H        |   +1                |
| -1          |      +1     |    H      |   H+1       | H         |   +2                |

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

• For which of the three cases do we need to perform a right-left rotation?
*If the balance of the current node  =+2 (so we want to left rotate), we first have to right rotate if the child of the current node has a balance of -1.*

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

For the cases where only a left rotation is applied, what are the possible balance factors of
the tree after the left rotation?
*possible balance factors are: -2 to 2*

### Activity 11: Fixing left-heavy trees
• For which of the three cases do we need to perform a left-right rotation?
*if the balance of the current node = -2 (so we want to right rotate), we first have to left rotate if the child ofthe current node has a balance of +1.*
• For the case where an LR rotation is applied, what are the possible balance factors of the
tree after that rotation combo?
*possible balance factors are: -1, 0, +1*
• For the cases where only a right rotation is applied, what are the possible balance factors
of the tree after the rotation?
*possible balance factors are -2 to 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:
            this->rotate_left();
            break;
        case -1:
            this->m_left->rotate_left();
            this->rotate_right();
            break;
        case +1:
            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: {
            this->rotate_left();
            break;
        }
        case +1: {
            this->rotate_left();
            break;
        }
        case -1: {
            this->m_right->rotate_right();
            this->rotate_left();
            break;
        }
    }
}
```

### Activity 13: Verify balance

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


## Looking back

### What we've learnt

BST are a great data structure. Good alternative for hash tables when mememory allocation is important.

### What were the surprises

Fill in...

### What problems we've encountered

Rebalancing the trees doesnt really go well. Single rotations are fine, but LR or RL rotations arent behaving as expected.

### What was or still is unclear

Why the balancing isnt working as expected.

### How did the group perform?

solo





