43964

AVL дерево как инструмент повышения эффективности поиска. Оценки сложности поиска

Доклад

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

Бинарные деревья поиска предназначены для быстрого доступа к данным. В идеале разумно сбалансированное дерево имеет высоту порядка O(log2n)...

Русский

2014-03-31

17.8 KB

12 чел.

AVL дерево как инструмент повышения эффективности поиска. Оценки сложности поиска

АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

Относительно АВЛ-дерева балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев = 2, изменяет связи предок-потомок в поддереве данной вершины так, что разница становится <= 1, иначе ничего не меняет. Указанный результат получается вращениями поддерева данной вершины.

Бинарные деревья поиска предназначены для быстрого доступа к данным. В идеале разумно сбалансированное дерево имеет высоту порядка O(log2n). Однако при некотором стечении обстоятельств дерево может оказаться вырожденным. Тогда высота его будет O(n), и доступ к данным существенно замедлится.

Разница во времени доступа будет гораздо заметнее при большем числе узлов. Например, в идеально сбалансированном дереве из 1023 узлов время доступа в худшем случае будет равно 10 единицам времени, в среднем: единицам времени.

А в вырожденном дереве из 1023 узлов потребуется в худшем случае 1023 единицы времени, в среднем - 512 единиц времени. Поэтому при работе с деревьями поиска больших размеров крайне желательно, чтобы они были близки к сбалансированным.

Оценка сложности поиска. Обоснованность применения AVL-деревьев неоднозначна, поскольку они требуют дополнительных затрат на поддержание сбалансированности при вставке или удалении узлов. Если в дереве постоянно происходят вставки и удаления элементов, эти операции могут значительно снизить быстродействие. С другой стороны, если ваши данные превращают бинарное дерево поиска в вырожденное, вы теряете поисковую эффективность и вынуждены использовать AVL-дерево. В большинстве случаев в программах используются алгоритмы, когда сначала заполняется список, а потом производится поиск по этому списку с небольшим количеством изменений. Поэтому на практике использование AVL-деревьев предпочтительно.

Для AVL-дерева не существует наихудшего случая, так как оно является почти полным бинарным деревом. Сложность операции поиска составляет O(log2n). Опыт показывает, что повороты требуются примерно в половине случаев вставок и удалений. Сложность балансировки обусловливает применение AVL-деревьев только там, где поиск является доминирующей операцией.

Очевидно, что операции вставки и удаления (а также более простая операция поиска) выполняются за время пропорциональное высоте дерева, т.к. в процессе выполнения этих операций производится спуск из корня к заданному узлу, и на каждом уровне выполняется некоторое фиксированное число действий. А в силу того, что АВЛ-дерево является сбалансированным, его высота зависит логарифмически от числа узлов. Таким образом, время выполнения всех трех базовых операций гарантированно логарифмически зависит от числа узлов дерева.


 

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

52885. Погода взимку. Розваги 502.5 KB
  Winter is the fourth season. December, January and February are winter months. In winter it is cold. Winter is the coldest season of the year. All rivers and ponds are frozen. The ground is covered with snow. Trees and bushes are covered with snowflakes.
52886. Свята та традиції. New Year 1.98 MB
  Objectives: to develop the habits of reading, writing and speaking on the given topic; to practise the structure “there is/are”, asking and answering questions in Present Simple; to enlarge the students’ knowledge about holidays and traditions of the English-speaking countries.
52887. All About Us. Two Capitals: London, Kyiv 48 KB
  Objectives: - to develop pupils’ skills in listening, reading, speaking and writing; - to teach pupils to express their opinion; - to provide interactive work in pairs and small groups; - to teach pupils cooperative work;
52888. London Transport 83 KB
  There are lots of places of interest in London. From Tower Bridge you can see the Tower of London. From Tower Bridge you can see the Tower of London. It is a museum now. There are hundreds of interesting collections in it. There is a famous clock in London called Big Ben
52889. All Seasons Are Beautiful 55 KB
  Teacher: Different people have different tempers. On different parts of the day everybody has different mood. Let’s see how you are now. Take your “faces” and if you feel well, great – draw a smile; if you feel neither well nor bad, draw a face without a smile; and if you are sad and unhappy, draw a sad face...
52890. Love. Wedding. Marriage 185 KB
  Objectives to develop student’s fluency in speaking English, communicative activity using interactive forms; to motivate students in expressing their opinions; to develop students’ thinking skills;
52892. Eating habits. Good health is above wealth 52.5 KB
  At the lesson we are going to revise the words learned at the previous lessons ; improve reading ,listening and speaking skills; We are going to practice in grammar. We’ll give advice what food should we eat to be healthy.
52893. Охорона навколишнього середовища 102.5 KB
  This footage includes Masai in their own village. No animals were harmed in any way during the making of this music video. Shock footage of the actual inhumane treatment of animals was acquired from documents archives. It should be noted that while filming was in progress an Africa elephant (not pictured in the video) was killed by poachers within miles of the shoot.