Page 43 - MATINF Nr. 1
P. 43

Optimalitatea algoritmului de c˘autare binar˘a                                                 43



            penultimul nivel, deci x are ca descendent , i dou˘a noduri externe y s , i z, situate pe ultimul nivel.
            Fie
                                      0
                                    T = T \ {y, z} = (V \ {y, z}, F \ {[x, y], [x, z]})
                                                                                          0
            arborele obt , inut din T prin eliminarea nodurilor externe y s , i z. Evident, T este arbore binar
                         0
                                                                                      0
                                              0
            strict s , i I(T ) = I(T) \ {x}, E(T ) = E(T) \ {y, z} ∪ {x}, deci card(I(T )) = card(I(T)) − 1 =
                                                                                                     0
                             0
            n − 1, card(E(T )) = card(E(T)) − 1. Conform ipotezei de induct , ie, aplicat˘a pentru T , avem
                                                                              0
                                     0
                      0
            card(E(T )) = card(I(T )) + 1 = n, deci card(E(T)) = card(E(T )) + 1 = n + 1, adic˘a arborele
            T are n + 1 noduri externe. Demonstrat , ia prin induct , ie este ˆıncheiat˘a.
            Propozit , ia 3. Pentru orice arbore binar strict T cu n noduri interne, n ∈ N, avem
                                             X               X
                                                  D T (v) =      D T (v) + 2n.
                                            v∈E(T)         v∈I(T)
            Demonstrat¸ie. Demonstr˘am egalitatea din enunt , prin induct , ie dup˘a n.

                Pentru n = 0 este evident c˘a arborele T este format doar din nodul r˘ad˘acin˘a r, E(T) = {r},
            I(T) = Ø,     P   D T (v) = D T (r) = 0,   P   D T (v) + 2n = 0 + 2 · 0 = 0, deci egalitatea din
                        v∈E(T)                       v∈I(T)
            enunt , este verificat˘a.

                Presupunem egalitatea adev˘arat˘a pentru n − 1 s , i o demonstr˘am pentru n, n ≥ 1. Fie
            T = (V, F) un arbore binar strict cu n noduri interne. Fie x un nod intern al lui T situat pe
            penultimul nivel, deci x are ca descendent , i dou˘a noduri externe y s , i z, situate pe ultimul nivel.
                                                        0
            Evident, D T (y) = D T (z) = 1+D T (x). Fie T = T \{y, z} = (V \{y, z}, F \{[x, y], [x, z]}) arborele
                                                                                  0
            obt , inut din T prin eliminarea nodurilor externe y s , i z. Evident, T r˘amˆane tot arbore binar
                        0                     0                                                   0        0
            strict s , i I(T ) = I(T) \ {x}, E(T ) = E(T) \ {y, z} ∪ {x}, D T  0(v) = D T (v), ∀ v ∈ I(T ) ∪ E(T ).
                                                              0
            Utilizˆand s , i ipoteza de induct , ie, aplicat˘a pentru T , avem  P  D T (v) =  P  D T  0(v)−D T 0(x)+
                                                                                          0
                                                                     v∈E(T)          v∈E(T )
            D T (y)+D T (z) =   P   D T 0(v)+2(n−1)−D T (x)+2(1+D T (x)) =       P     D T (v)+D T (x)+2n =
                                   0
                              v∈I(T )                                         v∈I(T)\{x}
                  D T (v) + 2n. Demonstrat , ia prin induct , ie este ˆıncheiat˘a.
              P
            v∈I(T)
            Propozit , ia 4. Pentru orice arbore binar strict T cu n noduri interne, n ∈ N, avem
                                                 h(T) ≥ dlog (n + 1)e .
                                                             2

            Demonstrat¸ie. Consider˘am c˘a nivelul pe care este reprezentat˘a r˘ad˘acina arborelui este numerotat
            cu 0. T este un arbore binar strict, cu 2n + 1 noduri (n interne s , i n + 1 externe), iar pe fiecare
                                                      i
                                                                                                2
            nivel i ∈ {0, 1, . . . , h(T)} el are cel mult 2 noduri (induct , ie!), deci 2n+1 ≤ 1+2+2 +. . .+2 h(T) .
            Obt , inem, succesiv: 2n + 1 ≤ 2 h(T)+1  − 1, 2 h(T)  ≥ n + 1, h(T) ≥ log (n + 1). Cum h(T) ∈ N,
                                                                                   2
            deducem c˘a h(T) ≥ dlog (n + 1)e .
                                     2
                                              ∗
            Observat ,ia 3. Pentru orice n ∈ N avem dlog (n + 1)e = 1 + blog nc .
                                                          2                    2
                ˆ                                           ∗
                Intr-adev˘ar, fie dlog (n + 1)e = k, k ∈ N . Avem, succesiv: k − 1 < log (n + 1) ≤ k,
                                     2                                                        2
                                             k
                             k
            2 k−1  < n+1 ≤ 2 , 2 k−1  ≤ n < 2 , k −1 ≤ log n < k. Deci blog nc = k −1 = dlog (n + 1)e−1.
                                                                            2
                                                          2
                                                                                               2
            Propozit , ia 5. Fie T un arbore binar strict cu n noduri interne, n ∈ N. Dac˘a toate nodurile
            externe sunt situate pe ultimul s , i, eventual, pe penultimul nivel, atunci avem
                                                 h(T) = dlog (n + 1)e ,
                                                             2
                                 X                                              dlog (n+1)e
                                     D T (v) = (n + 1) dlog (n + 1)e + n + 1 − 2   2     .
                                                           2
                               v∈E(T)
   38   39   40   41   42   43   44   45   46   47   48