---
# System prepended metadata

title: Week 10 - Balanced Binary Trees

---

# Week 10 - Balanced Binary Trees

## Team

Team name: TEAMWORK
Date: 15/05/2022

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

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

Record your answer here:

Formula: 1+floor(log2n)



### Activity 2: Remembering tree heights

```c++
int getMax(int x, int y){
    if (x >= y) {return x;};
    return y;
}

int bintree_node::findHeight(){
    bintree_node *current_node = this;
    if(current_node == nullptr)
        return 0;
    return 1 + getMax(current_node->m_left->findHeight(), current_node->m_right->findHeight());
}

int bintree_node::findHeight() const{
    return 1 + getMax(this->m_left->findHeight(), this->m_right->findHeight());
}

/// Activity 2: compute the height of a node given the heights of its child nodes
void bintree_node::update_height() {
    m_height = findHeight();
}

int bintree_node::height() const {
    return findHeight();;
}
```
### 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        |

the left binary tree is balanced while the right is not because it had a balance factor of -2 at K (-1>x, 1<x)
### Activity 4: Computing the balance factor

```c++
/// Activity 4: compute & return the balance factor of the tree rooted in this node
int bintree_node::balance() {
    int balance_factor;
    balance_factor = this->m_right->findHeight() - this->m_left->findHeight();
    return balance_factor;
}
```

### Activity 5: Balancing acts

Tree 4c preserves the order invariant. The restructuring is correct because the tree now has a balance factor of -1 and the values that are lower are on the left and the higher values are on the right.

### Activity 6: Implement left rotation

```c++
/// Activity 6: Left-rotates the tree rooted in this node
void bintree_node::rotate_left() {
    // Week 10 - Activity 6
    bintree_node *C = this->m_right;
    bintree_node *P = this->m_parent;
    this->m_right = C->m_left;
    if (C->m_left != nullptr) C->m_left->m_parent = this;
    C->m_left = this;
    this->m_parent = C;
    C->m_parent = P;
    if (P != nullptr) {
        if (P->m_right == this) {
            P->m_right = C;
        } else {
            P->m_left = C;
        }
    }
    update_height();
}
```



### Activity 7: Implement right rotation

```c++
/// Activity 7: right-rotates the tree rooted in this node
void bintree_node::rotate_right() {
    bintree_node *B = this->m_left;
    bintree_node *P = this->m_parent;
    this->m_left = B->m_right;
    if (B->m_right != nullptr) B->m_right->m_parent = this;
    B->m_right = this;
    this->m_parent = B;
    B->m_parent = P;
    if (P != nullptr) {
        if (P->m_left == this) {
            P->m_left = B;
        } else {
            P->m_right = B;
        }
    }
    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        | H+2      | +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-1    | H        | 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

Record your answer here:

1. For which of the three cases do we need to perform a right-left rotation?
When the balance factor of the nodes right child is -1.

2. For the case where an RL rotation is applied, what are the possible balance factors of the tree after the RL rotation?
-The possible balance factors of the tree are 0, -1.

3. For the cases where only a left rotation is applied, what are the possible balance factors of the tree after the left rotation?
The possible balance factors of the tree are

### Activity 11: Fixing left-heavy trees

1. For which of the three cases do we need to perform a left-right rotation?
When the balance factor of the nodes left child is +1.

3. For the case where an LR rotation is applied, what are the possible balance factors of the tree after that rotation combo?
The possible balance factors of the tree are 0, +1.

5. For the cases where only a right rotation is applied, what are the possible balance factors of the tree after the rotation?
The possible balance factors of the tree are 

```c++
bintree_node *bintree_node::remove() {
    if (is_leaf()) {
    } else if (has_right_child()) {
    } else if (has_left_child()) {
    } else {
    }
}
```

### Activity 12: Rebalancing the tree

```c++
/// Activity 12: restores the balance of a left-heavy tree
void bintree_node::fix_left_heavy() {
    if (this->m_left->balance() > 0) {
        this->m_left->rotate_left();
        this->rotate_right();
    } else {
        this->rotate_right();
    }
}

/// Activity 12: restores the balance of a right-heavy tree
void bintree_node::fix_right_heavy() {
    if (this->m_right->balance() < 0) {
        this->m_right->rotate_right();
        this->rotate_left();
    } else {
        this->rotate_left();
    }
}
```

### Activity 13: Verify balance

![](https://i.imgur.com/mxCQVI7.png)
![](https://i.imgur.com/TCziNp2.png)



## Looking back

### What we've learnt

We learned how to restore balance and to right and left rotate to balance the tree.

### What were the surprises

How unbalanced self balancing trees are

### What problems we've encountered

Encountered problems using the functions given to left and right rotate.

### What was or still is unclear

nothing

### How did the group perform?

Collaboration was done, communication is a little bit of a problem.





