Data Structures - Trees Flashcards
What is the definition of a tree?
Trees are a type of data structure consisting of a non-empty collection of nodes and edges which may carry properties.
What is the definition of a node?
A node is an object that has a name - normally with some information associated with it.
What is the definition of an edge?
An edge is a connection between two nodes.
This can also have information associated with it - for example, in neural networks, edges have their own weight attached to them.
What is the definition of a path?
A path is a sequence of adjacent nodes connected by edges.
What is the definition of a rooted tree?
A rooted tree is a tree where one element is designated as the “root” of that tree.
They are the most common form of a tree in computer applications, so much so that sometimes it is worth just referring to them as a “tree” themselves.
What is meant by a “forest” of trees?
A forest of trees is a disjoint set of trees. This means that two or more separate trees exist within the set.
What is meant by the “parent”, “child” and “siblings” of a rooted tree?
A node’s “parent” is the node immediately above this node.
A node’s “child” is each adjacent node below this node.
A node’s “siblings” are all other nodes connected to its parent.
Note that nodes with no children are called “leaves”.
What is meant by an “M-ary tree”, where M is a positive integer?
An M-ary tree is a tree where each node has a maximum number of children equal to M.
For example, a Binary Tree is a special type of M-ary tree where all nodes have at most 2 children. Hence, they are simply 2-ary trees.
What is the “level” of a node, and subsequently what is the “height” of the entire tree?
The level of a node is one higher than the level of its parent. For example, a child of the node with level 11 would be level 12.
The height of the whole tree is the maximum level of all of its nodes EXACTLY. For example, if a tree consists only of the root at level 0, then the height will also be 0.
If a rooted tree consists only of its root, would its height be 0 (exact node level) or 1 (numeric height)?
0, as a tree’s height is EXACTLY its maximum level.
What is a full binary tree?
A full binary tree is one in which all the nodes EXCEPT THE LEAVES have exactly two children.
In other words, they have either two children, or no children.
What is meant by a binary tree being “complete”?
A complete binary tree is one such that all levels except possibly the last are completely full, and the last level has all of its nodes to the left side.
So, every level of nodes has 0 or 2 children, and for the last level in the tree, all of its nodes are on the left subtree of the root node.
How may we implement a binary tree using an array?
We start from the topmost number (the root node) with 1, then move down the levels and number the nodes with 2 and 3, starting from the left.
This is an easyway to do it, as the numbering can be used as indexes in an array representation.
For example:
Z F S G J H Q X C
0 1 2 3 4 5 6 7 8 9
What is a binary search tree?
A BST is a binary tree where the nodes are organised such that…
All elements in the left subtree of a node are LESS than the node, and
all elements in the right subtree of a node are GREATER than the node.
Note that obviously, BSTs do not support repeated elements, as there is no way to classify whether 12 should be considered greater or less than 12.
What benefits do Binary Search Trees provide?
When they are balanced, BSTs provide blazing fast searches, at speeds of around O(h), where h is the height of the tree.
It is important to note that tree height is normally O(log n) to be randomly generated, meaning that we can search through n elements in logarithmic time.
To put into perspective how big this is, we could search through 1 million elements in under 20 operations!
