最快叶树搜索

Question

假设我有这样的树实现(简化)：

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

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

Answer 1

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

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

编辑1

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

Answer 2

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

算法中没有神奇的猜测。