Algorithms & Data Structures (Winter 2022) AVL
Announcements
Comp 251(c) 2020
Copyright By PowCoder代写 加微信 powcoder
• Introduction. • Operations. • Application.
Introduction – Binary Search Trees
• T is a rooted binary tree
• Key of a node x > keys in its left subtree.
• Key of a node x < keys in its right subtree. 4
BST – Operations
• Search(T,k): O(h) • Insert(T,k): O(h)
• Delete(T,k): O(h)
Where h is the height of the BST.
BST – Height of a tree
Height(n): length (#edges) of longest downward path from node n to a leaf.
Height(x) = 1 + max( height(left(x)), height(right(x)) )
Height(right(x))
Height(left(x))
BST – Height of a tree - Example
= 1+max( h(b) , h(g) )
= 1+max(1+max(h(c),h(d)),1+h(h)) = 1+max(1+max(0,h(d)),1+0)
= 1+max(1+max(0,1+h(e)),1)
= 1+max(1+max(0,1+(1+h(f)))),1) = 1+max(1+max(0,1+(1+0))),1)
= 1+max(3,1)
BST – In-order traversal
inorderTraversal(treeNode x)
if x != nil inorderTraversal(x.leftChild); print x.value; inorderTraversal(x.rightChild);
• Print the nodes in the left subtree (A), then node x, and then the nodes in the right subtree (B)
• InaBST,itprintsfirstkeys
BST – In-order traversal
8, 12, 15, 20, 27, 36, 43, 57 9 All keys come out sorted!
BST – In-order traversal – Sort
1. Build a BST from the list of keys (unsorted)
2. Use in-order traversal on the BST to print the keys.
Running time of BST sort: insertion of n keys + tree traversal.
à8, 12, 27, 36, 43, 57 10
BST – Sort – Running time
• In-order traversal is O(n)
• Running time of insertion is O(h)
Best case: The BST is always balanced for every insertion.
Ω(n log(n))
Worst case: The BST is always un-balanced. All
insertions on same side.
∑n n ⋅ ( n − 1 ) 2
i= 2 =O(n ) i=1
BST – Good vs Bad BSTs
Balanced h=O( log n )
Unbalanced
AVL – Trees
Definition: BST such that the heights of the two child subtrees of any node differ by at most one.
|hleft-hright|≤1
• Invented by G. Adelson-Velsky and E.M. Landis in 1962.
• AVL trees are self-balanced binary search trees.
• Insert, Delete & Search take O(log n) in average and worst
• To satisfy the definition, the height of an empty subtree is -1
AVL – Trees -Example
Taken from Langer2014
AVL – Trees -Example
Taken from Langer2014
AVL – Trees height – Worst case
• AVL trees with a minimum number of nodes are the worst case examples.
• every node’s subtrees differ in height by one.
• we cannot make these trees any worse / any more unbalanced.
• If we add or remove a leaf node, we either get a non-AVL or balance one of the subtree.
Figure taken from recitation
“If we can bound the height of these worst
case examples of AVL trees,
then we’ve pretty much bounded the height of all AVL trees”
AVL – Trees height
Nh = minimum #nodes in an AVL tree of height h.
𝑁! = 1 + 𝑁!”# + 𝑁!”$
𝑁! > 1 + 𝑁!”$ + 𝑁!”$
𝑁! > 2 ∗ 𝑁!”$ !’
𝑁! >2∗2 ∗𝑁!”% >2∗2 ∗2 ∗𝑁!”& > …>2 $
⟹ log(𝑁 ) > log(2!’ ) !”
⟹ 2*log(𝑁!) > h ⟹ h = O(log(n))
Larger height when tree is unbalanced.
• Introduction. • Operations. • Application.
Definition: Balance Factor
• The balance factor of a binary tree is the difference in heights of its two subtrees (hL – hR). It may take on one of the values -1, 0, +1.
Figure taken from randerson112358.medium.com.
Definition: Balance Factor
ß: Left tree is higher (left-heavy) = : Balanced
à: Right tree is higher (right-heavy)
Definition: Rotations
• Suppose we have. Taken from Langer2014
• All keys in A are less than key k1. k1 is less than all keys in B, which are less than k2. k2 is less than all keys in C 21
Definition: Right Rotation
Taken from Langer2014
Definition: Right Rotation
Definition: Right Rotation
Taken from Langer2014
Definition: Right Rotation
Taken from Langer2014
Definition: Left Rotation
Taken from Langer2014
Exercise =>
Definition: Rotations
Right rotation
AB BC Left rotation
Rotations change the tree structure & preserve the BST
Operations: AVL insertion
1.Insert as in standard BST 2.Restore AVL tree properties
x insert(y) x restoreAVL() x àèà
Operations: AVL insertion – Example
27 43 = 20ß=
Insert(T, 15)
How to restore AVL property?
Operations: AVL insertion
Taken from Langer2014
Operations: AVL insertion
Operations: AVL insertion
Left rotation
h+1 k1 h+1
B h+1hAhB C
After (balanced)
Operations: AVL insertion
Operations: AVL insertion
è Right rotation at k2 kè
h+1 k1 k2 h+1
C Left rotation at k1
14th , 2020 34
Operations: AVL insertion
1. SupposexislowestnodeviolatingAVL
2. Ifxisright-heavy:
• If x’s right child is right-heavy or balanced: Left
rotation (case outside)
• Else: Right followed by left rotation (case inside)
3. Ifxisleft-heavy:
• If x’s left child is left-heavy or balanced: Right
rotation (sym. of case outside)
• Else: Left followed by right rotation (sym. of case
Operations: AVL insertion – Example
Right rotation at 27
12 57 12 57
8 27 43 8 20 43
Insert(T, 15)
How to restore AVL property?
Operations: AVL insertion – Example
36 Left rotation at 43 36
12 57 12 57
8 20 43 8 20
152750 152743
We remove the zig-zag pattern
Insert(T, 50)
RotateLeft(T,43) 37
Operations: AVL insertion – Example
Right rotation at 57
50 8 20 43 57
AVL property restored!
RotateRight(T,57)
AVL insertion: running time
• Insertion in O(h)
• At most 2 rotation operations which take O(1)
• Running time is O(h) + O(1) = O(h) = O(log n) in AVL trees.
Comp 251(c) 2020
AVL sort: running time
Same as BST sort but use AVL trees and AVL insertion instead.
• Worst case running time can be brought to O(n log n) if the tree is always balanced.
• Use AVL trees (trees are balanced).
• Insertion in AVL trees are O(h) = O(log n) for balanced trees.
Comp 251(c) 2020
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com