---
# System prepended metadata

title: Week 9 - Binary search trees

---

# Week 9 - Binary search trees

## Team

Team name: Group 9
Date: 12-05-2021

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

## Activities

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

*O(log(n))*

• What is the worst-case time complexity of removal and membership testing in a tree where
the number of levels is kept as low as possible?

*Also O(log(n))*


### Activity 2: A naive approach

• How many nodes does the function visit?

*15 (2n+1)*


• What is the time complexity of the height function give above? Give your answer in Big O
notation.

*O(2n+1)*


### Activity 3: Remembering tree heights

CODE:
```c=
void bintree_node::update_height() {
    if (m_left != nullptr && m_right != nullptr){
        m_height = std::max(m_left->m_height, m_right->m_height) + 1;
    } else if (m_left != nullptr){
        m_height = m_left->m_height + 1;
    } else if (m_right != nullptr){
        m_height = m_right->m_height + 1;
    } else {
        m_height = 0;
    }
}
```
PHOTO:
![](https://i.imgur.com/9R1LTYQ.png)


### Activity 4: Do it yourself: Balance factors
Left tree:
| 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:
| 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|


**Which one of the two trees is height-balanced?**
*Answer: The first tree is height balanced.*

### Activity 5: Computing the balance factor
CODE:
```c=
int bintree_node::balance() const {
    if (m_left != nullptr && m_right != nullptr){
        return m_right->m_height - m_left->m_height;
    } else if (m_left != nullptr){
        return -1 - m_left->m_height;
    } else if (m_right != nullptr){
        return m_right->m_height + 1;
    } else {
        return 0;
    }
}
```
PHOTO:![](https://i.imgur.com/x9lIK1U.jpg)



### Activity 6: Balancing acts

**Which of the three trees is correct in the sense that it preserves the order invariant of a binary
search tree? And, more importantly, why is that restructuring correct?**


*Answer: Tree 4C is correct.*

### Activity 7: Implement left rotation

CODE:
```c=
void bintree_node::rotate_left() {
    auto r = m_right;
    auto rl = m_right->m_left;
    auto parent = m_parent;

    m_right->set_left(this);
    set_right(rl);
    parent->replace_child(this, r);

    update_height();
    r->update_height();

}
```
PHOTO:
![](https://i.imgur.com/L4gys8b.jpg)


### Activity 8: Implement right rotation
CODE:
```c=
void bintree_node::rotate_right() {
    auto l = m_left;
    auto lr = m_left->m_right;
    auto parent = m_parent;

    m_left->set_right(this);
    set_left(lr);
    parent->replace_child(this, l);

    update_height();
    l->update_height();

}
```
PHOTO:
![](https://i.imgur.com/TNGWCQC.jpg)


### Activity 9: Left rotations and balance
Balance factors Subtree heights
|A|C|B|D|E|Balance factor of tree after rotation|
| -------- | -------- | -------- | -------- | -------- | -------- |
|+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-1|H+1|1|


### Activity 10: Right rotations and balance

Balance factors Subtree heights
|A|C|B|D|E|Balance factor of tree after rotation|
| -------- | -------- | -------- | -------- | -------- | -------- |
|-1|-1|    H|H-1|H|+1|
|-1|0|    H|H|H|+1|
|-1|+1|    H-1|H|H|+2|

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

**• For which of the three cases do we need to perform a right-left rotation?**

C = -1

**• For the case where an RL rotation is applied, what are the possible balance factors of the tree after the RL rotation?**

+1 and 0

**• 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 12: Fixing left-heavy trees

**• For which of the three cases do we need to perform a left-right rotation?**

C = +1

**• For the case where an LR rotation is applied, what are the possible balance factors of the tree after that rotation combo?**

+1

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

+1

### Activity 13: Rebalancing the tree
Fix Left-heavy Tree
CODE:
```c=
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;
    }
}
```
PHOTO:
![](https://i.imgur.com/QHQnq71.png)

Fix Right-heavy Tree
CODE:
```c=
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;
    }
}
```
PHOTO:
![](https://i.imgur.com/pto4sZy.png)
#### Big tree 
PHOTO:
![](https://i.imgur.com/SlLcZYf.png)


## Look back

### What we've learnt

Fill in...

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



