In this assignment you’re going to implement splay trees. Your splay trees will be expansions upon the following class definition:
#pragma once
#include <cassert>
#include <stdexcept>
class splay_tree {
public:
struct node
{
node(int key, node* left, node* right, node* parent) :
key(key), left(left), right(right), parent(parent)
{ }
int key;
node* left;
node* right;
node* parent;
};
~splay_tree()
{
clear();
}
/* root()
Returns the root of the tree.
Runs in O(1) time.
*/
node* root() const
{
return rt;
}
/* size()
Returns the size (total number of nodes) in the tree.
Runs in O(n) time.
*/
int size() const
{
// Remove the next line and add your code here.
throw std::logic_error("Not implemented");
}
/* empty()
Returns true if the tree is empty.
Runs in O(1) time.
*/
bool empty() const
{
// Remove the next line and add your code here.
throw std::logic_error("Not implemented");
}
/* rotate(c,p)
Rotate child node c with parent node p. c must be a child of p
(either c == p->left or c == p->right) and neither c nor p can be
nullptr.
Runs in O(1) time.
*/
static void rotate(node* c, node* p)
{
assert(c != nullptr and p != nullptr);
assert(c == p->left or c == p->right);
assert(c->parent == p);
// Remove the next line and add your code here.
throw std::logic_error("Not implemented");
}
/* splay(n)
Splays n to the root of the tree, returning the new root. n must not
be nullptr.
As with `rotate`, splay is a static member function, so it is not allowed
to access any member variables (it can call `rotate`, however).
Runs in O(d) time where d is the depth of node n (amortized, this
will be O(log n)).
*/
static node* splay(node* n)
{
assert(n != nullptr);
// Remove the next line and add your code here.
throw std::logic_error("Not implemented");
}
/* find(k)
Finds and returns the node containing key k, splaying it to the root.
If no such node exists, then `find` splay's the parent of the location
where k *should* be to the root, and then returns the new root. If the
tree is empty, returns nullptr. To determine whether a key k exists in
the (nonempty) tree, you would check
k == find(k)->key
Runs in O(log n) amortized time.
*/
node* find(int k)
{
// Remove the next line and add your code here.
throw std::logic_error("Not implemented");
}
/* insert(k)
Inserts k into the tree, splaying the new node to the root. If k
already exists in the tree, it should be splayed to the root. Returns
the new root of the tree.
Runs in O(log n) amortized time.
*/
node* insert(int k)
{
// Remove the next line and add your code here.
throw std::logic_error("Not implemented");
}
/* remove(k)
EXTRA CREDIT: Removes the node containing k, and splays its parent to
the root. If k does not exist in the tree, then nothing is removed,
but the parent (of where k *should* exist) is still splayed. Returns
the new root of the tree.
Runs in O(log n) amortized time.
*/
node* remove(int k)
{
// If you want to do the extra credit problem, remove the next line.
throw std::logic_error("Not implemented");
}
/* set_root(n)
Replaces the root node with n; this is only used for testing.
*/
void set_root(node* n)
{
rt = n;
}
/* clear()
Delete all nodes in the tree. You should implement the recursive
`clear(node*)` version below, and not modify this one.
*/
void clear()
{
clear(rt);
}
private:
/* clear(n)
Delete n and all its descendants.
*/
void clear(node* n)
{
throw std::logic_error("Not implemented");
}
node* rt = nullptr;
};
All of the functions you need to implement throw
a “Not implemented”
logic_error
by default; when you implement them, remove this line of code.
This is there to allow the test code to determine which functions you haven’t
written yet, and skip testing them.
For most of the core functions (insert
, find
, and size
), you will probably
want to add a helper function to actually perform the recursion, as we did in
class.
Note that maintaining parent pointers significantly complicates rotate
! In
particular, there are several possibly-overlapping situations to consider:
When you rotate a child node
c
with a parent nodep
,c
becomesp
‘s new parent. Sop->parent
needs to be updated.But
c
has also changed places in the tree, soc->parent
also needs to be updated, set top
’s old parent.Depending on whether
c
is a left- or right-child ofp
,c
’s right or left child will switch to being a child ofp
. So it will need its parent updated.- However, it’s possible that this child does not exist (
== nullptr
) in which case trying to change it’s->parent
will dereference a null pointer and crash the program with a segmentation violation (commonly known as a “segfault” orSIGSEGV
). So you have to check for that situation and not try to update the parent if the node does not exist. (You don’t have to worry about a similar situation withc
andp
, because both of those are guaranteed to never benullptr
.)
- However, it’s possible that this child does not exist (
p
’s original parent, before the rotation, contains a pointer down top
. That is, before the rotation, eitherp == p->parent->left
orp == p->parent->right
. This pointer needs to be updated to point to c.- Again, though, it’s possible that there is no node above
p
(p->parent == nullptr
), ifp
is the root of the tree. In this case, we don’t want to update the pointer, because, again, that would trigger a segfault.
- Again, though, it’s possible that there is no node above
Note also that rotate
must work even if the tree is somehow not a proper
binary search tree! That is, it should not rely on the keys being in the correct
order; it shouldn’t even examine the keys at all. The only relationships between
nodes it is concerned with are ->left
, ->right
and ->parent
.
As described in class, find
and insert
both splay the “target” node to the
root, or the parent of the target node if that is not possible. They both return
the new root of the tree.
remove
is optional, and extra credit. If you implement it, this assignment
counts for two “assignment points” instead of the usual one. That is, it can
make up for another assignment you don’t complete at the end of the semester.
(Before you ask, no you can’t implement nothing but remove
and get just the
1 extra-credit point.)
Save your solution as splaytree.hpp
(if you want to put your method
implementations into a splaytree.cpp
file, feel free, but you don’t have to).
Compile assign4_test.cpp
(available as
/usr/local/class/src/assign4_test.cpp
on the server).
Submission
Save your work in a directory on the server named cs133/assign4/
.