Изменения

Перейти к: навигация, поиск

Декартово дерево

701 байт добавлено, 11:52, 17 апреля 2012
Insert
=== Insert ===
Операция <tex>Insert(T, k)</tex> добавляет в дерево <tex>T</tex> элемент <tex>k</tex>, где <tex>k.x</tex> {{---}} ключ, а <tex>k.y</tex>{{---}} приоритет.
 
Представим что элемент <tex>k</tex>, это декартово дерево из одного элемента, и для того чтобы его добавить в наше декартово дерево <tex>T</tex>, очевидно, нам нужно их слить. Но <tex>T</tex> может содержать ключи как меньше, так и больше ключа <tex>k</tex>, поэтому сначала нужно разрезать <tex>T</tex> по ключу <tex>k</tex>.
Представим что элемент <tex>k</tex>, это декартово дерево из одного элемента, и для того чтобы его добавить в наше декартово дерево <tex>T</tex>, очевидно, нам нужно их слить. Но <tex>T</tex> может содержать ключи как меньше, так и больше ключа <tex>k</tex>, поэтому сначала нужно разрезать <tex>T</tex> по ключу <tex>k</tex>.
Этот вариант отличается от первого существенно тем, что здесь не используется <tex>Merge</tex>.
 
Этот вариант отличается от первого существенно тем, что здесь не используется <tex>\mathrm{Merge}</tex>.
* Реализация №2

Навигация