1. In a binary search tree, we look for key 42. Is it possible that the sequence of compared keys in the nodes is (justify yout answer):
2. Consider a binary heap. Write the algorithm for adding an element to the heap. Show how the algorithm works for adding the value 42 to the following heap:
3. We want an abstract data type (ADT) and a corresponding data structure for a set-list combination. It shall allow:
Do the following:
a) Specify the ADT and give the public part of a class that implements it (including the iterator),
b) Specify the data structures used in the implementation of the collection class and of the iterator
c) Implement the "move next" operation for the iterator.
1.a) It is possible, for the tree depicted below.
We can check that, for each key in the comparison sequence, the keys following it are on the same side of the current key as the searched key. So, it is plausible that they belong to the same sub-tree of the current tree:
1.b) It is not possible, because, when reaching 44, the search will find that the searched key is smaller (42 < 44), so it shall go to the left sub-tree and meet only keys smaller than 55; however, the next key is larger.
2. The insertion algorithm, assuming that the heap is stored inside an array large enough to contain the old array plus the new element is:
Input-output: a - the array containing the heap
Input: v - the new element to be added
a.push_back(v)
current = a.size() - 1
while current > 0 do
parent = (current - 1) / 2
if a[parent] >= a[current] break
swap(a[parent], a[current])
end while
The successive states of the heap, until the heap is back in a valid state, are:
3. a)
template<typename T>
class SetList {
public:
// Desc: Creates an empty collection
// Pre: -
// Post: (*this) is an empty SetList collection
SetList();
// Pre: (*this) - a SetList collection
// Post: any memory dynamically allocated by object (*this) is deallocated
~SetList();
// Descr: verifies if val belongs to the collection, in O(log n)
// Pre: (*this) is a SetList collection
// Post: returned value = true if val is in collection (*this)
// false otherwise
bool contains(T val) const;
// Descr: Adds val at the last position, in O(log n);
// Pre: (*this) - a SetList collection
// val does not belong to the collection (*this)
// Post: val is in the collection (*this) on the last position
void append(T val);
// Iterator for the collection, C++ forward iterator style
class iterator {
public:
// Desc: moves the iterator to the next element in the collection
// Pre: (*this) is an iterator pointing to a valid element in a SetList
// (not past the end of the collection)
// Post: (*this) points to the next element of the SetList, in the order
// the elements were inserted, or past the end if no next element exists
iterator operator++();
// Desc: returns the current element
// Pre: (*this) is an iterator pointing to a valid element in a SetList
// (not past the end of the collection)
// Post: returned value = a reference to the current element
T const& operator*() const;
// Desc: returns the current element
// Pre: (*this) is an iterator pointing to a valid element in a SetList
// (not past the end of the collection)
// Post: returned value = a reference to the current element
T const* operator->() const;
// Desc: compares two iterators
// Pre: (*this) and that are iterators in the same SetList
// Post: returned value = true if (*this) and that both point to the same element,
// or if both point past the end of the collection
// false otherwise
bool operator==(iterator const& that) const;
// Desc: compares two iterators
// Pre: (*this) and that are iterators in the same SetList
// Post: returned value = false if (*this) and that both point to the same element,
// or if both point past the end of the collection
// true otherwise
bool operator!=(iterator const& that) const;
};
// Pre: (*this) - a SetList collection
// Post: returned value = iterator pointing to the first element
// in the collection (*this) if (*this) is non empty
// or "after the last" otherwise
iterator begin() const;
// Pre: (*this) - a SetList collection
// Post: returned value = iterator pointing after the last element
// in collection (*this)
iterator end() const;
};
3. b) We use an AVL tree.
template<typename T>
class SetList {
private:
struct Node {
T info;
Node* left; // left child in the AVL tree
Node* right; // right child in the AVL tree
Node* next; // next element inserted
short balance; // -1=left taller than right sub-tree; 0 = equal heights; 1=left shorter
};
Node* root; // root of the AVL tree
Node* head; // first node inserted
Node** lastPtr; // pointer to the 'next' member of the latest inserted node, or to head if empty
public:
class iterator {
private:
friend class SetList<T>;
iterator(Node* currentNode);
Node* m_currentNode; // node containing the current element, or nullptr for past-the-end
};
};
3. c) The iterator:
template<typename T>
void SetList::iterator::operator++() {
m_currentNode = m_currentNode->next;
}
Radu-Lucian LUPŞA