Trees Flashcards
(20 cards)
What is a tree data structure?
A specialised form of undirected graph with exactly one path between two nodes used to model hierarchical relationships.
What are the features of a tree?
- Undirected
- Unweighted
- Fully connected
- Acyclical
What is a binary tree?
A type of rooted tree where each node can have at most two children.
What are the uses of trees?
- Building efficient searching and sorting algorithms
- Storing data that has a hierarchical structure
- Processing syntax in natural and programming languages
- Implementing probability and decision trees
Why are trees well suited for recursion?
They are a recursive data type such that each child node can be the root of a separate tree.
What is a rooted tree?
Tree where
- One node is designated as the root which has no parents
- All nodes can be described as a parent or child node
- Direction of hierarchy often shown by arrows
What are the features on a rooted tree?
- Root node: has no parent
- Child and Parent nodes
- Edges/Branches
- Leaf node: has no children
What is a binary search tree?
A type of binary tree where a particular method is used to insert new node in an optimal location for later search/retreival
What are Binary Search Trees used for?
Provide an efficient way of searching for items as well as providing an effective way of returning all items in the correct order.
What are the key operations of a tree?
- Add nodes
- Get child nodes
- Getting a subtree
- Searching for a node
- Determining the height of the tree
What is the height of a tree?
The number of edges along the longest path from the root to the furthest leaf node.
What are the uses of a pre-order traversal?
- Copying a tree
- Evaluating mathematical expressions using prefix notation
What are the uses of an in-order traversal?
- Outputting the contents of a binary tree in ascending order
What are the uses of a post-order traversal?
- Converting mathematical expressions from infix to postfix notation (Reverse Polish)
- Producing a postfix expression from an expression tree
- Deleting a tree
- Completing dependant processes in order
What is an expression tree?
A tree that represents a mathematical expressions evaluated using post-order traversals.
What it Reverse Polish Notation?
An alternate means of writing mathematical expressions using postfix notation
What is infix notation?
The operator sits between the operands
What is postfix notation?
Operator comes after operands
What are the benefits of Reverse Polish Notation?
- Simplifies mathematical expressions by eliminating the need for brackets as order is implied by notation
- More easily evaluated by stack-based interpreters
What are some properties of stack-based interpreters?
- Translate and execute program code line-by-line
- Invoke pre-complied subroutines to perform the line being translated
