चौड़ाई-प्रथम खोज तरीके में सामान्य वृक्ष ट्रैवर्सल (अनंत)

मैं अभी भी सोच रहा हूं, लेकिन पेड़ को पार करने से कहीं ज्यादा तेज हर संभावित स्थिति के लिए एक स्थिति_आईडी होगी। यदि आप एक निश्चित स्तर के एक पूर्ण पेड़ को देखते हैं तो आप देखेंगे कि मेरा क्या मतलब है - आपका उदाहरण ऐसा दिखता है।

स्थिति और स्थिति_आईडी के बीच संबंध सरल इंट अंकगणित (div और modulo) के साथ कुछ हैं।

एक सबट्री में सभी नोड्स उन गुणों में से कुछ को साझा करते हैं - उदाहरण के लिए नोड 4 के प्रत्यक्ष सबनोड्स (दूसरी पंक्ति में तीसरा नोड) संख्याएं हैं

1 + 5 + (3-1)*5 +   1 
1 + 5 + (3-1)*5 +   2
1 + 5 + (3-1)*5 +   3
1 + 5 + (3-1)*5 +   4
1 + 5 + (3-1)*5 +   5

इसलिए यदि आप प्रत्येक नोड में उस स्थिति संख्या को प्रबंधित करते हैं, तो आपको अभी भी स्तरों को लूप में पार करना होगा, लेकिन नोड्स को नहीं।

चरण 2:

पंक्ति r में 5^r तत्व हैं (पंक्ति 0 से शुरू)।

हर नोड में रो और कॉलम को स्टोर करें, हर रो में कॉलम 0 से शुरू होता है। तो दूसरी रो 2,3,4,5,6 नहीं बल्कि 1|0, 1|1, 1|2, 1| 3, 1|4.

यदि आपका खोज रूट 1|1 (पंक्ति 1, दूसरा तत्व, आपके "3" नाम के अच्छे पेड़ में है), तो पंक्ति 2 के सभी बच्चों के पास

  col / 5 = 1

पंक्ति 3 के सभी बच्चों के पास

  col / 25 = 1

और इसी तरह।

नोड 2|10 के नीचे का एक स्तर नोड 3|(5*10) टिल 3|(5*11-1) =50 .. 55-1

नीचे दो स्तर नोड 4|(50*5) टिल 4|(55*5-1)

और इसी तरह।

चरण 3

स्यूडोकोड:

getFreeNode($node){
    $rowMax = 100;
    $row   = $node->row + 1;
    $from  = 5 * $node->col;
    $to    = $from + 5;
    while($row <= $rowMax){
        if ($id = query("select id from member " 
            ."where row = $row and col >= $from and col < $bis"
            ." and empty_position > 0"))
        {
            return $id;
        }
        $row++;
        $from *= 5;
        $to *= 5;
    }
}

insertNode($parent, $node){
    $node->row = $parent->row + 1;
    $node->col = 5*$parent->col + (5 - $parent->freeNodeCount);
    $node->parent_id = $parent->member_id
}

कृपया पूछें कि क्या अधिक विवरण की आवश्यकता है।