Brainscape's Knowledge GenomeTM

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


See full index

Data Structures > Trees > Flashcards

Trees Flashcards

1
Q

What type of data structure is a tree?

A

A hierarchical data structure

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

What internal data structure is used in a heap?

A

A queue

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

What is a node?

A

The elements of a data structure

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

What is an edge?

A

The theoretical relationship between a parent and child node

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

What are the two special cases of nodes?

A

root: topmost node
leaf: bottommost node

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

What is the length a measure of?

A

The number of nodes in a path

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

What is the height of a tree?

A

The largest depth(length of path)

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

What is the depth?

A

The length from the root node to the destination

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

What are some common uses for trees?

A
  1. )represent family trees, like genealogy
  2. )represent decision making algorithms
  3. )represent priority queues(as a heap)
  4. )provide fast access to databases(as a b-tree)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is a sub-tree?

A

The tree with a root node that is a descendant of the original root node.

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

What are the descendants of a node?

A

The subsequent children of a given parent node

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

What kind of relationship does a tree have that differs from the predecessor/successor of a list?

A

parent/child relationship

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

What are the requirements for a tree to be considered binary?

A

Each parent node has 2 children, a right and left node

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

What defines pre-order traversal?

A

Root-L-R

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

What defines post-order traversal?

A

L-R-Root

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

What defines level-order traversal?

A

Root-level1-level2-leveln…

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

What defines in-order traversal?

A

L-Root-R

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

What is BST short for?

A

Binary Search tree

19
Q

When is a binary tree a BST?

A

If for every node, the right subtree(k) is greater than the node(k) & the left subtree(k) is smaller

20
Q

Are duplicates allowed in a standard BST?

A

no. The insert makes sure of this by throwing a DuplicateException

21
Q

For the recursive lookup method of a BST, what base cases are there?

A
  1. ) the tree is empty

2. ) the root node has the value we are searching for

22
Q

For the recursive lookup method of a BST, what recursive cases are there?

A
  1. ) visit the right subtree

2. ) visit the left subtree

23
Q

How is the insert method implemented for a BST?

A

It is the same as the lookup method, but after finding the desired position it is added as a child of the parent

24
Q

What three cases have to be considered when deleting a node in a BST?

A

The node to delete has:

  • 1 node
  • 2 nodes
  • no nodes(is a leaf)
25
Q

What does the complexity of the lookup method depend on in a BST?

A

The combination of inserts/delete that shape the graph

26
Q

What BST will yield a faster lookup?

A

A bulkier tree that is more balanced O(log N), whereas more linear trees will yield a complexity closer to O(N)

27
Q

What are some examples of balanced trees?

A

AVL, 2-4, b-trees & red-black trees

28
Q

What fields does a treeNode have?

A

data, child node pointers. These are set to null when there’s less than the maximum amount

29
Q

When deleting a node from a BST, what is the n node replaced with for all three cases?

A

0: set parent to null
1: set parent to n
2: set n to numerically adjacent node (right subtree far left)

30
Q

What represents a priority queue?

A

A heap

31
Q

What type is a heap?

A

a class of binary tree with the ORDER and SHAPE property

32
Q

What is the order property?

A

All children nodes are smaller than their parent nodes

33
Q

What is the shape property?

A

All leaves are at the last or second to last level

All leaves at the bottom level are as far left as possible

34
Q

What is implied if the shape property is true?

A

The tree is complete

35
Q

What is a full tree?

A

where the d-1 level all have two children and all interior nodes are not null

36
Q

For an array implementation of a heap, where is the root node?

A

array[1]

37
Q

If a node is on array[k], where is the left node 1 & right node?

A

array[2k] & array[2k + 1], respectively

38
Q

Where does the insert operation add a node to a heap?

A

@ the end of the array i.e. the bottom level to the right.. Then swap parents until the order property is satisfied

39
Q

What is the largest value in a heap?

A

The root

40
Q

How does the removeMax operation work?

A

replaces root with the array[last], then swaps with the largest child until order property is satisfied

41
Q

What complexity are the methods of a heap?

A

O(log N)

42
Q

Is a heap balanced?

A

yes

43
Q

When is a tree height balanced?

A

When the right and left trees are balanced and their leaves are at levels that differ no more than 1

Data Structures (7 decks)

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