MOD 7_ZYBOOKS 9_BINARY SEARCH TREES

Question 1

What is a binary tree?

What is a left child and a right child?

Answer 1

In a list, each node has up to one successor. In a binary tree, each node has up to two children, known as a left child and a right child. “Binary” means two, referring to the two children.

Question 2

Provide definitions for:
- Leaf
- Internal node
- Parent, ancestors
- Root

Answer 2

Question 3

Provide definitions for:
- Edge
- Depth
- Level
- Height

Answer 3

Question 4

What are the 3 special types of binary trees?

Answer 4

Question 5

VIEW: Special types of binary trees: full, complete, perfect

Answer 5

Question 6

Trees are commonly used to represent ____ data. A tree can represent files and directories in a file system, since a file system is a hierarchy.

Answer 6

Hierarchical

Question 7

What is Binary Space Partitioning (BSP)?

What is a BSP tree?

Answer 7

Binary space partitioning (BSP) is a technique of repeatedly separating a region of space into 2 parts and cataloging objects contained within the regions. A BSP tree is a binary tree used to store information for binary space partitioning. Each node in a BSP tree contains information about a region of space and which objects are contained in the region.

Question 8

In graphics applications, a ____ tree can be used to store all objects in a multidimensional world. It can then be used to efficiently determine which objects must be rendered on screen.

The viewer’s position in space is used to perform a lookup within this tree. The lookup quickly eliminates a large number of objects that are not visible and therefore should not be rendered.

Answer 8

BSP

Question 9

VIEW: Using trees to store collections

Answer 9

Question 10

What is a Binary Search Tree (BST)?

Answer 10

An especially useful form of binary tree is a binary search tree (BST), which has an ordering property that any node’s left subtree keys ≤ the node’s key, and the right subtree’s keys ≥ the node’s key. That property enables fast searching for an item, as will be shown later.

Question 11

VIEW: BST ordering property: For three nodes, left child is less-than-or-equal-to parent, parent is less-than-or-equal-to right child. For more nodes, all keys in subtrees must satisfy the property, for every node.

Answer 11

Question 12

To ____ nodes means to find a node with a desired key, if such a node exists. A ____ may yield faster searches than a list - this starts by visiting the root node (which is the first currentNode below).

Answer 12

Search
BST

Question 13

With a BST, if a ____ to be visited doesn’t exist, the desired node does not exist. With this approach, only a small fraction of nodes need be compared.

Answer 13

Child

Question 14

VIEW: BST search runtime

Answer 14

Question 15

VIEW: Minimum binary tree heights for N nodes are equivalent to log_2(N)

Answer 15

Question 16

What is a BST node successor and predecessor?

Answer 16

A BST defines an ordering among nodes, from smallest to largest. A BST node’s successor is the node that comes after in the BST ordering, so in A B C, A’s successor is B, and B’s successor is C. A BST node’s predecessor is the node that comes before in the BST ordering.

If a node has a right subtree, the node’s successor is that right subtree’s leftmost child: Starting from the right subtree’s root, follow left children until reaching a node with no left child (may be that subtree’s root itself). If a node doesn’t have a right subtree, the node’s successor is the first ancestor having this node in a left subtree. Another section provides an algorithm for printing a BST’s nodes in order.

Question 17

Given a key, a ____ algorithm returns the first node found matching that key, or returns ____ if a matching node is not found.

A simple ____ search algorithm checks the ____ node (initially the tree’s root), returning that node as a match, else assigning that node with the left (if key is less) or right (if key is greater) child and repeating. If such a child is null, the algorithm returns null (matching node not found).

Answer 17

Search, null

BST, current

Question 18

How does a BST insert operation work?

Answer 18

Question 19

VIEW: BST insert algorithm complexity

Answer 19

Question 20

How does a BST remove operation work?

The algorithm performs which 3 sub-algorithms?

Answer 20

Question 21

VIEW: BST remove algorithm.

Answer 21

Question 22

VIEW: BST remove algorithm complexity

Answer 22

Question 23

What is a tree traversal algorithm?

What is an inorder traversal?

Answer 23

A tree traversal algorithm visits all nodes in the tree once and performs an operation on each node. An inorder traversal visits all nodes in a BST from smallest to largest, which is useful for example to print the tree’s nodes in sorted order. Starting from the root, the algorithm recursively prints the left subtree, the current node, and the right subtree.

Question 24

VIEW: BST inorder traversal algorithm

Answer 24

Question 25

Describe BST height and insertion order.

Answer 25

Question 26

Given a node representing a BST subtree, the height can be computed as?

Answer 26

Question 27

A ____ implementation often includes a parent pointer inside each node. A ____ BST, such as an AVL tree or red-black tree, may utilize the parent pointer to traverse up the tree from a particular node to find a node's parent, grandparent, or siblings.

Question 28

VIEW: BSTInsert algorithm for BSTs with nodes containing parent pointers.

Answer 28

The BST insertion and removal algorithms below insert or remove nodes in a BST with nodes containing parent pointers.

Question 29

VIEW: BSTReplaceChild algorithm.

Answer 29

Question 30

VIEW: BSTRemoveKey and BSTRemoveNode algorithms for BSTs with nodes containing parent pointers.

Answer 30

Question 31

Explain how BST search can be implemented using recursion.

Answer 31

BST search can be implemented using recursion. A single node and search key are passed as arguments to the recursive search function. Two base cases exist. The first base case is when the node is null, in which case null is returned. If the node is non-null, then the search key is compared to the node's key. The second base case is when the search key equals the node's key, in which case the node is returned. If the search key is less than the node's key, a recursive call is made on the node's left child. If the search key is greater than the node's key, a recursive call is made on the node's right child.

Question 32

How does a recursive BST get-parent algorithm search for a parent?

Answer 32

A recursive BST get-parent algorithm searches for a parent in a way similar to the normal BST search algorithm. But instead of comparing the search key with a candidate node's key, the search key is compared with the keys of the candidate node's children.

Question 33

VIEW: BST get parent algorithm.

Answer 33

Question 34

How can BST insertion and removal be implemented using recursion?

Answer 34

BST insertion and removal can also be implemented using recursion. The insertion algorithm uses recursion to traverse down the tree until the insertion location is found. The removal algorithm uses the recursive search functions to find the node and the node's parent, then removes the node from the tree. If the node to remove is an internal node with 2 children, the node's successor is recursively removed.

Question 35

VIEW: Recursive BST insertion

Answer 35

Question 36

A binary search tree can be implemented in C++ using a ____ class and a ____ class.

Answer 36

Node, BST

Question 37

When implementing a BST using a Node class and a BST class, the Node class has an integer ____ value and data members for the left and right ____ nodes. The BinarySearchTree class contains a data member for the tree's ____ (a Node object).

Answer 37

Key, child Root

Question 38

VIEW: Node and BinarySearchTree class definitions.

Answer 38

Question 39

The binary search tree search algorithm first assigns currentNode with the root. A loop is then entered, and one of 3 cases occurs:

Answer 39

Question 40

VIEW: Binary search tree Search() function.

Answer 40

Question 41

The Insert() function is used to insert a new ____ into the tree. If the tree is empty, then the root data member is assigned with the ____ node. If the tree is not empty, ____ is assigned with the root node, and a loop is entered. Inside the loop, if the new node's ____ is less than the current node's key, then the new node is inserted as the current node's left ____ (if the current node has no left child), or currentNode is assigned with currentNode's left child. If the new node's key is ____ than or equal to the current node's key, then the new node is inserted as the current node's right child (if the current node has no right child), or currentNode is assigned with currentNode's right child.

Answer 41

Node, new, currentNode Key, child, greater

Question 42

VIEW: Binary search tree Insert() function.

Answer 42

Question 43

VIEW: A program to test the Insert() and Search() functions.

Answer 43

Question 44

The Remove() function is more complicated than Search() and Insert() because several cases exist. Different actions are taken depending on the kind of node being removed. What are those 3 cases?

Answer 44

Question 45

VIEW: Binary search tree Remove() function in C++.

Answer 45