53488

Процедура вставки вершин в AVL дерева и ее особенности

Доклад

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

Показатель сбалансированности в дальнейшем будем интерпретировать как разность между высотой левого и правого поддерева, а алгоритм будет основаться на типе TAVLTree, описанном выше. Непосредственно при вставке (листу) присваивается нулевой баланс

Русский

2014-04-01

19.29 KB

0 чел.

Процедура вставки вершин в AVL дерева и ее особенности.

Показатель сбалансированности в дальнейшем будем интерпретировать как разность между высотой левого и правого поддерева, а алгоритм будет основаться на типе TAVLTree, описанном выше. Непосредственно при вставке (листу) присваивается нулевой баланс. Процесс включения вершины состоит из трех частей (данный процесс описан Николасом Виртом в «Алгоритмы и структуры данных»):

  1. Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.
  2. Включения новой вершины в дерево и определения результирующих показателей балансировки.
  3. «Отступления» назад по пути поиска и проверки в каждой вершине показателя сбалансированности. Если необходимо — балансировка.

Будем возвращать в качестве результата функции, уменьшилась высота дерева или нет. Предположим, что процесс из левой ветви возвращается к родителю (рекурсия идет назад), тогда возможны три случая: { hl — высота левого поддерева, hr — высота правого поддерева } Включение вершины в левое поддерево приведет к

  1. hl < hr: выравняется hl = hr. Ничего делать не нужно.
  2. hl = hr: теперь левое поддерево будет больше на единицу, но балансировка пока не требуется.
  3. hl > hr: теперь hl — hr = 2, — требуется балансировка.

В третьей ситуации требуется определить балансировку левого поддерева. Если левое поддерево этой вершины (Tree^.left^.left) выше правого (Tree^.left^.right), то требуется большое правое вращение, иначе хватит малого правого. Аналогичные (симметричные) рассуждения можно привести и для включение в правое поддерево.


 

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

57687. Мої улюблені страви 43.5 KB
  Teacher: Very good! Я хочу дізнатися, про ваші вподобання на обід. Look at the blackboard, please (слайд 10). Використовуйте фрази «I like... for dinner», «I don`t like... for dinner». Але тепер вам треба пригадати назви продуктів за їхніми малюнками, які ви бачите на дошці.
57688. All About Food 53.5 KB
  On today`s lesson we`re going to speak about food. We`ll read a text about English meals, rememmber the names of different kinds of food, work in groops, listen to the text “Lunch at School” and do a test.
57689. Їжа. Food 206.5 KB
  So, as you see, we are beginning a new topic – “Food”. Do you think we’ll have good time learning it? Is it important to be able to speak on this topic? And you will be able not to speak, but to read...
57690. Фрукти. Овочі 45 KB
  The lemon is on the table. The banana is in the box. The strawberry is on the plate. The pear is in the tree. The plum is in his hand and the apple is in his right hand.
57691. Biography and literary works of Jack London 140 KB
  Objectives: given the information about Jack London in the form of old newspapers pupils would be able to improve their reading skills of literature vocabulary; after reading the information about Jack London...
57692. Sights of Kyiv 45 KB
  Introduction. Повідомлення теми уроку. Dear children, today we are going to speak, read, guess the riddles and do many interesting tasks. We are going to make excursions to the zoo, Botanical Garden, circus and Puppet’s Theatre.
57693. Сучасний Лондон 352 KB
  Today we are going to speak places of interest in London. You’ll watch a Computer presentation on the topic and we’ll discuss it. By the end of the lesson you will be able to speak about London
57694. Love and Marriage 56.5 KB
  We will lern some trditions discuss them nd write legend tht is worth of speking in every ge t the beginning lets mke up poem look t my sheet of pper nd drem bout love nd mke up poem...
57695. Здоровий спосіб життя 51.5 KB
  Practical: to train in listening comprehension; to develop communicative skills, using active lexis on the topic, to work with video material, to gain pupils experience be finding necessary materials from various sources.