CS计算机代考程序代写 data structure AVL algorithm COMP2521

COMP2521
Data Structures & Algorithms

Week 4.2
AVL Trees

1

In this lecture

Why?

Rebalancing methods often have an O(n) worse case, and
we want to find something with O(log(n)) worst case.

What?

AVL Tree Overview
Examples
Pseudocode

2

AVL Tree

AVL trees fix imbalances as soon as they occur. It aims to have the tree
reasonably maintain balance with an O(log(n)) cost.

 
General Method:

Store information on each node (amortisation) about it’s height/balance
Do repairs on tree balance locally, not on overall structure

 
Invented by Georgy Adelson-Velsky and Evgenii Landis   (1962)

 

3

AVL Tree Method

A tree is unbalanced (height) when:
 
 

This tree can be repaired by rotation:

If left subtree is too deep, rotate right
If right subtree is too deep, rotate left

 
This process would normally be O(n) as you have to traverse all nodes to figure

out the height of any particular sub-tree.
 

However, we will store the balance data on each node (height or balance)
which will make things faster, but also mean more to maintain.

∣height(left) − height(right)∣ > 1

4

AVL Tree Structure(practical)

Red numbers are height. Typically stored on node.
Green numbers are balance. Stored or calculated based on immediate children.

Rule: Rotate whenever tree |balance| > 1
5 . 1

AVL Tree Structure(practical)

Insertion of 6 will trigger a rotate right on 8.

5 . 2

AVL Insertion Algorithm

PseudocodePseudocode
insertAVL(tree, item):
if tree is empty:
return new node containing item
else if item = data(tree):
return tree

if item < data(tree): left(tree) = insertAVL(left(tree),item) else if item > data(tree):
right(tree) = insertAVL(right(tree),item)
LHeight = height(left(tree))
RHeight = height(right(tree))
if (LHeight – RHeight) > 1:
if item > data(left(tree)):
left(tree) = rotateLeft(left(tree))
tree = rotateRight(tree)
else if (RHeight – LHeight) > 1:
if item < data(right(tree)) then right(tree) = rotateRight(right(tree)) tree=rotateLeft(tree) return tree 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 6 AVL Tree Performance Average/worst-case search performance of O(log(n)) Finite time spent on maintaining height data in each node Finite time spent rebalancing locally when there is imbalance Trees are always height-balanced. Subtree depths differ by +/- 1 May not be weight-balanced, as subtrees may differ in size (even if height only varies by 1)   7