---
# System prepended metadata

title: Week 10 - Balanced Binary Trees

---

# Week 10 - Balanced Binary Trees

## Team

Team name: Peach Technologies 
Date: 07/12/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.                                             |   Husam Kanoa 512881   |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings.                                              |  Rimma Davletova 508350  |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |  Yazan Tayeh 473427    |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data.                                                   |   Nafiz Redwan 515199   |

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

How many levels does the tree have? Give a formula that gives the minimum number of levels in case the tree has n values. 
- log2(n)

What is the worst-case time complexity of removal and membership testing in a tree with n values where the number of levels is kept as low as possible?
- O(log2[n])

### Activity 2: Remembering tree heights

```c++
void bintree_node::update_height() {  
    // TODO: set m_height to the correct height  
        m_height = ((m_left->height()>m_right->height())?m_left->height():m_right->height())+1;

}
```
### Activity 3: Do it yourself: Balance factors

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

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

### Activity 4: Computing the balance factor

```c++
int bintree_node::balance() const {  
    // TODO: compute balance factor  
  return 0;  
}
```

### Activity 5: Balancing acts

D

### 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;  
    
    (void) parent;
    (void) r;
    (void) rl;
    
    // TODO: update linkage (use replace_child, set_left, set_right)
    r->m_right = parent;
    parent->m_right = rl;
    // TODO: update heights (use update_height, only for some nodes)
    parent->update_height();
    r->update_height();
}
```
Record your answer here

### 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)
    l->m_right = parent;
    parent->m_left = lr;
    // TODO: update heights (use update_height, only for some nodes)
    parent->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       |  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               |

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

##### • For which of the three cases do we need to perform a right-left rotation?
    -1
##### • For the case where an RL rotation is applied, what are the possible balance factors of the tree after the RL rotation?
    0 and +1
##### • For the cases where only a left rotation is applied, what are the possible balance factors of the tree after the left rotation?
    -1 and 0


### Activity 11: Fixing left-heavy trees

##### • For which of the three cases do we need to perform a left-right rotation?
    -1
##### • For the case where an LR rotation is applied, what are the possible balance factors of the tree after that rotation combo?
    -1 and 0
##### • For the cases where only a right rotation is applied, what are the possible balance factors of the tree after the rotation?
    +1 and 0


### 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:
            break;
        case -1:
            m_right->rotate_right();
            rotate_left();
            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:
            break;
        case +1:
            m_left->rotate_left();
            return rotate_right();
            break;
        case -1:
            return rotate_left();
            break;
    }
}
```

### Activity 13: Verify balance

Record your answer here (include an image of the final tree)
##### 1. What is the height of the (root node of the) final tree?
15
##### 2. What is the balance factor of the (root node of the) final tree?
16
##### 3. How many rotations (left or right) were performed during the insertion of the 15 values?

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





