c++ - 最快的叶树搜索

Question

假设我有一个像这样的树实现(简化):

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

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

Answer 1

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

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

编辑 1

我熟悉 css 语法。在树上实现以满足所有 css 要求非常复杂。这里确实二叉搜索树不能代表 DOM 树。 DOM 树应该由 Node 表示，引用其子节点并可能指向其父节点。二叉搜索树可以存储对这些节点的引用，并通过 id 成功地提供搜索查询。但是，如果任何节点被删除/添加/id 更改，二叉搜索树应该做出相应的 react 。