Влияние върху производителността
Изтегляне 1.47 Mb.
|
Свързани:
saap conspect
| Наредени дървета- дърво с корен, в които е определен реда на децата за всеки възел.
Дърво с корен е това при което един възел е определен за корен на дървото. Бинарно дърво е или външен възел или вътрешен възел, свързан към двойка бинарни дървета, която се нарича ляво или дясно дърво на този възел. Математически свойства на бинарните дървета1св-во: Бинарно дърво с n на брой вътрешни възли има n+1 на брой външни възела. 2св-во: Бинарно дърво с n на брой вътрешни възли има 2 n на брой връзки. (n-1 на брой връзки към вътрешни възли и n+1 на брой връзки към вътрешни възли. 3св-во: Нивото на даден възел в дърво е по голямо с едно от нивото на неговия родител. 4св-во: Височината на бинарно дърво е максимума от нивата на неговите възли. 5св-во: Дължината на пътищата в бинарно дърво е сумата от нивата на неговите възли. Математически свойства на двоичните дървета.Св-во. Бинарно дърво с N вътр.възела има N+1 външни възела Док.се по индукция.Бин.дърво без вътр.възли има 1 външ.възел=>изпълн.за N=0. За N>0,всяко бин.дърво с N вътр.възли има К вътр.възли в лявото си поддърво и N-K-1 вътр.възли в дясното си поддърво,за К м/у 0 и N-1,тъй като коренът е вътр.възел.Спо-ред индукц.хипотеза,лявото поддърво има К+1 външ.възли,а дясното->N-K=>сум.N+1 Св-во. Бинарно дърво с N вътр.възела има 2N връзки;N-1 връзки към вътр.възли и N+1 връзки към външ.възли.. Във вс.дърво с корен вс.възел освен корена има 1родител,а вс.ребро свързва възел с неговия родител,така че има N-1 ребра,свърз. вътр.възли.Подобно вс.от N+1 външни възела има по 1 ребро към своя родител. Деф.Нивото на възел в дърво е > от нивото на неговия родител. Височина на дърво е max от нивата на въз. Дължина на вътр.пътища в бинар.дърво е сума от нивата на вътр.му възли Дължина на външ.пътища в бинар.дърво е сума от нивата на външ.му възли Тези деф.са пряко свърз.с анализа на алг. Изтегляне 1.47 Mb. Сподели с приятели:
|