4.2.5.1 Trees

Question 1

What is a tree?

Answer 1

A connected undirected graph with no cycles. Connected means that every node is connected to at least one other node. Undirected means there is no direction associated with an edge, i.e. lines are used, not arrows.

Question 2

What is a rooted tree?

Answer 2

A tree in which one vertex has been designed as the root and every edge is directed away from the root.The edges are instead called branches and the nodes without any subnodes are called leaf nodes. Internal nodes are the ones in between

Question 3

What is a binary tree?

Answer 3

Each node is the parent node of at maximum two other nodes. They can be split into left and right subtrees. They can represent the order that mathematical expressions are evaluated.

Question 4

What is a rooted tree used for?

Answer 4

Representing hierarchical data
Storing data in a way that makes it efficiently searchable (see binary search tree and tree traversal)
Representing sorted lists of data

Question 5

How does a binary search tree work?

Answer 5

can sort an unordered list of items into an order. A node is picked the nodes become it’s child nodes.The smaller number goes into the left subtree, the larger goes into the right. The tree can then be searched by starting at the root and if the number to search is larger it will be in the right subtree, like the binary search

Question 6

Describe one example of the use of a Binary Search Tree.

Answer 6

List of elements inserted into tree;
To allow rapid/fast searching of the data;
To output sorted/ordered data;