Re: балансировка бинарного дерева

From

Spiridonov Ed (2:5059/9.55)

To

Spiridonov Ed

Date

2003-01-12T09:32:40Z

Area

RU.ALGORITHMS

Здравствуй Spiridonov!

Было <Пятница Январь 10 2003>, когда я прочитал как Spiridonov Ed писал к Nick
Kovaliov

похоже мне нужно вот это - bb-tree (сбалансированное по весу дерево, bounded
balanced tree).

определение приблизительно такое:
Let Alpha be a real such that 1/4 < Alpha <= 1 - sqrt(2)/2
Let T be a binary search tree
Let Tl (Tr ) be the left (right) subtree of the root of T

Definitions
The root balance of T, Rho , is given by:
Rho(T) = | Tl | / |T | = 1 - | Tr | / | T |
where | T | = number of leaves of tree T

A tree T is of bounded balance Alpha ,
if for every subtree T' of T we have:

Alpha <= Rho(T' ) <= 1 - Alpha

другое определение, которое я встречал:
0 <= Alpha <= 1/2
Rho(T) = (| Tl | + 1) / (| T | + 1)
Alpha <= Rho(T' ) <= 1 - Alpha

но вот нигде не могу найти конкертных алгоритмов добавления/удаления вершин.
никто не поделится? :)
url (или в крайнем случае ссылка на книгу, которую в библиотеке и/или магазине
найти можно) приветствуется.

ps: почему bb-tree, а не avl и т.д. - по условию задачи у меня уже в каждой
вершине хранятся | Tl | и | Tr | (которые в этом случае будут использоваться, а
для avl мы получим лишний геморрой с их корректным обновлением после
балансировки дерева)

                        С уважением, Ed.

--- Ничего особенного
 * Origin: My tiny station, Penza (2:5059/9.55)