Week 7: Trees and Heaps

Question 1

What are the main properties of trees in general?

Answer 1

Miller and Ranum first introduce the tree data structure, giving examples from biology (a taxonomy) and computing (a file system and a web page). They note three properties of trees:

a. they are hierarchical
b. children of one tree node are independent of the children of another
c. leaf nodes are unique.

Question 2

In computing, what is a tree?

Answer 2

They offer two possible definitions of a tree in computing, one based on the concepts of nodes and edges, the other recursive.

Note that according to both the nodes and edges definition and the recursive definition of a tree, a tree can be empty. For the recursive definition of a tree, this is obvious. It states explicitly that trees can be empty. At first sight, the nodes and edges definition seems to exclude the possibility of an empty tree. After all, Miller and Ranum’s Definition One says that ‘One node of the tree is designated as the root node’. In fact, this formulation is misleading: it should really say: ‘One node of the tree, if the tree is non-empty, is designated as the root node’. In terms of nodes and edges, the empty tree is represented by an empty set of nodes with an empty set of edges.

Question 3

What is a binary tree?

Answer 3

In doing so, they introduce an important special case of a tree: the binary tree – a tree in which each node has a maximum of two children.

Question 4

What is the definition for a node?

Answer 4

A node is a fundamaental part of a tree. It can have a name, which we call the ‘key’. A node may also have additional infomration. we call this the ‘payload’ While the payload information is not central to many tree algorithms, it is often critical in applications that make use of trees.

Question 5

What is the definition for an Edge?

Answer 5

an edge is another fundamental part of a tree. an edge connects two nodes to show that there is a relationship between them. every node (except the root) is connected by exactly one incoming edge from another node. each node may have several outgoing edges.

Question 6

What is the definition for a root?

Answer 6

the root of the tree is the only node in the tree that has no incoming edges.

Question 7

What is the definition for a Path?

Answer 7

A path is an ordered list of nodes that are connected by edges.

Question 8

What is the definition for Children?

Answer 8

The set of nodes c that have incoming edges from the same node to are said to be the children of that node

Question 9

What is the definition for a Parent?

Answer 9

A node is the parent of all the nodes it connects to with outgoing edges

Question 10

What is the definition for a sibling

Answer 10

Nodes in the trees that are children of the same parent are said to be siblings.

Question 11

What is the definition for a subtree

Answer 11

A subtree is a set of nodes and edges comprised of a parent and all the decendants of that parent.

Question 12

What is the definition for a leaf node

Answer 12

A leaf node is a node that noc hildren

Question 13

What is the definition for a level?

Answer 13

the level of a node is the number of edges on the path from the root node to n.

Question 14

What does it mean to transverse a tree?

Answer 14

Traversing a tree simply means visiting every node in it. The difference between the three modes of traversal that Miller and Ranum present is simply the order in which they are visited.

Question 15

What forms of tree traversal are available?

Answer 15

Three ways of traversing a tree are presented: preorder, postorder and inorder. There are many videos and visualisations of these types of traversal available on the web; you might want to search for some of these yourself.

Question 16

What is the difference between what Miller and Ranum call (internal) methods and external functions of tree traversal? Why does the function in Listing 6.12 (an internal method) have the parameter self whereas those in Listings 6.13 and 6.15 (external functions) have the parameter tree?

Answer 16

An external function is a piece of client code – not a part of the tree data structure – that uses the methods of the tree to perform the traversal. Listings 6.11, 6.13 and 6.15 are all external functions, and so have tree (i.e. a reference to the tree) as parameters; they can access the methods of the tree through this reference. By contrast, an (internal) method is simply a method of the class BinaryTree itself. If such a method is provided, client code can then ask the tree to do (for instance) a preorder traversal of itself, using its own methods. Listing 6.12 is a method, and so has self (i.e. the tree itself) as a parameter.

Question 17

What is a complete binary tree?

Answer 17

its a tree in which each level has all of its nodes. The exception to this is the bottom level of the tree, which we fill in from left to right.

Question 18

What is a binary heap? How is it similar to, and different from, a binary tree?

Answer 18

Miller and Ranum introduce a special case of the complete binary tree: the binary heap. This is a complete binary tree with a special structure rule – the heap order property – for the ordering of parents and children. The authors show how the tree can be implemented in Python using a list.

Question 19

State the structure property of a binary heap described by Miller and Ranum. How does it differ from a plain binary tree?

Answer 19

As with any binary tree, a binary heap is a tree in which every parent node has at most two children. A binary heap has two further properties:

It is a complete binary tree (the heap structure property). This means that every level of the tree has its maximum number of nodes, apart from the lowest level, into which new leaf nodes are added left to right.
It has an ordering rule (the heap order property) which states that for every node x with parent p, p will be smaller than or equal to x.

Question 20

Look back over the unit and note down what you thought were the main ideas covered.

Answer 20

Sorting is one of the most common problems in computer science. We offered a formal definition of this problem.
We introduced three straight sorting algorithms: bubble sort, insertion sort and selection sort, with an analysis of their complexity, and a brief account of one of the attempts that has been made to improve their performance.
We then took a detour into mathematics, presenting the technique of proof by induction, in which a proof can be built up from a base case and an induction step.
Intimately related to induction is the computational technique of recursion. We covered recursion in some detail and worked out a recursive version of insertion sort.
Next, we considered sorting algorithms that are cleverer than the straight sorting operations previously discussed. Two examples were offered: merge sort and quick sort. Both of these are divide-and-conquer algorithms, which lend themselves to a recursive treatment.
Some problems can be solved computationally by transforming the input into a form that better lends itself to the processing necessary. As an example of this, we considered heap sort, in which a linear sequence to be sorted is first transformed into a special data type known as a heap.
Finally, we reviewed sorting, arguing that no sorting algorithm can improve on O(n log n). We also looked at Timsort, a very fast algorithm that employs heuristics to improve speed.