最快葉樹搜索

說我有一個樹實現像這樣（簡化）：最快葉樹搜索

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

，如果我需要它的屬性或名稱獲取特定的節點，我需要通過每一個子節點環從根源上找到它？或者有更快的搜索算法，還是更快/更好的樹實現？說，我需要通過它的類和id屬性找到一個節點，就像我需要應用CSS規則或什麼的時候一樣。

來源

2016-03-07 calcyss

您可以擁有另一個散列映射，將具有特定值的屬性映射到一組節點。查找會更快，這取決於樹中有多少葉子。 – marcadian

在你目前的草案我認爲唯一可能的方式找到一個Node與特定name，id，class任何其他數據是遍歷樹看着每節點。時間複雜度爲O（n節點）。

您可能會對二叉搜索樹感興趣，它允許您在O（log（nNodes））中執行搜索操作，它的速度更快！但是，當您添加/刪除節點時，他們需要一些額外的努力才能保持有效。此外，保持樹平衡是重要的，這對於O（log（nNodes））時間的主要要求。

編輯1

我熟悉CSS語法。爲了滿足所有的CSS要求，在樹上實現是很複雜的。這裏確實二叉搜索樹不能代表一棵DOM樹。 DOM樹應該由節點，其子節點的引用以及父節點的可能引用來表示。例如，二叉查找樹可以存儲對這些節點的引用，並且成功地爲id提供搜索查詢。但是，如果任何節點被刪除/添加/ ID更改二進制搜索樹應該作出相應的反應。

來源

2016-03-07 20:15:08

什麼是二叉樹的排序鍵？ – Amit

但是，這不會工作的DOM樹，會嗎？因爲這些可以有多個孩子 – calcyss

只是爲了查找 - 預先掃描樹（加載時間），並將指針指向適當hashmaps節點是一個好主意？所以我可以做一個快速查找，並且不必每次遍歷樹？ – calcyss

如果沒有定義節點可以/不可以定義的規則，則必須掃描所有節點，直到找到匹配。

在算法中沒有神奇的猜測。

來源

2016-03-07 20:11:48 Amit

最快葉樹搜索

回答

相關問題