In our study of binary search trees so far, we’ve looked at how to build and traverse one, but what happens when the tree becomes imbalanced? This is a situation we try to avoid. The more imbalanced the tree, the more our search approaches O(n) comparisons. This week we will look at types of self-balancing trees, such as AVL and 2-3 trees, which perform various operations on BSTs to maintain balance.
Assignment
AVL trees are balanced trees that track a balance factor (BF) in each node. This factor is calculated as (B – A), where B is the height of the right subtree and A is the height of the left subtree. The AVL algorithm performs rotations whenever this factor gets “out of whack” by more than 1 (that is, B – A is greater than 1 or less than -1), during an insert or delete operation.
Write a program that, given a series of integers to add to a BST, detects the point where an imbalance occurs in the tree.
Input
Use the file input.txt posted in this module, which contains 4 test cases (40 numbers total, one per line).
Requirements
- A starter file with a simple framework for reading the input is here: balance_main.cpp or you can start with any BST code you choose (we’ve studied a few so far and there is at least one posted in Canvas).
- The program should read a batch of 10 integers, do the inserts, and output the point where the insert causes an imbalance (where the BF for that node becomes greater than 1 or less than -1). The output should include both the value of the node where the imbalance occurs and which subtree (left or right).
- We’re only looking at inserts in this assignment — no need to handle deletes. No classes or templates are necessary.
- Your program must accept batches of 10 integers from a file and build a tree, until EOF. No programs will be accepted that hard-code outputs, do not read the file, or do not build a BST.
- It is good practice to free all of the dynamic memory allocated for each batch (as the starter file does) but this is optional.
- Duplicate values should be ignored.
Example Output
You should get the following output for the included test file.
Read 10 nodes.
Imbalance detected at node 71, left subtree.
Read 10 nodes.
Imbalance detected at node 9, right subtree.
Read 10 nodes.
Imbalance detected at node 96, left subtree.
Read 10 nodes.
Imbalance detected at node 97, right subtree.
Done.
input.txt:
71
7
32
38
99
19
82
27
2
85
58
9
59
40
36
2
62
73
3
87
45
96
31
52
40
78
30
66
94
91
44
95
31
52
40
97
30
99
98
7
balance_main.cpp:
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
#define FILENAME “input.txt”
#define N_NODES 10
// A tree node
struct Node {
int val; // The (integer) value
int bf; // Balance factor of this node
Node *left; // Left child pointer
Node *right; // Right child pointer
};
// Insert a node into the tree, balancing if needed.
// *tp is a pointer to the root of the tree (reference variable);
// ‘nv’ is the new (integer) value to add.
// ‘allNodes’ is an array of all of the nodes we’ve allocated, for easy clean-up
// ‘allNodesN’ is the number of nodes set in allNodes
int insertNode(Node *&tp, int nv, Node *allNodes[], int allNodesN) {
Node *newp;
if (tp == 0) {
// Setup our new node
newp = new Node;
newp->val = nv;
newp->bf = 0;
newp->left = 0;
newp->right = 0;
tp = newp;
allNodes[allNodesN] = newp;
return (1);
}
// Ignore existing values
if (nv == tp->val)
return (0);
if (nv < tp->val) {
// Insert into the LEFT subtree
} else {
// Insert into the RIGHT subtree
}
}
int main() {
Node *rootp = 0; // Root of the tree
Node *allNodes[N_NODES]; // Bookkeeping array so we can free everything
string ent; // Input string from file
ifstream infile(FILENAME); // Input file
int nums[N_NODES]; // Input integers
int i, j, status;
while (true) {
// Read a set of insertions
i = 0, j = 0;
rootp = 0;
while (getline(infile, ent)) {
nums[i++] = atoi(ent.c_str());
if (i == N_NODES)
break;
}
if (i != N_NODES)
break;
cout << “Read ” << i << ” nodes.” << endl;
for (; j < N_NODES; j++) {
status = insertNode(rootp, nums[j], allNodes, j);
if (status == -1)
break;
}
if (j == N_NODES) {
cout << “No imbalances detected.” << endl;
}
// Free everything
for (int k = 0; k < j; k++) {
delete allNodes[k];
allNodes[k] = 0;
}
}
cout << “Done.” << endl;
return (0);
}
Jermaine Byrant
Nicole Johnson
OVER
RATING
YEARS
