Trees Flashcards
What type of data structure is a tree?
A hierarchical data structure
What internal data structure is used in a heap?
A queue
What is a node?
The elements of a data structure
What is an edge?
The theoretical relationship between a parent and child node
What are the two special cases of nodes?
root: topmost node
leaf: bottommost node
What is the length a measure of?
The number of nodes in a path
What is the height of a tree?
The largest depth(length of path)
What is the depth?
The length from the root node to the destination
What are some common uses for trees?
- )represent family trees, like genealogy
- )represent decision making algorithms
- )represent priority queues(as a heap)
- )provide fast access to databases(as a b-tree)
What is a sub-tree?
The tree with a root node that is a descendant of the original root node.
What are the descendants of a node?
The subsequent children of a given parent node
What kind of relationship does a tree have that differs from the predecessor/successor of a list?
parent/child relationship
What are the requirements for a tree to be considered binary?
Each parent node has 2 children, a right and left node
What defines pre-order traversal?
Root-L-R
What defines post-order traversal?
L-R-Root
What defines level-order traversal?
Root-level1-level2-leveln…
What defines in-order traversal?
L-Root-R
What is BST short for?
Binary Search tree
When is a binary tree a BST?
If for every node, the right subtree(k) is greater than the node(k) & the left subtree(k) is smaller
Are duplicates allowed in a standard BST?
no. The insert makes sure of this by throwing a DuplicateException
For the recursive lookup method of a BST, what base cases are there?
- ) the tree is empty
2. ) the root node has the value we are searching for
For the recursive lookup method of a BST, what recursive cases are there?
- ) visit the right subtree
2. ) visit the left subtree
How is the insert method implemented for a BST?
It is the same as the lookup method, but after finding the desired position it is added as a child of the parent
What three cases have to be considered when deleting a node in a BST?
The node to delete has:
- 1 node
- 2 nodes
- no nodes(is a leaf)
What does the complexity of the lookup method depend on in a BST?
The combination of inserts/delete that shape the graph
What BST will yield a faster lookup?
A bulkier tree that is more balanced O(log N), whereas more linear trees will yield a complexity closer to O(N)
What are some examples of balanced trees?
AVL, 2-4, b-trees & red-black trees
What fields does a treeNode have?
data, child node pointers. These are set to null when there’s less than the maximum amount
When deleting a node from a BST, what is the n node replaced with for all three cases?
0: set parent to null
1: set parent to n
2: set n to numerically adjacent node (right subtree far left)
What represents a priority queue?
A heap
What type is a heap?
a class of binary tree with the ORDER and SHAPE property
What is the order property?
All children nodes are smaller than their parent nodes
What is the shape property?
All leaves are at the last or second to last level
All leaves at the bottom level are as far left as possible
What is implied if the shape property is true?
The tree is complete
What is a full tree?
where the d-1 level all have two children and all interior nodes are not null
For an array implementation of a heap, where is the root node?
array[1]
If a node is on array[k], where is the left node 1 & right node?
array[2k] & array[2k + 1], respectively
Where does the insert operation add a node to a heap?
@ the end of the array i.e. the bottom level to the right.. Then swap parents until the order property is satisfied
What is the largest value in a heap?
The root
How does the removeMax operation work?
replaces root with the array[last], then swaps with the largest child until order property is satisfied
What complexity are the methods of a heap?
O(log N)
Is a heap balanced?
yes
When is a tree height balanced?
When the right and left trees are balanced and their leaves are at levels that differ no more than 1
