Aranıyor: In-al ikili ağaç çıkış yönteminin Tekrarlama Formula

Question

Bu java yönteminin nüks formül

void printInorder(Node<T> v) { 
    if(v != null) { 
     printInorder(v.getLeft()); 
     System.out.println(v.getData()); 
     printInorder(v.getRight()); 
    } 
} 

Bazı kriterler arayan bir reçel biraz belada:

• onun tam bir ikili ağaç
• ağaç knot ve O (n) bir karmaşıklık n sahiptir

(her iç düğüm her yaprak aynı derinliğe sahiptir, 2 çocuğu var)

n knots ile ağacın depth h ile ilgili yineleme formülünü bulmalıyım ve bir ek bonus olarak, O (n) 'ye giden açık formülü tahmin etmeliyim.

Şimdi, bu bende ne olduğunu:

d = depth of the tree 
c = constant runtime for execution of the method itself 
d = 1: T(n) = c 
d = 3: T(n) = T(d=1) + T(d=2) + T(d=3) + c 

Ben zorluklar daha da bu parçalayarak yaşıyorum kendim için bir şeyler açıklığa kavuşturmak için örnek d = 3 kullandı. Benim varsayımım bile doğru mu?

---

Düzenleme: şeylerin

[x] = { x in real numbers : max([x]) <= x }, [x] rounded down to next full number 
d = 1: T(d) = 1 
d > 1: T(d) = 2^(h-1) * T(n/(2^(h-1))) 

1: T(h) = T(i = 0) + T(i = 1) + ... T(i = h-1) 
2: T(h) <= (2^(0-1) + n/(2^(0-1))) + (2^(1-1) + n/(2^(1-1))) + ... + (2^(h-2) + n/(2^(h-2))) 
3: T(h) = n + n + ... + n 
4: T(h) = (h-1)n 
5: T(h) = O(n) 

ağacının derinliği her seviye tam 2^(h-1) düğümler içerdiğinden

de Sonraki girişimi, 4. satırdaki h faktörü nedeniyle göz ardı edilebilir n son sonuç için daha uygundur.

Answer 1

T (n) = T (n/2) + T (n/2) + 1

• Seviye 0 1 çalışma vardır.

• Düzey 1'de 2 işlem bulunmaktadır.

• Düzey 2'de 4 işlem bulunmaktadır.

• Seviye k, 2^k işlemlere sahiptir.

• Ağacın derinliği lgn.

1 + 2 + ... + 2^lgn =
2^0 + 2^1 + 2^2 + ... + 2^lgn =
(2^(lgn + 1) -1)/(2-1) = 2 * 2^lgn =
2n.

Answer 2

Burada bunlar da bu yerine üs olarak temsil edilmesi için bir yineleme ilişki sağlar Pürüzsüzlük kural (Levitin, Algoritma tasarımı & analizi, 2. Baskı., 481-82) kullanılarak alternatif bir yaklaşım.

Her iki yaklaşım - ileri veya geri ikame - Bu sorun için uygundur. Sindirimi kolaylaştırmak için birçok durumda geriye doğru ikame buluyorum.