Изменения

|definition=""'''Танго дерево"" ''' - online бинарное дерево поиска с временем работы <tex> O(log log N) </tex>, создателями которого были которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Mihai Patrascu в 2004 году.

|definition='''Жирное ребро'''("''Prefered Path"'') - ребро, соединяющее вершину с ее последним посещенным ребенком.

<font color=green> // Из каждой вершины выходит <= 2 ребер.В общем случае одно жирное, другое нет.</font>

Поиск ключа <tex>x</tex>элемента в tango дереве схож с поиском в стандартном дереве поиска.

Ищем Начинаем с поиска в корне жирном пути корня tango-дерева – - splay-дереве.

Если текущее вспомогательное дереве не нашлисодержит искомый элемент, значит надо идти по нежирному ребрупоиск останавливается на родителе корня поддерева, содержащего нужное значение.

Пойдем Пройдем по немувспомогательной ссылке(красная стрелка) и ищем осуществим поиск в новом дереве.

Поиск в splay-дереве(синем) дереве = высота от количества вершин (количество вершин - длина = длине жирного пути = <tex>log n</tex>) = <tex>log log n</tex>.