LAB: AVL tree Nth largest operation

Suoritettu Julkaistu 3 kuukautta sitten Maksettu toimituksen yhteydessä
Suoritettu Maksettu toimituksen yhteydessä

I am looking for a skilled programmer to implement the AVL tree Nth largest operation in C++. This operation aims to find the Nth largest element in the AVL tree.

Skills and Experience:

- Proficiency in C++

- Strong understanding of AVL trees and their operations

- Experience with implementing algorithms for finding the Nth largest element in a data structure

Additional Information:

Step 1: Inspect the BSTNode.h and BinarySearchTree.h files

Inspect the BSTNode class declaration for a binary search tree node in BSTNode.h. Access BSTNode.h by clicking on the orange arrow next to [login to view URL] at the top of the coding window. 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 BinarySearchTree class declaration for a binary search tree node in BinarySearchTree.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 BinarySearchTree, respectively. Each class is implemented in a read only header file.

Classes ExtendedAVLNode and ExtendedAVLTree are declared, but implementations are incomplete. Both classes must be implemented in this [login to view URL] 3: Understand the purpose of the subtreeKeyCount 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 nodeExtendedAVLNode's constructor and GetSubtreeKeyCount() member functions 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 ExtendedAVLNode to keep each node's subtreeKeyCount correct. New functions can be added along with overridden functions, if desired.

Hint: Consider an UpdateSubtreeKeyCount() 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 in develop mode and submit mode

TreeTestCommand 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

TreeVerifySubtreeCountsCommand verifies that each node in the tree has the expected subtree key count

TreeGetNthCommand verifies that GetNthKey() returns an expected value

Code in [login to view URL] 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, run code in develop mode and ensure that the first two tests in [login to view URL] pass. Then submit code and ensure that the first two unit tests pass.

Step 6: Implement ExtendedAVLTree's GetNthKey() member function (worst case O(log n))

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.

Determine an algorithm that uses the subtree key counts so that GetNthKey() operates in worst case O(log n) time.

C++ -ohjelmointi C-ohjelmointi C# -ohjelmointi Java Tietojärjestelmäarkkitehtuuri

Projektin tunnus: #37490288

Tietoa projektista

8 ehdotusta Etäprojekti Aktiivinen 3 kuukautta sitten

Myönnetty käyttäjälle:


Hello there, I see that I can do it as required and on time with high quality. I am data structure and algorithm expert. Regards,

$100 USD 7 päivässä
(92 Arvostelua)

8 freelanceria on tarjonnut keskimäärin $133 tähän työhön


Hello, there. My Name is John, and I am an expert of developing algorithm. I am very familiar with C|C++ language. I am very interested in your project. I am sure I can finish your project on time perfectly. I am looki Lisää

$140 USD 7 päivässä
(2 arvostelua)

Hi I have just read your specification with deep concern and interest. I am an expert in algorithm design and analysis with skillful C/C++/Java/Python. I am sure that I can deliver a good product to you within timeli Lisää

$100 USD 1 päivässä
(1 arvostelu)

Hello, I'm Jeremy and I am a developer with extensive experience in the field of computer security, app development, deep learning, mT4/MT5 programming, website design and development, game design and crypto recovery. Lisää

$140 USD 5 päivässä
(0 arvostelua)

Hi Greetings! We are team of software developers. We have developers working on almost all the technologies. We will assign you a project manager who will assist you during entire process of project completion. We wil Lisää

$250 USD 5 päivässä
(0 arvostelua)

Hello, We have extensive knowledge in C++ STL, iterators, and standard containers along with internal representations of RB tree, linked lists, binary tree and related areas. We can help you once you confirm the dea Lisää

$130 USD 7 päivässä
(1 arvostelu)