Course week 13¶

Self-study¶

The topics for this week are the following: (i) Binary search trees, (ii) Balanced binary search trees

The following links will take you to the video-lectures and the accompanying slides:

Binary search trees¶

Video_en (part 1)

Video_en (part 2)

slides

Balanced binary search trees¶

Binary search trees¶

Question 1

Suppose all the keys in a binary search tree (BST) are unique. Let \(x\) and \(y\) be two nodes in the BST whose keys are \(x.key\) and \(y.key\). Which of the following statements are always true? (More than 1 statement may be true.)

If \(y.key < x.key\), then \(y\) is the left child of \(x\).

If \(y.key < x.key\), then \(y\) is in the left subtree of \(x\).

If \(y\) is in the left subtree of \(x\), then \(y.key < x.key\).

If \(y\) is in the left subtree of \(x\), then \(y.key > x.key\).

If \(y\) is further away from the root than \(x\), then node \(y\) is in one of the subtrees of node \(x\).

If \(y.key < x.key\) and \(x\) is the root, then \(y\) is in the left subtree of \(x\).

Question 2

Suppose all the keys in a binary search tree (BST) are unique. When searching for a particular \(k\) key using a standard BST search algorithm, the algorithm reaches a leaf \(x\). Which of the following is true?

The key of \(x\) is equal to \(k\).

There is no node in the BST whose key is \(k\).

If there is a node in the BST whose key is \(k\), then it is node \(x\).

If the key of \(x\) is not equal to \(k\), then the search must continue by starting from the root of the BST and searching in the subtree that does not contain \(x\).

Question 3

To obtain all the keys of a binary search tree in ascending order …

… we can use a breadth first search.

… we can use Dijkstra’s algorithm.

… we can use an inorder traversal.

… we can use a postorder traversal.

Question 4

Suppose all the keys in a binary search tree (BST) are unique and we want to insert a new node having key \(k\) into the BST using the standard insert algorithm. What can be said about the position of the new node?

If \(k\) is less than the key of the root, then the new node will always be a left child.

If \(k\) is less than the key of the key of some leaf, then the new node will always be a left child.

If the existing BST has at least 2 nodes and \(x\) is the parent of the new node, then after inserting the new node \(x\) will have exactly 2 children.

The new node will always be a leaf.

Question 5

Suppose all the keys in a binary search tree (BST) are unique and let the tree have at least 1000 nodes. Let \(x\) be a leaf in the BST whose key is \(x.key\). If a new node \(y\) having key \(y\) is being inserted, which of the following claims is true?

If \(y.key < x.key\), then inserting node \(y\) as the left child of \(x\) will always yield a valid BST.

If \(y.key < x.key\), then inserting node \(y\) as the right child of \(x\) will always yield a valid BST.

If \(y.key < x.key\), then inserting node \(y\) as the right child of \(x\) will never yield a valid BST.

If \(y.key < x.key\) and \(x.key\) is the smallest key in the BST, then inserting node \(y\) as the left child of \(x\) will never yield a valid BST.

Balanced binary search trees and the efficiency of binary search tree operations¶

Question 1

Suppose a binary search tree (BST) has been formed by adding \(n\) nodes to an empty BST and \(n > 1000\). In addition suppose that we are performing a search for a key that does not occur in the BST. The worst case runtime efficiency for such a search is linear in \(n\). Which of the following properties does not correspond to a BST having this worst case runtime efficiency?

A BST where the number of nodes which have have 2 children is as large as possible.

A BST whose height is as large as possible for the given \(n\).

A BST where each node has at most one child.

A BST which has only one leaf.

Question 2

Suppose a rotation is performed on BST \(B1\) with the result being BST \(B2\). Which of the following is not a possible consequence of the rotation?

A right subtree of some node in \(B1\) becomes the left subtree of some other node in \(B2\).

When node \(u\) was the parent of node \(v\) in \(B1\), node \(v\) becomes the parent of node \(u\) in \(B2\).

For all nodes \(u\), the distance of \(u\) from the root in \(B2\) is less than the distance of \(u\) from the root in \(B1\).

The height of \(B2\) is less than the height of \(B1\).

Question 3

Which of the following is not true for an AVL binary search tree?

One or more rotations might be used when inserting a new node into an AVL binary search tree.

Let \(x\) be a node in an AVL binary search tree. The difference in the heights of the left and right subtrees of \(x\) is at most 1.

Let \(x\) be a node in an AVL binary search tree and \(y\) be a leaf in some subtree of \(x\). The distance of any leaf \(y\) from node \(x\) is always the same value.

Let \(x\) be a node in an AVL binary search tree. Some data must be stored at \(x\) from which we can get the difference in the heights of the left and right subtrees.

Question 4

Suppose a binary search tree (BST) has been formed by adding \(n\) nodes to an empty BST and \(n > 1000\). Consider two alternatives: (I) in forming the BST nothing special is done to try to keep it balanced, (II) the BST is formed using either an AVL or a red-black BST. What advantage do we gain by in using alternative (II)?

We avoid the possibilty that the runtime efficiency of a search operation is linear in \(n\).

We ensure that the difference between the depth of any two leaves is at most 1.

We ensure that the height of the BST is as small as possible.

We ensure that in the BST there is at most one node that has precisely one child.

Question 1

What is a central question, related to this course, whose answer can be found in this week’s videos?

Question 2

Of the following topics, which do you think deserves further discussion/explanation during the weekly consultation session?

What is a binary search tree

Rotations done in a binary search tree

AVL binary search trees

Red-black binary search trees

Question 3

Were there any parts of the video lectures that were particularly difficult? Particularly interesting? Something about which you wish to learn more?

Extra links on the topic:

A site where you can visualize operations on binary search trees

Week13 - Glossary

Submit weekly exercises¶

Questions to be submitted this week