1. # Week 9 - Binary search trees
## Team
Team name: groep 5
Date: 28-04-2021
Members
Anton Vorderman
Nian Luisman
Thom Kistemaker
| 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
### Activity 1: Maintaining order in Arrays and Linked Lists - reprise
|time complexity|Array|Linked List|
|---------|---------|--------|
|**value insertion**|O(n)|O(1)|
|**value removal**|O(n)|O(1)|
|**membership testing**|O(1)|O(n)|
### Activity 2: Recognizing BSTs
Boom A klopt niet. 71 staat aan de kant van "groter dan 72"
Boom B klopt niet. 84 is niet groter dan 85.
Boom C klopt! :D
### Activity 3: Building a BST
```cpp=
bintree_node root {7,
new bintree_node {3,
new bintree_node {2},
new bintree_node {5}},
new bintree_node {11}};
bintree_node root {7,
new bintree_node {5,
new bintree_node{3,
new bintree_node {2}, nullptr}, nullptr},
new bintree_node {11}};
bintree_node root {2,nullptr,
new bintree_node{3, nullptr,
new bintree_node{5, nullptr,
new bintree_node{7, nullptr,
new bintree_node{11}}}}};
```
### Activity 4: Searching for values
```cpp=
if (this->m_value == value){
return this;
}
else if(value > this->value() && this->m_right != nullptr){
this->m_right->find(value);
}
else if(value < this->value() && this->m_left != nullptr){
this->m_left->find(value);
}
else{
return nullptr;
}
```
### Activity 5: Inserting values
```cpp=
if(this->m_value == value){
return nullptr;
}
else if(this->m_value > value && this->m_left != nullptr){
this->m_left->insert(value);
}
else if(this->m_value < value && this->m_right != nullptr){
this->m_right->insert(value);
}
else {
if(value < this->m_value){
return this->m_left = new bintree_node {value, this};
}
else{
return this->m_right = new bintree_node {value, this};
}
}
return nullptr;
}
```
### Activity 6: Properties of the minimum value
1. Nee, als de linker subtree een minimum waarde heeft die groter is dan de rechter subtree minimum waarde, is een van de 2 waarden onjuist geplaatst in de tree.
2. Nee, de linker subtree heeft een kleinere waarde als node t.o.v. de bovenliggende node, waardoor de minimum waarde kleiner wordt.
3. Kies altijd de linker node. Zodra er geen linker node is gevonden, is de kleinste waarde bereikt.
### Activity 7: Finding the minimum value
```cpp=
if(this->m_left != nullptr){
this->m_left->minimum();
}
else {
return *this;
}
```
### Activity 8: Removing leafs
```cpp=
if (m_left == nullptr && m_right == nullptr) {
if(this->m_value > this->m_parent->m_value) {
this->m_parent->m_left = nullptr;
}
else{
this->m_parent->m_right = nullptr;
}
this->m_parent = nullptr;
return this;
```
### Activity 9: Removing nodes that have one child
```cpp=
else if (m_left == nullptr) {
if(this->m_value > this->m_parent->m_value) {
this->m_parent->m_left = this->m_right;
}
else{
this->m_parent->m_right = this->m_right;
}
this->m_right->m_parent = this->m_parent;
return this;
} else if (m_right == nullptr) {
if(this->m_value > this->m_parent->m_value) {
this->m_parent->m_left = this->m_left;
}
else{
this->m_parent->m_right = this->m_left;
}
this->m_left->m_parent = this->m_parent;
return this;
}
```
### Activity 10: Moving values around
1. Omdat F de kleinste waarde is in de rechter subtree `(F <= E, F <= D)`, zou deze in de root node terecht kunnen komen aangezien F >= A. B is de grootste waarde in de linker subtree `(B >= A, B >= C)`, dus ook B zou in de root node kunnen worden gezet.
2. E is de grootste waarde in de linker subtree, dus deze zou in de root node plaats kunnen nemen. G is de kleinste waarde in de rechter subtree, dus deze is ook geschikt voor vervangend root node.
### Activity 11: Removing *full* nodes
### Activity 12: Performance analysis
insertion, O(log(n))
membership testing, O(log(n))
removal, O(1)
### Activity 13: Restoring balance (optional)
## 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?
Google Drive
Gist
Clipboard
Sign in with Wallet
