DSA 2. Data Structure Implementation
x ≠ NIL - answer*Inserting into a Binary Search Tree*
Given a binary search tree T and a new node z, the TREE_INSERT(T,z) procedure
insert the new node into the tree, maintaining the Binary Search Tree Property. Identify
the missing piece of code.
x ≠ NIL and k ≠ x.key - answer*Searching a Binary Search Tree*
Given a root node x and a key k, the TREE_SEARCH(x,k) procedure iteratively
searches the tree for the key K, returning NIL if k is not found. Identify the missing piece
of code.
TREE_SEARCH(x.left,k) - answer*Searching a Binary Search Tree*
Given a root node x and a key k, the TREE_SEARCH(x,k) procedure recursively
searches the tree for the key K, returning NIL if k is not found. Identify the missing piece
of code.
T[j] == NIL - answer*Inserting into an open addressing hash table*
Given a key k, the HASH_INSERT(T, k) procedure adds the key k to the hash table T.
This hash table is implemented as an array T[1..m], and includes a hash function h(k, i)
that, for every key k, the probe sequence {h(k,0),h(k,1),...,h(k,m-1)} is a permutation of
{0,1...,m-1}. Identify the missing piece of code.
T[j] == NIL - answer*Searching an open addressing hash table*
Given a key k, the HASH_SEARCH(T, k) procedure searches for the key k in the hash
table T. This hash table is implemented as an array T[1..m], and includes a hash
function h(k, i) that, for every key k, the probe sequence {h(k,0),h(k,1),...,h(k,m-1)} is a
permutation of {0,1...,m-1}. The HASH_SEARCH(T, k) procedure returns the index j
where the key k is found or NIL if the key is not in the hash table. Identify the missing
piece of code.
exchange A[i] with A[largest] - answer*Max-heapify an array*
Given an array A and an index i, where the left subtree rooted at 2i and the right subtree
rooted at 2i + 1 are max-heaps, the MAX_HEAPIFY(A,i) procedure lets the value at A[i]
x ≠ NIL - answer*Inserting into a Binary Search Tree*
Given a binary search tree T and a new node z, the TREE_INSERT(T,z) procedure
insert the new node into the tree, maintaining the Binary Search Tree Property. Identify
the missing piece of code.
x ≠ NIL and k ≠ x.key - answer*Searching a Binary Search Tree*
Given a root node x and a key k, the TREE_SEARCH(x,k) procedure iteratively
searches the tree for the key K, returning NIL if k is not found. Identify the missing piece
of code.
TREE_SEARCH(x.left,k) - answer*Searching a Binary Search Tree*
Given a root node x and a key k, the TREE_SEARCH(x,k) procedure recursively
searches the tree for the key K, returning NIL if k is not found. Identify the missing piece
of code.
T[j] == NIL - answer*Inserting into an open addressing hash table*
Given a key k, the HASH_INSERT(T, k) procedure adds the key k to the hash table T.
This hash table is implemented as an array T[1..m], and includes a hash function h(k, i)
that, for every key k, the probe sequence {h(k,0),h(k,1),...,h(k,m-1)} is a permutation of
{0,1...,m-1}. Identify the missing piece of code.
T[j] == NIL - answer*Searching an open addressing hash table*
Given a key k, the HASH_SEARCH(T, k) procedure searches for the key k in the hash
table T. This hash table is implemented as an array T[1..m], and includes a hash
function h(k, i) that, for every key k, the probe sequence {h(k,0),h(k,1),...,h(k,m-1)} is a
permutation of {0,1...,m-1}. The HASH_SEARCH(T, k) procedure returns the index j
where the key k is found or NIL if the key is not in the hash table. Identify the missing
piece of code.
exchange A[i] with A[largest] - answer*Max-heapify an array*
Given an array A and an index i, where the left subtree rooted at 2i and the right subtree
rooted at 2i + 1 are max-heaps, the MAX_HEAPIFY(A,i) procedure lets the value at A[i]
