ExtendedAVLNode's constructor and getSubtreeKeyCount() member function are already implemented and should not be changed. Additional member functions are needed to ensure that subtreeKeyCount remains accurate. Step 4: Implement ExtendedAVLTree and ExtendedAVLNode Each node in an ExtendedAVLTree must have a correct subtreeKeyCount after an insertion or removal operation. Determine which member functions in AVLTree and AVLNode must be overridden in ExtendedAVLTree and Extended AVLNode to keep each node's subtreeKeyCount correct. New functions can be added along with overridden functions, if desired. Hint: Consider an UpdateSubtree KeyCount() member function for the ExtendedAVLNode class. The function requires each child node's subtreeKeyCount to be correct, and updates the node's subtreeKeyCount appropriately. Overridden functions in both ExtendedAVLNode and ExtendedAVLTree can call a node's UpdateSubtreeKeyCount() function as needed. Once determinations are made, complete the implementation of both the ExtendedAVLTree and ExtendedAVLNode classes. Do not implement ExtendedAVLTree's GetNthKey() in this step. GetNthKey() requires correct subtree counts at each node. Step 5: Run tests Tree TestCommand is an abstract base class defined in TreeCommands.h. A TreeTestCommand object is an executable command that operates on a binary search tree. Classes inheriting from TreeTestCommand are also declared in TreeCommands.h: • TreeInsertCommand inserts keys into the tree TreeRemoveCommand removes keys from the tree TreeVerifyKeysCommand verifies the tree's keys using an inorder traversal TreeVerifySubtreeCounts Command verifies that each node in the tree has the expected subtree key count TreeGetNthCommand verifies that GetNthKey() returns an expected value Code in main.cpp contains three automated test cases. Each test executes a vector of TreeTestCommand objects in sequence. The third test includes TreeGetNthCommands and will not pass until the completion of Step 6. The first two tests should pass after completion of step 4. Before proceeding to Step 6, verify that the first two tests in main.cpp pass. Then submit code and ensure that the first two unit tests pass. Step 6: Implement ExtendedAVLTree's GetNthKey() member function GetNthKey() must return the tree's nth-largest key. The parameter n starts at 0 for the smallest key in the tree. Ex: Suppose a tree has keys: 10, 19, 20, 30, 42, 55, 77. Then GetNthKey(0) returns 10, GetNthKey (1) returns 19, ..., GetNthKey (5) returns 55, and GetNthKey(6) returns 77. Implement an algorithm that uses the subtree key counts so that GetNthKey() operates in worst case O(log N) time. Go Files +01 ▷ Run History Tutorial Step 1: Inspect the BSTNode.h and BinarySearchTree.h files Inspect the BSTNode class declaration for a binary search tree node in BSTNode.h. The BSTNode class has private member variables for the key, parent pointer, left child pointer, and right child pointer. Accessor functions exist for each. Inspect the Binary Search Tree class declaration for a binary search tree in BinarySearch Tree.h. The GetNthKey() function is the only pure virtual function that exists. Step 2: Inspect other files related to the inheritance hierarchy Classes AVLNode and AVLTree inherit from BSTNode and BinarySearch Tree, respectively. Each class is implemented in a read-only header file. Classes ExtendedAVLNode and Extended AVLTree are declared, but implementations are incomplete. Both classes must be implemented in this lab. BinarySearch Tree BSTNode AVLTree ExtendedAVLTree AVLNode ExtendedAVLNode Read-only, completed class implementation Incomplete class implementation Step 3: Understand the purpose of the subtreeKeyCount member variable The ExtendedAVLNode class inherits from AVLNode and adds one integer member variable, subtreeKeyCount. Each node's subtree key count is the number of keys in the subtree rooted at that node. Ex: 20 7 Subtree key count

ExtendedAVLNode's constructor and getSubtreeKeyCount() member function are already implemented and should not be changed. Additional member functions are needed to ensure that subtreeKeyCount remains accurate. Step 4: Implement ExtendedAVLTree and ExtendedAVLNode Each node in an ExtendedAVLTree must have a correct subtreeKeyCount after an insertion or removal operation. Determine which member functions in AVLTree and AVLNode must be overridden in ExtendedAVLTree and Extended AVLNode to keep each node's subtreeKeyCount correct. New functions can be added along with overridden functions, if desired. Hint: Consider an UpdateSubtree KeyCount() member function for the ExtendedAVLNode class. The function requires each child node's subtreeKeyCount to be correct, and updates the node's subtreeKeyCount appropriately. Overridden functions in both ExtendedAVLNode and ExtendedAVLTree can call a node's UpdateSubtreeKeyCount() function as needed. Once determinations are made, complete the implementation of both the ExtendedAVLTree and ExtendedAVLNode classes. Do not implement ExtendedAVLTree's GetNthKey() in this step. GetNthKey() requires correct subtree counts at each node. Step 5: Run tests Tree TestCommand is an abstract base class defined in TreeCommands.h. A TreeTestCommand object is an executable command that operates on a binary search tree. Classes inheriting from TreeTestCommand are also declared in TreeCommands.h: • TreeInsertCommand inserts keys into the tree TreeRemoveCommand removes keys from the tree TreeVerifyKeysCommand verifies the tree's keys using an inorder traversal TreeVerifySubtreeCounts Command verifies that each node in the tree has the expected subtree key count TreeGetNthCommand verifies that GetNthKey() returns an expected value Code in main.cpp contains three automated test cases. Each test executes a vector of TreeTestCommand objects in sequence. The third test includes TreeGetNthCommands and will not pass until the completion of Step 6. The first two tests should pass after completion of step 4. Before proceeding to Step 6, verify that the first two tests in main.cpp pass. Then submit code and ensure that the first two unit tests pass. Step 6: Implement ExtendedAVLTree's GetNthKey() member function GetNthKey() must return the tree's nth-largest key. The parameter n starts at 0 for the smallest key in the tree. Ex: Suppose a tree has keys: 10, 19, 20, 30, 42, 55, 77. Then GetNthKey(0) returns 10, GetNthKey (1) returns 19, ..., GetNthKey (5) returns 55, and GetNthKey(6) returns 77. Implement an algorithm that uses the subtree key counts so that GetNthKey() operates in worst case O(log N) time. Go Files +01 ▷ Run History Tutorial Step 1: Inspect the BSTNode.h and BinarySearchTree.h files Inspect the BSTNode class declaration for a binary search tree node in BSTNode.h. The BSTNode class has private member variables for the key, parent pointer, left child pointer, and right child pointer. Accessor functions exist for each. Inspect the Binary Search Tree class declaration for a binary search tree in BinarySearch Tree.h. The GetNthKey() function is the only pure virtual function that exists. Step 2: Inspect other files related to the inheritance hierarchy Classes AVLNode and AVLTree inherit from BSTNode and BinarySearch Tree, respectively. Each class is implemented in a read-only header file. Classes ExtendedAVLNode and Extended AVLTree are declared, but implementations are incomplete. Both classes must be implemented in this lab. BinarySearch Tree BSTNode AVLTree ExtendedAVLTree AVLNode ExtendedAVLNode Read-only, completed class implementation Incomplete class implementation Step 3: Understand the purpose of the subtreeKeyCount member variable The ExtendedAVLNode class inherits from AVLNode and adds one integer member variable, subtreeKeyCount. Each node's subtree key count is the number of keys in the subtree rooted at that node. Ex: 20 7 Subtree key count

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter17: Linked Lists

Section: Chapter Questions

Problem 9PE

See similar textbooks

Related questions

Question

#ifndef EXTENDEDAVLNODE_H

#define EXTENDEDAVLNODE_H

#include "AVLNode.h"

#include <iostream>

class ExtendedAVLNode : public AVLNode {

private:

int subtreeKeyCount;

public:

ExtendedAVLNode(int nodeKey) : AVLNode(nodeKey) {

subtreeKeyCount = 1;

std::cout << "Node created with key: " << nodeKey << std::endl;

}

int GetSubtreeKeyCount() {

return subtreeKeyCount;

}

void UpdateSubtreeKeyCount() {

int leftCount = GetLeft() ? ((ExtendedAVLNode*)GetLeft())->GetSubtreeKeyCount() : 0;

int rightCount = GetRight() ? ((ExtendedAVLNode*)GetRight())->GetSubtreeKeyCount() : 0;

subtreeKeyCount = 1 + leftCount + rightCount;

std::cout << "Updated subtreeKeyCount for node " << GetKey() << ": " << subtreeKeyCount << std::endl;

}

virtual void SetLeft(BSTNode* newLeftChild) override {

std::cout << "Setting left child for node " << GetKey() << std::endl;

AVLNode::SetLeft(newLeftChild);

UpdateSubtreeKeyCount();

std::cout << "Set left child for node " << GetKey() << std::endl;

}

virtual void SetRight(BSTNode* newRightChild) override {

std::cout << "Setting right child for node " << GetKey() << std::endl;

AVLNode::SetRight(newRightChild);

UpdateSubtreeKeyCount();

std::cout << "Set right child for node " << GetKey() << std::endl;

}

};

#endif // EXTENDEDAVLNODE_

#ifndef EXTENDEDAVLTREE_H

#define EXTENDEDAVLTREE_H

#include "AVLTree.h"

#include "ExtendedAVLNode.h"

#include <iostream>

class ExtendedAVLTree : public AVLTree {

protected:

virtual BSTNode* MakeNewNode(int key) override {

std::cout << "Creating new node with key: " << key << std::endl;

return new ExtendedAVLNode(key);

}

virtual void InsertNode(BSTNode* node) override {

std::cout << "Inserting node with key: " << node->GetKey() << std::endl;

AVLTree::InsertNode(node);

UpdateSubtreeKeyCounts((ExtendedAVLNode*)node);

}

virtual bool RemoveNode(BSTNode* nodeToRemove) override {

std::cout << "Removing node with key: " << nodeToRemove->GetKey() << std::endl;

bool result = AVLTree::RemoveNode(nodeToRemove);

if (result) {

ExtendedAVLNode* parent = (ExtendedAVLNode*)nodeToRemove->GetParent();

if (parent) {

std::cout << "Updating subtree key counts starting from parent node with key: " << parent->GetKey() << std::endl;

UpdateSubtreeKeyCounts(parent);

} else {

std::cout << "Removed node was the root." << std::endl;

}

return result;

}

void UpdateSubtreeKeyCounts(ExtendedAVLNode* node) {

while (node) {

node->UpdateSubtreeKeyCount();

node = (ExtendedAVLNode*)node->GetParent();

}

public:

virtual int GetNthKey(int n) override {

std::cout << "Getting the " << n << "th key" << std::endl;

return GetNthKeyHelper((ExtendedAVLNode*)root, n);

}

private:

int GetNthKeyHelper(ExtendedAVLNode* node, int n) {

if (!node) throw std::out_of_range("Index out of range");

int leftCount = node->GetLeft() ? ((ExtendedAVLNode*)node->GetLeft())->GetSubtreeKeyCount() : 0;

if (n < leftCount) {

return GetNthKeyHelper((ExtendedAVLNode*)node->GetLeft(), n);

} else if (n == leftCount) {

return node->GetKey();

} else {

return GetNthKeyHelper((ExtendedAVLNode*)node->GetRight(), n - leftCount - 1);

}

};

#endif

ExtendedAVLNode's constructor and getSubtreeKeyCount() member function are already implemented and should not be changed.
Additional member functions are needed to ensure that subtreeKeyCount remains accurate.
Step 4: Implement ExtendedAVLTree and ExtendedAVLNode
Each node in an ExtendedAVLTree must have a correct subtreeKeyCount after an insertion or removal operation. Determine which
member functions in AVLTree and AVLNode must be overridden in ExtendedAVLTree and Extended AVLNode to keep each node's
subtreeKeyCount correct. New functions can be added along with overridden functions, if desired.
Hint: Consider an UpdateSubtree KeyCount() member function for the ExtendedAVLNode class. The function requires each child node's
subtreeKeyCount to be correct, and updates the node's subtreeKeyCount appropriately. Overridden functions in both ExtendedAVLNode
and ExtendedAVLTree can call a node's UpdateSubtreeKeyCount() function as needed.
Once determinations are made, complete the implementation of both the ExtendedAVLTree and ExtendedAVLNode classes. Do not
implement ExtendedAVLTree's GetNthKey() in this step. GetNthKey() requires correct subtree counts at each node.
Step 5: Run tests
Tree TestCommand is an abstract base class defined in TreeCommands.h. A TreeTestCommand object is an executable command that
operates on a binary search tree. Classes inheriting from TreeTestCommand are also declared in TreeCommands.h:
•
TreeInsertCommand inserts keys into the tree
TreeRemoveCommand removes keys from the tree
TreeVerifyKeysCommand verifies the tree's keys using an inorder traversal
TreeVerifySubtreeCounts Command verifies that each node in the tree has the expected subtree key count
TreeGetNthCommand verifies that GetNthKey() returns an expected value
Code in main.cpp contains three automated test cases. Each test executes a vector of TreeTestCommand objects in sequence. The
third test includes TreeGetNthCommands and will not pass until the completion of Step 6. The first two tests should pass after
completion of step 4.
Before proceeding to Step 6, verify that the first two tests in main.cpp pass. Then submit code and ensure that the first two unit tests
pass.
Step 6: Implement ExtendedAVLTree's GetNthKey() member function
GetNthKey() must return the tree's nth-largest key. The parameter n starts at 0 for the smallest key in the tree. Ex: Suppose a tree has
keys: 10, 19, 20, 30, 42, 55, 77. Then GetNthKey(0) returns 10, GetNthKey (1) returns 19, ..., GetNthKey (5) returns 55,
and GetNthKey(6) returns 77.
Implement an algorithm that uses the subtree key counts so that GetNthKey() operates in worst case O(log N) time.
Go Files
+01
▷ Run
History Tutorial

Step 1: Inspect the BSTNode.h and BinarySearchTree.h files
Inspect the BSTNode class declaration for a binary search tree node in BSTNode.h. The BSTNode class has private member variables
for the key, parent pointer, left child pointer, and right child pointer. Accessor functions exist for each.
Inspect the Binary Search Tree class declaration for a binary search tree in BinarySearch Tree.h. The GetNthKey() function is the only pure
virtual function that exists.
Step 2: Inspect other files related to the inheritance hierarchy
Classes AVLNode and AVLTree inherit from BSTNode and BinarySearch Tree, respectively. Each class is implemented in a read-only
header file.
Classes ExtendedAVLNode and Extended AVLTree are declared, but implementations are incomplete. Both classes must be
implemented in this lab.
BinarySearch Tree
BSTNode
AVLTree
ExtendedAVLTree
AVLNode
ExtendedAVLNode
Read-only, completed class implementation
Incomplete class implementation
Step 3: Understand the purpose of the subtreeKeyCount member variable
The ExtendedAVLNode class inherits from AVLNode and adds one integer member variable, subtreeKeyCount. Each node's subtree key
count is the number of keys in the subtree rooted at that node. Ex:
20
7
Subtree key count

Expert Solution

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here