程序代写代做代考 data structure algorithm Recursive Version

Recursive Version

Data Structures and Algorithms
(DSA)

Lecture 10: Binary Search Trees

Data Structures and Algorithms

Overview

• Trees

• Sorted Sequences

• Binary Search Trees

Data Structures and Algorithms

Tree

Data Structures and Algorithms

7

3 13

2 11

17

19

5

18 22

Representing Trees

• Heaps are special trees (can be stored
efficiently in an array)

• Want to have a pointer based representation
of trees

• Each node stores

– an element

– has a pointer to the left subtree (might be empty)

– has a point to the right subtree (might be empty)

Data Structures and Algorithms

TreeItem

Class Handle = Pointer to TreeItem

Class TreeItem of Element

e: Element

right: Handle

left: Handle

Data Structures and Algorithms

e

right

left

Tree Traversal

• Want to visit every node in the tree (and print
out the elements).

• Recursive formulation for tree traversal

Data Structures and Algorithms

Preorder Traversal

Preorder(Tree T)

1. Visit the root (and print out the element)

2. If (T->left !=null) Preorder(T->left)

3. If (T->right !=null) Preorder(T->right)

Data Structures and Algorithms

Preorder Traversal

Data Structures and Algorithms

7

3 13

2 11

17

19

5

18 22

Order nodes are visited: 17, 7, 3, 2, 5, 13, 11, 19, 18, 22

Postorder Traversal

Postorder(Tree T)

1. If (T->left !=null) Postorder(T->left)

2. If (T->right !=null) Postorder(T->right)

3. Visit the root (and print out the element)

Data Structures and Algorithms

Postorder Traversal

Data Structures and Algorithms

7

3 13

2 11

17

19

5

18 22

Order nodes are visited: 2, 5, 3, 11, 13, 7, 18, 22, 19, 17

Inorder Traversal

Inorder(Tree T)

1. If (T->left !=null) Inorder(T->left)

2. Visit the root (and print out the element)

3. If (T->right !=null) Inorder(T->right)

Data Structures and Algorithms

Inorder Traversal

Data Structures and Algorithms

7

3 13

2 11

17

19

5

18 22

Order nodes are visited: 2, 3, 5, 7, 11, 13, 17, 18, 19, 22

Observation: This sequence is sorted

Sorted Sequences

Operations for Sorted Sequences

• Find an element e in the sorted sequence

• Insert an element e into the sorted sequence

• Delete an element e from the sorted
sequence.

Data Structures and Algorithms

Want to have all these operations implemented in time O(log n).

Binary Search Tree

Data Structures and Algorithms

7

3 13

2 11

17

Sorted sequence by Inorder Traversal: 2, 3, 5, 7, 11, 13, 17, 18, 19, 22

19

5

18 22

Properties of Binary Search Trees

• All elements in the left subtree of a node k
have value smaller than k.

• All elements in the right subtree of a node k
have value larger than k.

Data Structures and Algorithms

Method find

find(k)

• Start at the root.

• At a node x, compare x and k.

1. If k=x, then found

2. If k < x, search in the left subtree of x. If subtree does not exist return not found. 3. If k > x, search in the right subtree of x. If
subtree does not exist, return not found

Data Structures and Algorithms

Find

Data Structures and Algorithms

7

3 13

2 11

17

19

5
Find 11

18 22

Find

Data Structures and Algorithms

7

3 13

2 11

17

19

5
Find 11

18 22

Insertion

insert(k)

1. find(k)

2. If not found, element with key k becomes
child of the last visited node of find(k).

Data Structures and Algorithms

Insert

Data Structures and Algorithms

7

3 13

2 11

17

19

5
Insert 14

18 22

Insert

Data Structures and Algorithms

7

3 13

2 11

17

19

5
Insert 14

14
Last visited node for find(14)

18 22

Remove

remove(k)
1. find(k)
• If k is stored at a leaf, delete this leaf and the

incoming edge.
• If k has one child x, redirect pointer pointing to k

to x and delete k.
• If k has two children

– search in the tree for the largest element x smaller
than k.

– swap x and k and delete(k)

Data Structures and Algorithms

Remove leaf

Data Structures and Algorithms

7

3 13

2 11

17

19

5
Remove 2

18 22

Remove leaf

Data Structures and Algorithms

7

3 13

11

17

19

5
Remove 2

18 22

Remove node with 1 child

Data Structures and Algorithms

7

3 13

11

17

19

5
Remove 3

18 22

Remove node with 1 child

Data Structures and Algorithms

7

5 13

11

17

19

3
Remove 3

18 22

Remove node with 1 child

Data Structures and Algorithms

7

5 13

11

17

19

Remove 3

18 22

Remove node with 2 children

How to find the largest element smaller than k?

• Go to the left child of k (has to exist as k has
two children.

• Follow the pointer to the right as long as
possible.

Data Structures and Algorithms

Remove node with 2 children

Data Structures and Algorithms

7

5 13

11

17

19

Remove 17

18 22

Swap 13 and 17

Remove node with 2 children

Data Structures and Algorithms

7

5 17

11

13

19

Remove 17

18 22

Remove node with 2 children

Data Structures and Algorithms

7

5 11

17

13

19

Remove 17

18 22

Remove node with 2 children

Data Structures and Algorithms

7

5 11

13

19

Remove 17

18 22

Perfectly Balanced Binary Search Trees

• A binary search tree is perfectly balanced if it
has height (height is the length of the
longest path from the root to a leaf)

Data Structures and Algorithms

Insertion

Data Structures and Algorithms

19 Insert 17

Insertion

Data Structures and Algorithms

19 Insert 13

17

Insertion

Data Structures and Algorithms

19 Insert 11

17

13

Insertion

Data Structures and Algorithms

19 Insert 7

17

13

11

Insertion

Data Structures and Algorithms

19

17

13

11

7

Problem?

Tree can degenerate to a list.