質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.44%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

2回答

714閲覧

Red-black tree の問題 デバックエラーになる (C++)

taka012

総合スコア1

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2023/03/27 23:04

実現したいこと

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つを送ってくださると幸いです。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

taka012

2023/03/30 02:21

virtual void InsertNode(BSTNode* node) override はできたみたいです。 RemoveNodeのoverrideの仕方でFAILが起こってるのでやり方を教えていただけると助かります。
guest

回答2

0

どうやって解決したんですか?私も同じ問題を抱えています。

投稿2023/10/13 21:22

happycc

総合スコア2

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

自己解決

自分で解決しました。

投稿2023/04/02 06:00

taka012

総合スコア1

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.44%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問