47287

Алгоритм пересчета балансов вершин выделенного пути и его особенности

Доклад

Информатика, кибернетика и программирование

После добавления нового элемента необходимо обновить коэффициенты сбалансированности родительских узлов Если любой родительский узел принял значение -2 или 2, то необходимо выполнить балансировку поддерева путем поворота

Русский

2014-03-31

76.6 KB

0 чел.

Алгоритм пересчета балансов вершин выделенного пути и его особенности.

Основная идея

Если вставка или удаление элемента приводит к нарушению сбалансированности дерева то выполняется его балансировка 

 Коэффициент сбалансированности узла

это разность высот его левого и правого поддеревьев 

В АВЛ дереве коэффициент сбалансированности любого

узла принимает значения из множества {-1, 0, 1}

Балансировка дерева

После добавления нового элемента необходимо обновить коэффициенты сбалансированности родительских узлов Если любой родительский узел принял значение -2 или 2, то необходимо выполнить балансировку поддерева путем поворота

Типы поворотов:

Одиночный правый поворот

Одиночный левый поворот

Двойной лево -правый поворот

Двойной право- левый поворот


 

А также другие работы, которые могут Вас заинтересовать

29444. Рынок и государство. Роль государства в рыночной и командно-административной экономике. Экономические функции государства 18.49 KB
  Роль государства в рыночной и командноадминистративной экономике. Экономические функции государства. Роль государства в рыночной экономике Представления о рыночной экономике как куплепродаже по свободным ценам не исчерпывает всего многообразия рыночных отношений. Основной для любого государства является факт государственного вмешательства в экономику.
29448. Модель LM 30.14 KB
  В основе построения кривой LM лежит кейнсианская теория предпочтения ликвидности объясняющая как соотношение спроса и предложения реальных запасов денежных средств определяют ставку процента. Рассмотрим построение кривой LM на основе графического анализа равновесия денежного рынка. Графический вывод кривой LM первый способ На рис. Пересечение кривой спроса с кривой предложения денег дает нам ставку процента r1 которая уравновешивает рынок денег при данном уровне дохода Y1.
29451. Экономические отношения в системе всемирного хозяйства.Основные формы ЭО 15.16 KB
  Международные экономические отношения включают многоуровневый комплекс экономических отношений между отдельными странами их региональными объединениями и субъектами а также отдельными предприятиями транснациональными многонациональными корпорациями в системе мирового хозяйства. При рассмотрении международных экономических отношений с точки зрения науки объектом изучения становится не экономика зарубежныхстран а особенности их экономических отношений причем только наиболее часто повторяющиеся типичные характерные определяющие...
29452. Понятие критических точек инфляции. Инфляция в РБ. Степень развития инфляции 13.41 KB
  Понятие критических точек инфляции.Степень развития инфляции Крит.В условиях критической точки инфляции уменьшаются поступления в бюджет особенно прямых налогов так как они исчисляются с доходов и имущества имеющих оценку в предшествующий период.Следовательно на начальной стадии развития инфляции предприниматели и население выражают определенную веру в стабильность уровня цен.