# Week 10 - Self-balancing [Trees]

## Team

Team name: **Group [497441]**
Date: 05/12/2021

Members: Max Thielen

| Role | Name |
| - | - |
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | Max Thielen |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Max Thielen |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Max Thielen |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Max Thielen |

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

The minimum number of levels to a tree with n nodes is calculated by taking the greatest integer less than or equal to log(n) otherwise know as **floor(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?**

The worst case time complexity of a rebalancing binary tree can be represented as **O(log(n))**.

### Activity 2: A naive approach

int height(const bintree_node* node) {
    if (node == nullptr)
        return -1;
    else
        return std::max(height(node->left()), height(node>right())) + 1;
}

* **How many nodes does the function visit?**

The Height function visits all node in the tree is called with the root node.
* **What is the time complexity of the height function give above? Give your answer in Big O notation.**

O(n)

### Activity 3: Remembering tree heights

void bintree_node::update_height() {
    // failed recursive approach
    // if(m_parent!= nullptr) {
    //     m_parent->m_height++;
    //     m_parent->update_height();
    // }
    
    if(m_right == nullptr && m_left == nullptr){
        m_height = 0;
    }
    else if(m_right == nullptr) {
        m_height = std::max(-1, m_left->m_height)+1;
    }
    else if(m_left == nullptr) {
        m_height = std::max(-1, m_right->m_height)+1;
    }
    else {
        m_height = std::max(m_right->m_height, m_left->m_height)+1;
    }
}

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


### Activity 5: Computing the balance factor

int bintree_node::balance() const {
    if(this == nullptr){
        //std::cout<<"pooo ... disgrace"<<'\n';
        return 0;
    }
    else{
        //std::cout << m_value << '\n';
        if (m_right == nullptr && m_left == nullptr) return 0;
        else if (m_right == nullptr) {
            m_left->update_height();
            return (m_left->m_height);
        } else if (m_left == nullptr) {
            m_right->update_height();
            return (m_right->m_height);
        } else if (m_right != nullptr && m_left != nullptr) {
            m_right->update_height();
            m_left->update_height();
            return (m_right->m_height - m_left->m_height);
        } else return 0;
    }
}

### Activity 6: Balancing acts

Assuming Tree (a) was build correctly, Tree (b) is also correct since C>D in Tree (a) however, C is located in the left subtree with D being the root.

Tree ( c) is built correctly as well. Node D and C are correctly swapped, since D is the maximum node in the left subtree. (replacing the root node)

Lastly, Tree (d) is incorrect varient of Tree (a). The only difference from Tree ( c) is that D and A are swapped. This is a illegal switch since A is still less than D however, A is placed as the right left node of D.

### Activity 7: Implement left rotation

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();
}

### Activity 8: Implement right rotation

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();
}

### Activity 9: Left rotations and balance

### Activity 10: Right rotations and balance

### Activity 11: Fixing right-heavy trees using rotation combos
In a right-heavy unbalanced (sub)tree, the (root) node has a balance factor of +2. There are
three cases to consider: the balance factor of the node’s right child can be either -1, 0, or +1
* **For which of the three cases do we need to perform a right-left rotation?**

If the right child has a balance factor of (-1), LR rotation is required to restore the tree's balance.

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

After LR rotation the tree should be perfectly blanced assuming the three was balanced further down before the rotation was applied.
* **For the cases where only a left rotation is applied, what are the possible balance factors of the tree after the left rotation?**

If the right child has a balance factor of (+1), solely rotating left will perfectly blance the tree. Howevere, if the right child has a balance factor of (0), the final balance factor of the tree ends up being (-1).

### Activity 12: Fixing left-heavy trees using rotation combos
The balance factor of the node’s left child can be either -1, 0, or +1, again giving three cases to
consider.
* **For which of the three cases do we need to perform a left-right rotation?**

If the left child has a balance factor of (+1), RL rotation is required to restore the tree's balance.
* **For the case where an LR rotation is applied, what are the possible balance factors of the tree after that rotation combo?**

After RL rotation the tree should be perfectly blanced assuming the three was balanced further down before the rotation was applied.
* **For the cases where only a right rotation is applied, what are the possible balance factors of the tree after the rotation?**

If the left child has a balance factor of (-1), solely rotating right will perfectly blance the tree. Howevere, if the left child has a balance factor of (0), the final balance factor of the tree ends up being (+1).

### Activity 13: Rebalancing the tree

void bintree_node::fix_left_heavy() {
    switch (m_left->balance()) {
        case 0:
            rotate_right();
        case -1:
            rotate_right();
        case +1:
            m_left->rotate_left();
            rotate_right();
            break;
    }
}

void bintree_node::fix_right_heavy() {
    switch (m_right->balance()) {
        case 0:
            rotate_left();
        case +1:
            rotate_left();
        case -1:
            m_right->rotate_right();
            rotate_left();
            break;
    }
}

## Look back

### What we've learnt

Although AVL tree operations are quite complex, the operations are rather logical after working through them and do improve the efficiency of a tree data structure dramaticly.

### What were the surprises

Not in particular.

### What problems we've encountered

How difficult it was to think about tree rotation and balance factors.

### What was or still is unclear

How can a node of a height of H-1?

### How did the group perform?

Frictionless.