-1

假设我们有一个 RedBlack-Tree 实现，它由 2 个类组成：

  • Tree- 保存指向Node *root树的指针并定义树上的所有操作（Insert、、Delete等）
  • Node- 一个数据存储，它保存指向Node *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

它相对简单。首先，节点结构：

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 日”吗？还是一个非常高分辨率的时钟？在任何情况下，这些“创建时间”细节都不会影响树。

编辑：等等，你想要一种只有一些节点知道创建时间的树类型吗？或者只是改变树以便所有节点都知道创建时间？我做了 #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 回答