Алгоритмы и структуры данных на С++. Аксёнова Е.А - 76 стр.

UptoLike

ВУЗ: 

ПетрГУ | Петрозаводск

Составители: 

Рубрика: 

76 Глава 6. Поиск
q=new node;
q->key=K;
cin>>q->info;
q->llink=NULL;
q->rlink=NULL;
if(K>p->key)
p->rlink=q;
else
p->llink=q;
}
Среднее время поиска вычисляется по формуле T = 2 · ln(n).
6.4. Оптимальные и сбалансированные деревья
Пусть есть три ключа K
1
, K
2
, K
3
, где K
1
≤ K
2
≤ K
3
, и известны
вероятности обращений к этим ключам p
1
, p
2
, p
3
, где p
1
+ p
2
+ p
3
= 1.
Возможны 5 разных деревьев поиска (рис. 6.2).
Рис. 6.2
Напишем формулу, которая вычисляет среднее время поиска для
каждого дерева:
I: 1 · p
1
+ 2 · p
2
+ 3 · p
3
,
II: 2 · p
1
+ 1 · p
2
+ 2 · p
3
,
... и т. д. ...
Вычисляя средние времена поиска для всех возможных деревьев,
мы находим дерево, которое минимизирует время поиска, т. е. опти-
76                                                      Глава 6. Поиск


         q=new node;
         q->key=K;
         cin>>q->info;
         q->llink=NULL;
         q->rlink=NULL;

         if(K>p->key)
                 p->rlink=q;
         else
                 p->llink=q;
}
     Среднее время поиска вычисляется по формуле T = 2 · ln(n).


     6.4. Оптимальные и сбалансированные деревья

   Пусть есть три ключа K1 , K2 , K3 , где K1 ≤ K2 ≤ K3 , и известны
вероятности обращений к этим ключам p1 , p2 , p3 , где p1 + p2 + p3 = 1.
Возможны 5 разных деревьев поиска (рис. 6.2).




                               Рис. 6.2

   Напишем формулу, которая вычисляет среднее время поиска для
каждого дерева:
          I: 1 · p1 + 2 · p2 + 3 · p3 ,
          II: 2 · p1 + 1 · p2 + 2 · p3 ,
          ... и т. д. ...
   Вычисляя средние времена поиска для всех возможных деревьев,
мы находим дерево, которое минимизирует время поиска, т. е. опти-

Страницы