Dictionary ADT

(1)

Dictionary ADT

Dictionary ADT models:

I a searchable collection of key-element items.

I search via the key

Main operations are: searching, inserting, deleting items

I findElement(k): returns the element with keykif the dictionary contains such an element

(otherwise returns special elementNo_Such_Key)

I insertItem(k,e): inserts(k,e)into the dictionary

I removeElement(k): likefindElement(k)but additionally removes the item if present

I size(),isEmpty()

I keys(),elements()

(2)

Log File

A log file is a dictionary implemented based on an unsorted list:

I Performance:

I insertItemisO(1)(can insert anywhere, e.g. end)

I findElement, andremoveElementareO(n)

(have to search the whole sequence in worst case)

I Efficient for small dictionaries or if insertions are much more frequent than search and removal.

(e.g. access log of a workstation)

(3)

Ordered Dictionaries

Ordered Dictionaries:

I Keys are assumed to come from a total order.

I New operations:

I closestKeyBefore(k)

I closestElementBefore(k)

I closestKeyAfter(k)

I closestElementAfter(k)

(4)

Binary Search

Binary search performsfindElement(k)on sorted arrays:

I each step the search space is halved

I time complexity isO(log₂n)

I for pseudo code and complexity analysis see lecture 1 Example:findElement(7)

0 1 3 5 7 8 9 11 15 16 18

low high

(5)

Binary Search

0 1 3 5 7 8 9 11 15 16 18

low high

8

(6)

Binary Search

0 1 3 5 7 8 9 11 15 16 18

low high

8

0 1 3 5 7 8 9 11 15 16 18

low high

(7)

Binary Search

0 1 3 5 7 8 9 11 15 16 18

low high

8

0 1 3 5 7 8 9 11 15 16 18

low high

3

(8)

Binary Search

0 1 3 5 7 8 9 11 15 16 18

low high

8

0 1 3 5 7 8 9 11 15 16 18

low high

3

0 1 3 5 7 8 9 11 15 16 18

low high

(9)

Binary Search

0 1 3 5 7 8 9 11 15 16 18

low high

8

0 1 3 5 7 8 9 11 15 16 18

low high

3

0 1 3 5 7 8 9 11 15 16 18

low high 5

(10)

Binary Search

0 1 3 5 7 8 9 11 15 16 18

low high

8

0 1 3 5 7 8 9 11 15 16 18

low high

3

0 1 3 5 7 8 9 11 15 16 18

low high 5

0 1 3 5 7 8 9 11 15 16 18

low high

(11)

Binary Search

0 1 3 5 7 8 9 11 15 16 18

low high

8

0 1 3 5 7 8 9 11 15 16 18

low high

3

0 1 3 5 7 8 9 11 15 16 18

low high 5

0 1 3 5 7 8 9 11 15 16 18

low high 7

(12)

Lookup Table

A lookup table is a (ordered) dictionary based on a sorted array:

I Performance:

I findElementtakesO(log₂n)using binary search

I insertItemisO(n)(shiftingn/2 items worst case)

I removeElementtakesO(n)(shiftingn/2 items worst case)

I Efficient for small dictionaries or if search are much more frequent than insertion and removal.

(e.g. user authentication with password)

(13)

Data Structure for Trees

A node is represented by an object storing:

I an element

I link to the parent node

I list of links to children nodes

A

B C

E F

D

∅

A

∅

B C

∅

D

∅ E

∅ F

(14)

Data Structure for Binary Trees

A node is represented by an object storing:

I an element

I link to the parent node

I left child

I right child

A

B C

D E

∅ A

∅ ∅

B C

∅ ∅ D

∅ ∅ E

Binary trees can also be represented by a Vector, see heaps.

(15)

Binary Search Tree

Abinary search treeis a binary tree such that:

I The inner nodes store keys (or key-element pairs).

(leafs are empty, and usually left out in literature)

I For every noden:

I the left subtree ofncontains only keys<key(n)

I the right subtree ofncontains only keys>key(n)

6 2

1 4

9 8

I Inorder traversal visits the keys in increasing order.

(16)

Binary Search Tree: Searching

Searching for keykin a binary search treetworks as follows:

I if the root oftis an inner node with keyk⁰:

I ifk ==k⁰, then return the element stored at the root

I ifk <k⁰, then search in the left subtree

I ifk >k⁰, then search in the right subtree

I iftis a leaf, then returnNo_Such_Key(key not found) Example:findElement(4)

6 2

1 4

9 8

<

>

(17)

Binary Search Tree: Minimal Key

Finding the minimal key in a binary search tree:

I walk left until the the left child is a leaf minKey(n):

ifisExternal(n)then returnNo_Such_Key ifisExternal(leftChild(n))then

returnkey(n) else

returnminKey(leftChild(n))

Example: for the tree below,minKey()returns 1 6

2

1 4

9 8

(18)

Binary Search Tree: Maximal Key

Finding the maximal key in a binary search tree:

I walk right until the the right child is a leaf maxKey(n):

ifisExternal(n)then returnNo_Such_Key ifisExternal(rightChild(n))then

returnkey(n) else

returnmaxKey(rightChild(n))

Example: for the tree below,maxKey()returns 9 6

2

1 4

9 8

(19)

Binary Search Tree: Insertion

Insertion of keykin a binary search treet:

I search forkand remember the leafwwhere we ended up (assuming that we did not findk)

I insertk at nodew, and expandwto an inner node Example:insert(5)

6 2

1 4

9 8

<

>

6 2

1 4

5

9 8

(20)

Binary Search Tree: Deletion above External

The algorithmremoveAboveExternal(n)removes a node for which at least one child is a leaf (external node):

I if the left child ofnis a leaf, replacenby its right subtree

I if the right child ofnis a leaf, replacenby its left subtree Example:removeAboveExternal(9)

6 2

1 4

9 8 7

remove

6 2

1 4

8 7

(21)

Binary Search Tree: Deletion

The algorithmremove(n)removes a node:

I if at least one child is a leaf thenremoveAboveExternal(n)

I if both children ofnare internal nodes, then:

I find the minimal nodemin the right subtree ofn

I replace the key ofnby the key ofm

I remove the nodemusingremoveAboveExternal(m) (works also with the maximal node of the left subtree) Example:remove(6)

6 2

1 4

9 8 7

remove

7 2

1 4

9 8

(22)

Performance of Binary Search Trees

Binary search tree storingnkeys, and heighth:

I the space used isO(n)

I findElement,insertItem,removeElementtakeO(h)time The heighthisO(n)in worst case andO(log₂n)in best case:

I findElement,insertItem, andremoveElement takeO(n)time in worst case

(23)

AVL Trees

AVL treesare binary search trees such that for every inner nodenthe heights of the children differ at most by 1.

I AVL trees are often called height-balanced.

3 0

2

8 6

4 7

9 4

2 1

1 1

1 2

3

I Heights of the subtrees are displayed above the nodes.

(24)

AVL Trees: Balance Factor

Thebalance factorof a node is the height of its right subtree minus the height of its left subtree.

3 0

2

8 6

4 7

9 1

1 0

0 0

-1

I Above the nodes we display the balance factor.

I Nodes with balance factor -1,0, or 1 are called balanced.

(25)

The Height of AVL Trees

The height of an AVL tree storingnkeys isO(logn).

Proof.

Letn(h)be the minimal number of inner nodes for heighth.

I we haven(1) =1 andn(2) =2

I we know

n(h) =1+n(h−1) +n(h−2)

>2·n(h−2) sincen(h−1)>n(h−2)

>4·n(h−4)

>8·n(h−6)

n(h)>2ⁱ·n(h−2i) by induction

≥2^h/2 Thush≤2·log₂n(h).

(26)

AVL Trees: Insertion

Insertion of a keykin AVL trees works in the following steps:

I We insertkas for binary search trees:

I let the inserted node bew

I After insertion we might need to rebalance the tree:

I the balance of the ancestors ofwmay be affected

I nodes with balance factor -2 or 2 need rebalancing

Example:insertItem(1)(without rebalancing) 3

0 2

8 -1

1 0

0 3

0 2 1

8 -2

0 2

-1 0 insert

rebalance

(27)

AVL Trees: Rebalancing after Insertion

After insertion the AVL tree may need to be rebalanced:

I walk from the inserted node to the root

I we rebalance the first node with balance factor -2 or 2 There are only the following 4 cases (2 modulo symmetry):

Left Left -2 -1

A h+1

inserted

B h

C h

Left Right -2 1

A h

B h+1

inserted

C h

Right Right 2 A 1

h B

h C h+1

inserted

Right Left 2 A -1

h B

h+1

inserted

C h

(28)

AVL Trees: Rebalancing, Case Left Left

The case ‘Left Left’ requires aright rotation:

x y

A h+1

inserted

B h

C h -2

-1 y

x A

h+1

inserted

B h

C h 0

0 rotate right

(29)

Example: Case Left Left

Example:insertItem(0) 7 4 2

1 3

6

8 0 9

0 0

-1 1

-1 insert

7 4 2 1 0

3 6

8 9 0

-1 -1

0

0 0

-2 1

-2

7 2 1 0

4

3 6

8 0 9

-1 0

0 0

1 -1 rotate right 2, 4

(30)

AVL Trees: Rebalancing, Case Right Right

The case ‘Right Right’ requires aleft rotation:

(this case is symmetric to the case ‘Left Left’)

x

y A

h B

h

C h+1

inserted

2

1 y

x

A h

B h

C h+1

inserted

0 0

rotate left

(31)

Example: Case Right Right

Example:insertItem(7) 3

2 5

4 8

0

0 0 0

1 insert

3

2 5

4 8

7 0

-1 0 1 0 2

5 3

2 4

8 7 0

-1 0 0

0 0 rotate right 3, 5

(32)

AVL Trees: Rebalancing, Case Left Right

The case ‘Left Right’ requiresa left and a right rotation:

x y

z A

h B

h

inserted

C h−1

D h -2 1

-1

x z

y

A h

B h

inserted

C h−1

D h -2 -2

0 rotate lefty,z

z

y x

A h

B h

inserted

C h−1

D h 0

0 1

rotate rightx,z

(insertion inC orzinstead ofBworks exactly the same)

(33)

Example: Case Left Right

Example:insertItem(5) 7 4

2 6

0 0 8

0 0

-1 insert

7 4

2 6

5 0 -1 8

1 0

-2

0

7 6

4

2 5

8 0

-2 0

0 -2

0 rotate left 4, 6

6 4

2 5

7 8 0

0 0

0 1 0

rotate right 6, 7

(34)

AVL Trees: Rebalancing, Case Right Left

The case ‘Right Left’ requiresa right and a left rotation:

x y A z

h B h−1

C h

inserted

D h 2

-1 1

x z A y

h B

h−1 C h

inserted

D h 2

2 0 rotate righty,z

z

x y

A h

B h−1

C h

inserted

D h 0

0 -1

rotate leftx,z

(this case is symmetric to the case ‘Left Right’)

(35)

Example: Case Right Left

Example:insertItem(7) 5

8 1

0

insert 5

8 7 2

-1 0

5

7 8 2

0 1 rotate right 7, 8

7

5 8

0 0

0 rotate left 5, 7

(36)

AVL Trees: Rebalancing after Deletion

After deletion the AVL tree may need to be rebalanced:

I walk from the inserted node to the root

I we rebalance all nodes with balance factor -2 or 2 There are only the following 6 cases (2 of which are new):

Left Left -2 -1

A h+1

B h

C h

deleted

Left Right -2 1

A h

B h+1

C h

deleted

Left -2 0

A h+1

B h+1

C h

deleted

Right Right 2 A 1

h

deleted B

h C h+1

Right Left 2 A -1

h

deleted B

h+1 C h

Right 2 A 0

h

deleted B

h+1 C h+1

(37)

AVL Trees: Rebalancing, Case Left

The case ‘Left’ requires aright rotation:

x y

A h+1

B h+1

C h

deleted

-2

0 y

x A

h+1 B

h+1 C

h

deleted

1

-1 rotate right

(38)

Example: Case Left

Example:remove(9) 7 4 2

1 3

6 5

8 0 9

0 0

-1 0

0 1

-1

0

remove

7 4 2

1 3

6 5

8 0

0 0

-1 0

0 0

-2

0

4 2

1 3

7 6 5

8 0

0

0 -1

0

1

0 -1

0 rotate right 4, 7

(39)

AVL Trees: Rebalancing, Case Right

The case ‘Right’ requires aleft rotation:

x

y A

h

deleted

B h+1

C h+1 2

0 y

x

A h

deleted

B h+1

C h+1 -1

1 rotate left

(40)

Example: Case Right

Example:remove(4) 6

4 8

7 9

0 0 0

1

0

remove

6 8

7 9

0 0 2

0

8 6

7

9 0 -1

1 0 rotate left 6, 8

(41)

AVL Trees: Performance

A single rotation (restructure) isO(1):

I assuming a linked-structure binary tree Insertion runs inO(logn):

I initial find isO(logn)

I rebalancing and update of heights isO(logn)

(at most 2 rotations are needed, no further rebalancing) Deletion runs inO(logn):

I initial find isO(logn)

I rebalancing and update of heights isO(logn)

I rebalancing may decrease the height of the subtree, thus further rebalancing above the node may be necessary Lookup (find) isO(logn)(height of the tree isO(logn)).

(42)

Example from Last Years Exam

8 5

3 2 1

4

6 7

10

9 11

11

I Show with pictures step for step how item 9 is removed.

I Indicate in every picture:

I which node is not balanced, and

I which nodes are involved in rotation.

(43)

Dictionaries: Performance Overview

Dictionary methods:

search insert remove

Log File O(n) O(1) O(n)

Lookup Table O(log₂n) O(n) O(n) AVL Tree O(log₂n) O(log₂n) O(log₂n) Ordered dictionary methods:

closestAfter closestBefore

Log File O(n) O(n)

Lookup Table O(log₂n) O(log₂n) AVL Tree O(log₂n) O(log₂n)

I Log File corresponds to unsorted list.

I Lookup Table corresponds to unsorted list