最快的叶树搜索

Question

假设我有一个像这样的树实现（简化）：

class Node 
{
public:
    std::string name;
    int attr_1;
    double attr_2;
    unsigned int nChildren;
    Node* Children;
}

如果我需要通过其属性或名称获取特定节点，是否需要从根节点遍历每个子节点以找到它？或者是否有更快的搜索算法，或 faster/better 树实现？说，我需要通过它的 class 和 id 属性找到一个节点，比如当我需要应用 CSS 规则或其他东西时。

Answer 1

如果没有规则定义节点可以/不可以在哪里，则必须扫描所有节点，直到找到匹配项。

算法中没有神奇的猜测。

Answer 2

在您当前的草稿中，我假设找到具有特定 name、id、class 任何其他数据的 Node 的唯一可能方法是遍历查看每个节点的树。时间复杂度为 O(nNodes).

您可能对二叉搜索树感兴趣，它允许您在 O(log(nNodes)) 中执行搜索操作，速度更快！但是，当您 add/remove 节点时，它们需要一些额外的努力才能保持有效。保持树平衡也很重要，这是 O(log(nNodes)) 时间的主要要求。

编辑 1

我熟悉 css 语法。在树上实现以满足所有 css 要求非常复杂。这里确实二叉搜索树不能表示 DOM 树。 DOM 树应该由 Node 表示，引用其子项并可能引用其父项。二叉搜索树可以存储对这些节点的引用，并通过 id 成功地提供搜索查询。但是如果任何节点 removed/added/id 发生变化，二叉搜索树应该做出相应的反应。

最快的叶树搜索

Fastest leaf tree search

c++

tree