実現したいこと
ExtendedRedBlackTree.hとExtendedRBTNode.hに変更を加えてプログラムを完成させたい
問題文
ソースコード
問題で与えられているそれぞれのソースコードは、以下のURLにまとめておきましたので、ダウンロードできます。
ソースコード
問題を解くために直すprogram
ExtendedRBTNode.h
#ifndef EXTENDEDRBTNODE_H #define EXTENDEDRBTNODE_H #include "RBTNode.h" class ExtendedRBTNode : public RBTNode { private: int subtreeKeyCount; public: ExtendedRBTNode(int nodeKey) : RBTNode(nodeKey) { subtreeKeyCount = 1; } virtual int GetSubtreeKeyCount() override { return subtreeKeyCount; } // Your code here }; #endif
ExtendedRedBlackTree.h
#ifndef EXTENDEDREDBLACKTREE_H #define EXTENDEDREDBLACKTREE_H #include "RedBlackTree.h" #include "ExtendedRBTNode.h" class ExtendedRedBlackTree : public RedBlackTree { protected: // Each node in an ExtendedRedBlackTree is an ExtendedRBTNode virtual BSTNode* MakeNewNode(int key) override { return new ExtendedRBTNode(key); } // Your code here public: virtual int GetNthKey(int n) override { // Your code here (remove placeholder line below) return 0; } }; #endif
自分で変更して試したソースコード
ExtendedRedBlackTree.h
#ifndef EXTENDEDREDBLACKTREE_H #define EXTENDEDREDBLACKTREE_H #include "RedBlackTree.h" #include "ExtendedRBTNode.h" class ExtendedRedBlackTree : public RedBlackTree { protected: // Each node in an ExtendedRedBlackTree is an ExtendedRBTNode virtual BSTNode* MakeNewNode(int key) override { return new ExtendedRBTNode(key); } // Your code here // Override the InsertNode function virtual void InsertNode(BSTNode* node) override { BinarySearchTree::InsertNode(node); node = (ExtendedRBTNode*)node->GetParent(); while (node) { RedBlackTree::InsertionBalance((ExtendedRBTNode*)node); static_cast<ExtendedRBTNode*>(node)->UpdateSubtreeKeyCount((ExtendedRBTNode*)node); node = (ExtendedRBTNode*)node->GetParent(); } } public: virtual int GetNthKey(int n) override { // Your code here (remove placeholder line below) int Index = 0; ExtendedRBTNode* current = static_cast<ExtendedRBTNode*>(GetRoot()); while (current != nullptr) { int leftCount = current->GetLeft() == nullptr ? 0 : static_cast<ExtendedRBTNode*>(current->GetLeft())->GetSubtreeKeyCount(); if (Index + leftCount == n) { return current->GetKey(); } if (Index + leftCount < n) { Index += leftCount + 1; current = static_cast<ExtendedRBTNode*>(current->GetRight()); } else { current = static_cast<ExtendedRBTNode*>(current->GetLeft()); } } return -1; } };
ExtendedRBTNode.h
#ifndef EXTENDEDRBTNODE_H #define EXTENDEDRBTNODE_H #include "RBTNode.h" class ExtendedRBTNode : public RBTNode { private: int subtreeKeyCount; public: ExtendedRBTNode(int nodeKey) : RBTNode(nodeKey) { subtreeKeyCount = 1; } virtual int GetSubtreeKeyCount() override { return subtreeKeyCount; } // Your code here virtual void SetLeft(BSTNode* newLeftChild) override { RBTNode::SetLeft(newLeftChild); UpdateSubtreeKeyCount(newLeftChild); } virtual void SetRight(BSTNode* newRightChild) override { RBTNode::SetRight(newRightChild); UpdateSubtreeKeyCount(newRightChild); } virtual void UpdateSubtreeKeyCount(BSTNode* node) { int count = 1; if (GetLeft() != NULL) { count += ((ExtendedRBTNode*)GetLeft())->GetSubtreeKeyCount(); } if (GetRight() != NULL) { count += ((ExtendedRBTNode*)GetRight())->GetSubtreeKeyCount(); } subtreeKeyCount = count; } }; #endif
発生している問題・エラーメッセージの一例
Inserting keys: 21, 64, 32, 91, 87, 66, 15, 88, 58, 20, 67, 82, 19, 44, 51 PASS: Inorder key verification Expected: { 15, 19, 20, 21, 32, 44, 51, 58, 64, 66, 67, 82, 87, 88, 91 } Actual: { 15, 19, 20, 21, 32, 44, 51, 58, 64, 66, 67, 82, 87, 88, 91 } FAIL: Node with key 15 has a subtree key count of 3, but the expected subtree key count is 2. PASS: Node with key 19 has a subtree key count of 1 FAIL: Node with key 20 has a subtree key count of 2, but the expected subtree key count is 4. FAIL: Node with key 21 has a subtree key count of 4, but the expected subtree key count is 1. FAIL: Node with key 32 has a subtree key count of 9, but the expected subtree key count is 8. FAIL: Node with key 44 has a subtree key count of 2, but the expected subtree key count is 1. FAIL: Node with key 51 has a subtree key count of 1, but the expected subtree key count is 3. FAIL: Node with key 58 has a subtree key count of 4, but the expected subtree key count is 1. FAIL: Node with key 64 has a subtree key count of 1, but the expected subtree key count is 15. FAIL: Node with key 66 has a subtree key count of 15, but the expected subtree key count is 1. FAIL: Node with key 67 has a subtree key count of 2, but the expected subtree key count is 3. PASS: Node with key 82 has a subtree key count of 1 FAIL: Node with key 87 has a subtree key count of 5, but the expected subtree key count is 6. PASS: Node with key 88 has a subtree key count of 1 PASS: Node with key 91 has a subtree key count of 2
コメント
自分でも試してみましたが、エラーが起こって問題が解けません。わかる方がいましたら、変更を加えていただいたソースコード2つを送ってくださると幸いです。

回答1件
あなたの回答
tips
プレビュー