Trees
No description yet. This curated deck is ready for daily study.
Card preview (22)
Define a tree
A connected undirected graph with no cycles
Define a cycle
A path which starts and ends at the same node
Define connected in the frame of trees
There’s a path from any node to another node and there’s no node disconnected from others
Define undirected in the frame of trees
There is no direction associated with an edge
What’s the root of a tree?
The start node for traversals
What is a tree called if it has a root?
A rooted tree
What is a branch?
A path from the root to an end point
What is the end point of a branch called?
A leaf
What does the height of a tree describe?
The number of edges that connect the root node to the leaf node that is furthest away
What is the E, N equation?
E (number of edges) = N (number of nodes) -1
How are nodes connected in a rooted tree?
By parent-child relationships
What is a binary tree?
A rooted tree where every node has at most 2 child nodes
Why is a binary search tree different from a rooted tree?
It’s ordered to optimise searching
Describe a binary search tree
A rooted tree where the nodes of a tree are ordered If the orders ascending the left nodes have values lower than the root and the right higher
How does an expression tree work?
Leaf nodes contain operands and other nodes contain operators
What are binary trees used for?
Used in compilers to build syntax trees Used in routers to store routing tables Speed up searching
What are expression trees used for?
Representing algebraic and Boolean expressions
What 2 ways can all trees be implemented?
As an adjacency matrix or adjacency list
What other way can a binary tree be implemented?
An array of records
Define the term Pre-order in traversals
Specifies the point in the traversal at which the node content is processed
How does a pre-order traversal work?
Each node is visited before the algorithm traverses either of the nodes subtrees
What is the simplified recursive algorithm for left-right pre-order traversal?
Visit the node Do a pre-order traversal of the nodes left subtree Do a pre-order traversal of the node’s right subtree