Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

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

25
what does the put method do
associates a value with a key
26
how does the put method work
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
worst case run time of put function
depth + 1
28
what does tree shape depend on
order of insertion
29
what does the best case BST look like
each node has 2 children | balanced
30
what does the minimum function do
returns the smallest key
31
what does the maximum function do
returns the largest key
32
what does the floor function do
finds the largest key that is less than or equal to a given key
33
what does the ceiling key do
finds the smallest key that is greater than or equal to a given key
34
what are the three cases in the method for finding the floor | floor(k)
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
how is the minimum function implemented
follow left links until the one with a null left link
36
how is the maximum function implemented
follow right links until find the one with a null right link
37
what does the rank function do
returns how may keys are less than k
38
what parameters does the rank function take
k
39
what does the select function do
tells us what key has a rank n
40
what parameter does the select function take
int n
41
how to implement rank and select effectivelu
in each node, we store the number of nodes in the subtree rooted at that node
42
how does the rank function work
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
how does the select function work
compare rankings on either side of node | go to side which contains the ranking
44
what does it mean to traverse through a tree
process all the nodes in the tree
45
what are the 3 kinds of traversals of BST
in order pre order post order
46
how does pre order traversal work
1. prints root 2. prints left subtree 3. prints right subtree
47
what is the in order traversal
process left tree until null process the node process the right subtree
48
in what order does the in order traversal print nodes
ascending
49
what is post order traversal
process all of lefr subtree process all of right subtree process node
50
which of the traversals tells us nothing of the structure of the BST
in order traversal
51
what does the delete function take as a parameter
key
52
what are the 3 cases in Hibbard deletion
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
what is the average case time complexity of the delete funtion
sq(N)
54
what determines shape of BST
order of insertion
55
how many worse case trees can be created from an array with N elements
2^n-1 trees
56
what does the size method return
the number of nodes below that node in the subtree
57
trees lean in what direction
left
58
why do we expect a BST to lean to the left
always deletes from right subtree, creating a left spine
59
why is it bad that a BST will start to lean to the left
run times worsen with deletions

Algorithms and Data Structures (19 decks)

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