# Week 10 - Balanced Binary Trees

## Team

Team name:Error
Date:18/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. |Thanh 516467 |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Minh 511907 |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Kaloyan 511216 |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. |Hoa 487272 |

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

Tree may have at least log2(n+1) – 1 levels
Worst time complexity:
- Removal: O(n)
- Membership testing O(n)

### Activity 2: Remembering tree heights

void bintree_node::update_height() {
    if(is_leaf()){
        m_height=1;
    }
    else{
        if(has_left_child()&&!has_right_child()){
            m_height=this->m_left->m_height+1;
        }
        else if(has_right_child()&&!has_left_child()){
            m_height=this->m_right->m_height+1;
        }
        else{
            m_height=std::max(m_right->m_height,m_left->m_height)+1;
        }
    }
}

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

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

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

### Activity 4: Computing the balance factor

/// Activity 4: compute & return the balance factor of the tree rooted in this node
int bintree_node::balance() const {
    // TODO: compute balance factor
    if(is_leaf())
        return 0;
    else if(has_left_child()&&!has_right_child())
        return 0-m_left->height();
    else if(has_right_child()&&!has_left_child())
        return m_right->height();
    else
        return m_right->height()-m_left->height();
}

### Activity 5: Balancing acts

From figure a, we can conclude that B<=A<=D<=C<=E
In the figure b, C is smaller than D, which is incorrect. In addition, the tree in the figure d is wrong since it displays node A > node D. The only tree preserving right order is tree in the figure c

### Activity 6: Implement left rotation

void bintree_node::rotate_left() {
    // Week 10 - Activity ?
    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)
    // TODO: update heights (use update_height, only for some nodes)
    //to rotate the left node, just simply make the child node
    //become parent node of the current node and the left child node
    //of right child node become right child node of current node

    if(m_right->has_left_child())//check if the right child has sub tree
    {
        m_right->replace_child(m_right->m_left,this);
        this->replace_child(r,rl);
    }

    else{
        m_right->set_left(this);
        this->set_right(nullptr);
    }
    m_parent->m_parent=parent;//update parent for the old right child who is now parent of current node after rotating
    parent->replace_child(this,m_parent);//update the child node for old parent node   
    this->update_height();
    r->update_height();
}

### Activity 7: Implement right rotation

void bintree_node::rotate_right() {
    // TODO: update linkage (use replace_child, set_left, set_right)
    // TODO: update heights (use update_height, only for some nodes)
    auto parent = m_parent;
    auto l= m_left;
    auto lr = m_left->m_right;
    if(m_left->has_right_child()){
        m_left->replace_child(m_left->m_right,this);
        this->replace_child(l,lr);
    }
    else{
        m_left->set_right(this);
        this->set_left(nullptr);
    }
    l->m_parent=parent;
    parent->replace_child(this,m_parent);
    this->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 + 2 | H + 1 | -1 |
| +2 | 0 | H | H + 1 | H + 1 | -1 |
| +2 | +1 | H | H | H + 1 | +1 |
| +2 | +2 | H | H | H + 2 | +2 |

### 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 + 1 | H - 1 | H | +2 |
| -1 | +1 | H + 1 | H | H | +1 |

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

Question 1:
We need to implement the RL rotation for the case where we have +2 for the root and +1 for the right child as the balance after that is not restored and the tree will have a balance +1, which means that is still unbalanced.
Question 2:
The new possibilities for the root's balance is -1 or 0 for perfectly balanced tree or tree that is almost perfectly balanced.
Question 3:
The only possible balance factors after left rotation are -1, 0 and +1.

### Activity 11: Fixing left-heavy trees
Question 1:
For cases -1 and 1. After RR rotation is applied,the new balance factor is +1
Question 2:
The new possibilities for the root's balance is +1 or 0 for perfectly balanced tree or tree that is almost perfectly balanced
Question 3:
The only possible balance factors after left rotation are +1, +2.
### Activity 12: Rebalancing the tree

/// Activity 12: restores the balance of a left-heavy tree  
void bintree_node::fix_left_heavy() {
    switch (m_left->balance()) {
        case 0:
        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:
        case +1:
            rotate_left();
            break;
        case -1:
            m_right->rotate_right();
            rotate_left();
            break;
    }
}

### Activity 13: Verify balance

Record your answer here (include an image of the final tree)
1. The height for the root node in the final tree is 4
2. The balance factor of the root node in the final tree is +0
3. There were 12 times the rotations were performed

## Looking back

### What we've learnt

- Get to know what is a height-balanced tree
- Time complexity of insertion, removal and membership testing
- Learn to balance a binary tree with implementing rotation

### What were the surprises

Nothing

### What problems we've encountered

Nothing

### What was or still is unclear
Nothing

### How did the group perform?

As good as usual