Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algorithms and Data Structures > Binary Search Tree (1) > Flashcards

Binary Search Tree (1) Flashcards

1
Q

what is a binary search tree

A

a binary tree in symmetric order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

what does the symmetric order property of a binary search tree mean

A

each node’s key is:

larger than all the keys in its left subtree
smaller than all the keys in its right subtree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

what is a leaf of a tree

A

a node with no children

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

what is the height of a BST

A

the maximum number of links from the root to a leaf

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

what is a level of a BST

A

the maximum number of nodes from the root to a leaf (includes the root and leaf)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

what is the size of a BST

A

number of nodes in the tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

what is the depth of a BST

A

number of links from the root to the node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

at most, how often does every key appear in a BST

A

once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

every node must have at most how many parents

A

1

the root has 0
the rest have 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

generally what is the number of levels in a BST

A

height + 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

in general, how do we search through a BST

A

currentNode = root
if key we are searching for is less than the currentNode, go left
if the key we are searching for is greater than the currentNode, go right
if the key we are searching for is equal to the key in the currentNode, return

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

in general, how do we insert into a BST

A

search for the key we want to insert
if found: do nothing
else: create a new node in the space where the search finished

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

what does the BST java definition reference

A

the root node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

what are the four values that a BST node is composed on

A

key
value
left ref
right ref

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

which of the fields in the node of the BST should be comparable

A

key

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

the types key and value in the BST node are …

A

generic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

what does the get function do

A

return value corresponding to given key

or null if no such key

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

how does the get function work

A

while the node is not null
if the key we are looking for is less than the given key go left
if the key we are looking for is greater than the given key go right
else if the keys are equal, return the value of that node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

what parameter does the get function take

A

key

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

what is the runtime cost of get

A

1 + depth

so depth as we ignore constant

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

what is the worst case input for get

A

asking to get an element that is not in the tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

the get method is the only method that doesn’t use …

A

recursion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

what is the worst possible arrangement of a binary search tree, or any tree

A

when it looks more like a linked list (each node has either 0 or 1 children)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

what is the worst case height of a binary search tree

A

N-1

25
Q

what does the put method do

A

associates a value with a key

26
Q

how does the put method work

A

search for the key

if the key is in the tree, reset its value
if the key is not in the tree, add a new node

27
Q

worst case run time of put function

A

depth + 1

28
Q

what does tree shape depend on

A

order of insertion

29
Q

what does the best case BST look like

A

each node has 2 children

balanced

30
Q

what does the minimum function do

A

returns the smallest key

31
Q

what does the maximum function do

A

returns the largest key

32
Q

what does the floor function do

A

finds the largest key that is less than or equal to a given key

33
Q

what does the ceiling key do

A

finds the smallest key that is greater than or equal to a given key

34
Q

what are the three cases in the method for finding the floor

floor(k)

A

CASE 1:
k equals the key in the node

CASE 2:
floor of k is in the left subtree

CASE 3:
Floor of k is in the right subtree (if there is any key <= k in the right subtree) otherwise it is the key in the node

35
Q

how is the minimum function implemented

A

follow left links until the one with a null left link

36
Q

how is the maximum function implemented

A

follow right links until find the one with a null right link

37
Q

what does the rank function do

A

returns how may keys are less than k

38
Q

what parameters does the rank function take

A

k

39
Q

what does the select function do

A

tells us what key has a rank n

40
Q

what parameter does the select function take

A

int n

41
Q

how to implement rank and select effectivelu

A

in each node, we store the number of nodes in the subtree rooted at that node

42
Q

how does the rank function work

A

count what’s in the left subtree and in the left tree of the parent (as these are all definitely less) using recursion
add one for the parent

43
Q

how does the select function work

A

compare rankings on either side of node

go to side which contains the ranking

44
Q

what does it mean to traverse through a tree

A

process all the nodes in the tree

45
Q

what are the 3 kinds of traversals of BST

A

in order
pre order
post order

46
Q

how does pre order traversal work

A
  1. prints root
  2. prints left subtree
  3. prints right subtree
47
Q

what is the in order traversal

A

process left tree until null
process the node
process the right subtree

48
Q

in what order does the in order traversal print nodes

A

ascending

49
Q

what is post order traversal

A

process all of lefr subtree
process all of right subtree
process node

50
Q

which of the traversals tells us nothing of the structure of the BST

A

in order traversal

51
Q

what does the delete function take as a parameter

A

key

52
Q

what are the 3 cases in Hibbard deletion

A

case 0: node we want to delete has 0 children (delete by setting parent link to null)

case 1: node we want to delete has 1 child (delete by replacing parent link)

case 2: node we want to delete has 2 children (find successor node, delete it from subtree and replace in space of node we want to delete)

53
Q

what is the average case time complexity of the delete funtion

A

sq(N)

54
Q

what determines shape of BST

A

order of insertion

55
Q

how many worse case trees can be created from an array with N elements

A

2^n-1 trees

56
Q

what does the size method return

A

the number of nodes below that node in the subtree

57
Q

trees lean in what direction

A

left

58
Q

why do we expect a BST to lean to the left

A

always deletes from right subtree, creating a left spine

59
Q

why is it bad that a BST will start to lean to the left

A

run times worsen with deletions

Algorithms and Data Structures (19 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions