# Week 10 - Balanced Binary Trees

## Team

Team name: BeastsFromTheEast
Date: 31/07/2023

Members: Attila Poldan, Nikola Zahariev, Casian Ionescu, Alexandra Melei

| 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

Record your answer here
log2(n)

### Activity 2: Remembering tree heights

void bintree_node::update_height() {  
    // TODO: set m_height to the correct height  
    
	if(is_leaf())
	{
		m_height = 1;

	}

	if(has_left_child() && !has_right_child())
	{
		m_height = m_left->m_height + 1;

	}
    
	if(has_right_child() && !has_left_child())
	{
		m_height = m_right->m_height + 1;

	}
    
	if(has_left_child() && has_right_child())
	{
		m_height = std::max(m_left->m_height,m_right->m_height) + 1;

	}

}

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

### Activity 4: Computing the balance factor

int bintree_node::balance() const 
{  
    // TODO: compute balance factor  
    
  	if(is_leaf())
	{
		return 0;
	}
    
	if(!has_right_child() && has_left_child())//because the left tree will be bigger than right, so it will be left heavy
	{
		return -(m_left->m_height);
	}
    
	if(!has_left_child() && has_right_child())
	{
		return m_right->m_height;
	}
    
	if(has_left_child() && has_right_child())
	{
		return m_right->m_height - m_left->m_height;
	} 
}

### Activity 5: Balancing acts

Record your answer here: c)

### Activity 6: Implement left rotation

void bintree_node::rotate_left() {  
    auto parent = m_parent;  
    auto r = m_right;  
    auto rl = m_right->m_left;  
    (void) r;
    (void) rl;
    // TODO: update linkage (use replace_child, set_left, set_right)
    
	parent->replace_child(this,r);
	set_right(rl);
	r->set_left(this);
    // TODO: update heights (use update_height, only for some nodes)
	this->update_height();
	r->update_height();
}

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;

	(void) parent;
	(void) l;
	(void) lr;
	// TODO: update linkage (use replace_child, set_left, set_right)

	parent->replace_child(this,l);
	set_left(lr);
	l->set_right(this);
	// TODO: update heights (use update_height, only for some nodes)
	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 | | | | |
| +2 | 0 | H | H + 1 | H + 1 | -1 |
| +2 | +1 | | | | |
| +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 | | | | |
| -1 | +1 | | | | |

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

Record your answer here

### Activity 11: Fixing left-heavy trees

### 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:  
        case +1:  
            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:  
        case -1:  
            break;  
    }  
}

### Activity 13: Verify balance

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

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