Searching and Tables

Question 1

What are common names for data structures that allow for efficient searching?

Answer 1

• Associative array
• Map
• Dictionary

Question 2

What are data structures in the table ADT?

Answer 2

• Associative array
• Dictionary
• Map

Question 3

What are basic operations of table ADTs?

Answer 3

1. construct (initialize) a table
2. search and retrieve for an entry
3. update record (doesn’t change key)
4. insert and delete (dynamic operations)
5. enumerate all (usually unsorted)

Question 4

Binary search example

Answer 4

Question 5

Basic table ADT operations and worst case running times on a table of n elements are:

Answer 5

1. Construct (initialize) a table; requires sorting Θ(n lg n)
2. Search and retrieve an entry; binary search Θ(lg n)
3. Update record (doesn’t change key); binary search Θ(lg n)
4. Insert and delete (dynamic operations); shift array Θ(n)
5. Enumerate all (here it will be sorted); scan array Θ(n)

we can improve running of number 4 to O(lg n) by using a different data structure i.e. binary tree or hash table

Question 6

What is a BST?

Answer 6

A binary search tree (BST) is a binary tree that satisfies the following ordering relation: for every node ν in the tree, the values of all the keys in the left subtree are smaller than (or equal, if duplicates allowed) to the key in ν and the values of all the keys in the right subtree are greater than the key in ν.

Left subtree has smaller valued nodes then right subtree

Question 7

Searching and Inserting example

Answer 7

Question 8

Illustrating Removal of Nodes in a BST

Answer 8

Question 9

The search, retrieval, update, insert and remove operations in a BST all take what time?

Answer 9

O(h) in the worst case, where h is the height of the tree

Question 10

The search, retrieval, update, insert and remove operations in a well-balanced BST

Answer 10

Θ(lg n)

dynamic operations of insertion and deletions may destroy balance, degrading performance to Ω(n)

Question 11

What technique is used to make sure worst case does not occur in BST?

Answer 11

balancing

Question 12

Left and right rotation of BST

Answer 12

Question 13

What is an AVL tree?

Answer 13

An AVL tree is a binary search tree with the additional balance property that the tree is balanced

Question 14

What is the height of an AVL tree with n nodes?

Answer 14

Θ(log n)

(AVL trees are more rigidly balanced than red-black trees so good for applications with more prominent search-only operations)

Question 15

What is a red-black tree?

Answer 15

A red-black tree is a binary search tree such that every node is colored either red or black and every non-leaf node has two children. In addition, it satisfies the following properties:

• the root is black;
• all children of a red node must be black;
• every path from the root node to a leaf must contain the same number of black nodes.

Question 16

If every path from the root to a leaf contains b black nodes then how many black nodes are in the tree?

Answer 16

at least 2b − 1 black nodes

Question 17

What is the max height of a red-black and thus the search time?

Answer 17

height: 2lg n

search time: O(log n)

Question 18

Red-black tree example

Answer 18

Question 19

What is a B-Tree?

Answer 19

A B-tree of order m is an m-ary tree such that:

• the root is either a leaf or it has between 2 and m children;
• each nonleaf node (except possibly the root) has between dm/2e and m children inclusive;
• each nonleaf node with µ children has µ − 1 keys;
• all leaves are at the same depth; • data items are stored in le

Question 20

What are B-Trees used for?

Answer 20

• A B-tree implements the table API but used for external/slow devices such as disks (or cloud)

Question 21

2-4 B-Tree example

Answer 21