Trees Flashcards
What is a Node?
- The elements of the tree
- Each node contains a key which uniquely identifies that node
What is an Edge?
The link/connection between nodes
What is unique about the root node?
It has no parent
What are leaf nodes?
Nodes that have no child
What is a Path?
A sequence of nodes connected by edges
How is the length of a path determined?
Determined by the number of nodes in the path (including start and end nodes)
What is a Parent node?
The unique predecessor of every node
What is a Child node?
The successor to a parent node
What are Sibling nodes?
Nodes that have a common parent
What is the Level of a node?
- The number of nodes between this node and the root node
- Calculated using the shortest path to the root node
What is the height of a tree?
The height is determined by the highest level node
What are Sub-trees?
- A Sub-tree is formed using a parent node and all of it’s descendants.
- The parent node becomes the root node of the Sub-tree.
What is the difference between a Strictly Binary Tree and a Knuth Binary tree?
- Each node in a Strictly Binary tree has either 0 or 2 sub-trees
- Each node in a Knuth Binary Tree can have 0, 1 or 2 sub trees
What 3 qualities make Trees a recursive data structure?
- The data of the node itself
- A reference to the left child node (can be null)
- A reference to the right child node (can be null)
What makes a tree balanced?
All leaf nodes have the same level
What is a Breadth-first traversal?
Returns the data of each node level by level
(e.g. returns all nodes at level 1, then level 2, etc.)
What is the procedure for a Depth first Pre-order traversal?
- Process current node
- Traverse to left sub-tree
- Return to parent node
- Traverse to right sub-tree
- Return to parent node
-Process, Left, Right or P, L, R
What is the procedure for a Depth first In-order traversal?
- Visit current node
- Traverse to left sub-tree
- Process current node
- Traverse to right sub-tree
- Return to parent node
- Left, Process, Right or LPR
What is the procedure for a Depth first Post-order traversal?
- Visit current node
- Traverse to left sub-tree
- Visit current node
- Traverse to right sub-tree
- Process current node
- Return to parent node
- Left, Right, Process or LRP
What is a Binary Search Tree (BST)?
- A Binary Tree that is ordered so that, starting at the root, when we search for a node we always know which sub tree to search in
- This mean the maximum number of comparisons = height of tree
How is a BST organised?
- The values in the left sub-tree are always less than the parent
-The values in the right sub-tree are always greater than the parent
What is the worst-case and best-case time complexity of searching a BST?
- Worst case: O (n) when every parent node only has one child
- Best case: O (log n) when every parent node has 2 children
What type of traversal is needed to return an ordered list of items from a BST?
Depth first in-order traversal
What is a Full Binary tree?
A binary tree where every level of the tree has the maximum possible number of nodes
What is a B-Tree?
(not a binary tree)
A tree where nodes contain multiple key values, and have multiple children
What are the benefits of a B-Tree?
- Can be efficiently stored in files and memory
- Minimise disk reads ( complexity of O (log n)
What are the applications of a B-Tree?
- Suitable for datasets that are too large to fit in main memory
- Useful for databases and file systems
What are the limitations of a B-Tree?
- Often half empty (inefficient use of space)
- Sequential access requires revisiting nodes
What is the degree/order of a B-Tree?
The order (M) of a B-Tree is the maximum number of children allowed per parent
How many children does each node of a B-Tree have?
Between M and M/2 with M being the order of a B-Tree
How many key values do parents have in a B-Tree?
- Number of children -1
- So for a parent with 4 children, it would have 3 key values
Describe the Node splitting method
- When a node is full (M elements), split into two nodes at the same level as the original node
- Put the smallest elements into the left node
- Put the largest elements into the right node
- Insert the middle element into the parent node
- If no parent node exists, create a new root node and insert the middle element
How do you convert this infix expression:
(A + B) * C - D / E
into a prefix expression?
- (A + B) = AB+
- (A + B) * C = AB+C*
- D / E = DE/
AB+C*DE/-
Why are expressions converted into prefix forms?
- Can be processed with a single left to right pass
- Easier to build an expression tree
How are expression trees formatted?
- Parent node will be the operator
- Child nodes will be the two elements being processed
e.g. the parent node could be + and the child nodes would be the element A, and the subtree B*C (will be processed recursively)
How is a modified in-order traversal used to evaluate an expression tree?
- IF parent node, then print (
- Left
- Process
- Right
- IF parent node, print )
How is a post order traversal used to evaluate an expression tree?
- Left, Right, Process
- Using a stack data structure means we don’t need parentheses
e.g. ABCD-+ will return:
C-D, B(C-D), A+B*(C-D)
