-1

2 つのクラスで構成される RedBlack-Tree 実装があるとします。

  • Tree- ツリーの へのポインタを保持しNode *root、ツリーに対するすべての操作を定義します ( Insert、Deleteなど)。
  • NodeNode *parent- 、Node *left、Node *rightノードおよびへのポインタを保持するデータ ストレージstd::string key。

にはTree::Insert()次の実装があります。

void Tree::Insert(const std::string &key)
{
    Node *z = new Node(key);
    // adding node logic
}

ここでのタスク: すべてのノードはその作成時刻を保存する必要があります。

制限: ベース ツリーの実装は、できるだけ変更を少なくする必要があり、特定の拡張機能の詳細を含める必要があります (したがって、作成時のプロパティについて何も認識しないようにする必要があります)。

私の考え:プロパティの拡張NodeWithTime : Nodeと追加。unsigned int creation_time

私が立ち往生している場所: ノードを今どのようにインスタンス化しますか?

何か提案はありますか？

PS: これは宿題でも仕事でもありません。C++ とデータ構造を学んでいるだけです。

4

1 に答える 1

1

比較的単純です。まず、 Node 構造体:

template<typename T> struct Node {
    Node(T t) : value(std::move(t)), time(RightNow()) {}
    T value;
    TimeType time;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
};

クイックヘルパーmake_unique:

template<typename T, typename... Args> std::unique_ptr<T> make_unique(Args&&... args) {
    return std::unique_ptr<T>(new T(std::forward<Args>(args...)));
}
template<typename T> void Tree<T>::Insert(T key) {
    auto z = make_unique<Node<T>>(std::move(key));
    // insert
}

最初に、私はあなたのくだらない問題を修正newし、deleteそれをスマート ポインターに置き換えました。それから、あなたのツリーもテンプレートにしました。次に、移動のみのタイプで使用できるように、あなたconst T&を aに交換しました。T

次に、Time フィールドを追加し、コンストラクターで RightNow() を呼び出しました。使用する正確な TimeType と RightNow() は、ニーズと、「作成時」とは正確に何を意味するかによって異なります。「2013 年 7 月 6 日」のことですか？それとも非常に高解像度の時計ですか? いずれにせよ、これらの「作成時間」の詳細はツリーには影響しません。

編集: ちょっと待って、ノードの一部だけが作成時間を知っている 1 つのツリー タイプが必要ですか? または、すべてのノードが作成時間を知るようにツリーを変更するだけですか? 私は #2 を行いましたが、#1 については、Node.js から単純に継承することができます。つまり、

template<typename T> struct Node {
    Node(T t) : value(std::move(t)) {}
    T value;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
};
template<typename T> struct NodeWithTime : Node<T> {
    TimeType time;
    NodeWithTime(T t) : Node(std::move(t)), time(RightNow()) {}
};
template<typename T> void Tree<T>::insert(T t) {
    std::unique_ptr<Node> nodeptr;
    if (IWantToStoreCreationTime)
        nodeptr = make_unique<NodeWithTime<T>>(std::move(t));
    else
        nodeptr = make_unique<Node>(std::move(t));
    // insert
}
于 2013-07-06T12:20:35.447 に答える