CS计算机代考程序代写 algorithm COMP 250

COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 12-1 : Binary Search Trees
Giulia Alberini, Fall 2020 Slides adapted from Michael Langer’s

WHAT ARE WE GOING TO DO IN THIS VIDEO?
Binary Search Trees

BINARY SEARCH TREES

BSTNode
 The keys are “comparable” <, =, > e.g. numbers, strings.
class BSTNode{
K key;
BSTNode leftchild;
BSTNode rightchild;
: }

BINARY SEARCH TREE DEFINITION
binary tree
 keys are comparable, and unique (no duplicates)
 for each node, all descendents in left subtree are less than the node, and all descendents in the node’s right subtree are greater than the node (comparison is based on node key)

EXAMPLE
c
ae d
f
m
g
j

THIS IS NOT A BST. WHY NOT?
f
m g
j
c
ae d

BST – TRAVERSALS
f
m
g
j
An in-order traversal on a BST visits the nodes in the natural order defined by the key.
a c d ef g j m
c
ae d

BINARY SEARCH TREE ADT
 find( key )
 findMin()
 findMax()
 add(key)
 remove(key)
We can define the operations of a BST without knowing how they are implemented. (ADT)
Let’s next look at some recursive algorithms for implementing them.

FIND()
f
m
g
j
Desired behaviour:
• find(root, g)returnsthegnode • find(root, s)returnsnull.
c
ae d

FIND() – IMPLEMENTATION
f
m
g
j
find(root, key){ // returns a node if (root == null)
return null
else if (root.key == key))
}
return root
c
ae d

FIND() – IMPLEMENTATION
f
m
g
j
find(root, key){ // returns a node if (root == null)
return null
else if (root.key == key))
return root
else if (key < root.key) return find(root.left, key) else } return find(root.right, key) c ae d FINDMIN() f m g j findMin() should return the node with the smallest key. So, for example given the BST on the left, • findMin(root) returns ... ? c ae d FINDMIN() f m g j findMin() should return the node with the smallest key. So, for example given the BST on the left, • findMin(root)returnstheanode c ae d FINDMIN() f m findMin() should return the node with the smallest key. So, for example given the BST on the left, • findMin(root) returns ... ? c g d e j FINDMIN() f m findMin() should return the node with the smallest key. So, for example given the BST on the left, • findMin(root)returnsthecnode c g d e j FINDMIN() - IMPLEMENTATION f m g j findMin(root){ // returns a node if (root == null) } return null c ae d FINDMIN() - IMPLEMENTATION f m g j findMin(root){ // returns a node if (root == null) return null else if (root.left == null) return root else } return findMin( root.left ) c ae d FINDMAX() f m g j findMax() should return the node with the greatest key. So, for example given the BST on the left, • findMax(root) returns ... ? c ae d FINDMAX() f m g j findMax() should return the node with the greatest key. So, for example given the BST on the left, • findMax(root)returnsthemnode. c ae d FINDMAX() – IMPLEMENTATION f m g j findMax(root){ // returns a node if (root == null) return null else if (root.right == null)) return root else return findMax (root.right) } c ae d ADD() k t m p add(key) should add a BSTNode to the tree. • Where? • How? c ah f ADD() k t m p add(key) should add a BSTNode to the tree. • add(j) ? • add(n) ? A new node is always a leaf. c ah f ADD() k t add(key) should add a BSTNode to the tree. • add(j) ? • add(n) ? A new node is always a leaf. c ah m p f n j ADD() - IMPLEMENTATION k t add(root, key){ // returns root node return root } c ah m p f n j ADD() - IMPLEMENTATION k t add(root, key){ // returns root node if (root == null) root = new BSTnode(key) return root } c ah m p f n j ADD() - IMPLEMENTATION k t add(root, key){ // returns root node if (root == null) root = new BSTnode(key) else if (key < root.key){ root.left = add(root.left,key) return root } c ah m p f n j ADD() - IMPLEMENTATION k t add(root, key){ // returns root node if (root == null) root = new BSTnode(key) else if (key < root.key){ root.left = add(root.left,key) else if (key > root.key){
root.right = add(root.right,key) return root
}
c
ah
m
p
f
n
j
Q: What happens if root.key == key? A: Nothing!

REMOVE()
k
t
m
p
remove(c) 
c
ah f

REMOVE()
remove(c)this is one way to do it kk
ct at
ahm hm fpfp

REMOVE()
remove(c)the following algorithm k does this: k
ct ft
ahm ahm
f
pp

REMOVE() – IMPLEMENTATION
k
t
m
p
remove(root, key){ // returns root node if( root == null )
return null
else if ( key < root.key ) else if ( key > root.key )
else
}
return root }
c
ah f

REMOVE() – IMPLEMENTATION
k
t
m
p
remove(root, key){ // returns root node if( root == null )
return null
else if ( key < root.key ) root.left = remove(root.left, key) else if ( key > root.key )
root.right = remove(root.right, key) else if (root.left == null)
root = root.right
else if (root.right == null)
root = root.left
}
return root }
c
ah
f

REMOVE() – EXAMPLE
remove(k)  k
t
m
p
c a
h f

REMOVE() – EXAMPLE
remove(k)  k
m
t
m
p
cct h ahp
f
a
f

BALANCED VS UNBALANCED
balanced
height=log 𝑛+1 −1 𝑛 = 2h+1 −1
maximally unbalanced height= 𝑛−1

BESTVSWORSTCASE SCENARIO
findMin() findMax() find( key ) add(key) remove(key)
best case
W(1) W(1)
W(1) W(log 𝑛)
W(1)
worst case
O(𝑛) O(𝑛)
O(𝑛) O(𝑛)
O(𝑛)

BESTVSWORSTCASE SCENARIO
findMin() findMax() find( key ) add(key) remove(key)
best case
O(1) W(1)
W(1) W(log 𝑛)
W(1)
worst case
O(𝑛) O(𝑛)
O(𝑛) O(𝑛)
O(𝑛)

BESTVSWORSTCASE SCENARIO
findMin() findMax() find( key ) add(key) remove(key)
best case
O(1) O(1)
W(1) W(log 𝑛)
W(1)
worst case
O(𝑛) O(𝑛)
O(𝑛) O(𝑛)
O(𝑛)

BESTVSWORSTCASE SCENARIO
findMin() findMax() find( key ) add(key) remove(key)
best case
O(1) O(1)
O(1) W(log 𝑛)
W(1)
worst case
O(𝑛) O(𝑛)
O(𝑛) could be zigzag O(𝑛)
O(𝑛)

BESTVSWORSTCASE SCENARIO
findMin() findMax() find( key ) add(key) remove(key)
best case
O(1)
O(1) O(1) O(1)
O(1)
worst case
O(𝑛) O(𝑛)
O(𝑛) O(𝑛) O(𝑛)
Could be zigzag

BINARY SEARCH (TREES)
When a binary search tree is balanced, then finding a key is very similar to a binary search.

BALANCED BINARY SEARCH TREES
(COMP251: AVLTREES,RED-BLACKTREES)
findMin() findMax() find( key ) add(key) remove(key)
best case
O(log 𝑛) O(log 𝑛) O(1) O(log 𝑛) O(log 𝑛)
worst case
O(log 𝑛) O(log 𝑛) O(log 𝑛) O(log 𝑛) O(log 𝑛)

In the next videos:  Heaps

Related Posts