# Week 10 - Balanced Binary Trees

## Team

Team name: Totally Useless
Date: 2022/05/20

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

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

* If there are n nodes in binary tree, the minimum height is floor: log2(n).
* The worst time complexity to remove or search for a certain value is: O(n) when the height is kept as low as possible.

### Activity 2: Remembering tree heights

void bintree_node::update_height() {  
    m_height = 1 + std::max((has_left_child()? m_left->m_height : 0), (has_right_child()? m_right->m_height : 0));
}

### 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 tree that is height balanced is the first one because the balance factor is either 1 or 0 which are 2 of the valid balance factors for a balanced tree. The second one on the other hand, has K with a balance factor of -2 which means that it's not a balanced tree.

### Activity 4: Computing the balance factor

int bintree_node::balance() const {
    return ((has_right_child()? m_right->m_height : 0) - (has_left_child()? m_left->m_height : 0));
}

### Activity 5: Balancing acts

The correct tree is C because if we comapare the values for A: B<=A<=D<=C<=E and C follows the same logic: B<=A<=D<=C<=E
### Activity 6: Implement left rotation

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

Record your answer here

### Activity 7: Implement right rotation

void bintree_node::rotate_right() {  
    auto parent = m_parent;
   auto l = m_left;
   auto lr = m_left->m_right;
   l->set_right(this);
    set_left(lr);
    parent->replace_child(this,l);
    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 | -1 |
| +2 | +2 | H | H+1 | H+1 | -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?**
In the case that the right child has a balance of +1 we need to perform a right-left rotation.

**• 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 are 0, +1 or -1.

**• 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 are -2 and -1.

### Activity 11: Fixing left-heavy trees
• **For which of the three cases do we need to perform a left-right rotation?**
In the case that the left child has a balance factor of -1 we need to perform a left-right rotation.

**• 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 are 0, +1 or -1.

**• 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 are +2 and +1.

### Activity 12: Rebalancing the tree

void bintree_node::fix_left_heavy() {
    switch (m_left->balance()) {
        case 0:
            rotate_right();
            break;
        case -1:
           rotate_right();
            break;
        case +1:
            m_left->rotate_left();
            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:
            rotate_left();
           break;
        case +1:
            rotate_left();
            break;
        case -1:
            m_right->rotate_right();
            rotate_left();
            break;
    }
}

### Activity 13: Verify balance
The height of the tree is 4.
The tree is perfectly balanced so the balance is 0.
The number of rotations needed was 10 and the final tree looks like this:

## Looking back

### What we've learnt

Formulate at least one lesson learned.

### What were the surprises

Implementation of the rotation of the trees

### What problems we've encountered

Understanding the basics of Binary Trees. In addition, we could not meet and work together as much.

### What was or still is unclear

Rotation of binary tress

### How did the group perform?

The group performed good. There were problems with the communication and the difficulty of the activities.