// Implementation of Treap class (Randomized Binary Search Tree)
#include "TreapSkeleton.h"
#include
#include
#include
#include
Treap::Treap()
: root_(0)
{}
Treap::Treap(const Treap& other)
: root_(0)
{
root_ = copy (other.root_);
}
TreapNode* Treap::copy (const TreapNode* current) {
if (current != 0) {
return new TreapNode (current->get_key(),
current->get_priority(),
copy(current->get_left()),
copy(current->get_right()));
} else
return 0;
}
Treap& Treap::operator= (const Treap& other)
{
if (root_ != other.root_) { //check for self-assignment
clear();
root_ = copy (other.root_);
}
return *this;
}
Treap::~Treap()
{
clear();
}
void Treap::clear()
{
clear_subtree(root_);
root_ = 0;
}
void Treap::clear_subtree(TreapNode* current)
{
if (current != 0) {
clear_subtree(current->left_);
clear_subtree(current->right_);
delete current;
}
}
void Treap::insert(const int key)
{
insert (root_, key, std::rand());
}
void Treap::insert (TreapNode*& current, const int key, const int priority)
{
if (current == 0)
current = new TreapNode (key, priority);
else
if (key < current->key_) {
insert (current->left_, key, priority);
if (priority > current->get_priority())
rotate_right (current);
}
else {
insert (current->right_, key, priority);
if (priority > current->get_priority())
rotate_left (current);
}
}
void Treap::rotate_left (TreapNode*& current)
{
assert (current->right_ != 0);
TreapNode* old_current = current;
current = current->right_;
old_current->right_ = current->left_;
current->left_ = old_current;
}
void Treap::rotate_right (TreapNode*& current)
{
assert (current->left_ != 0);
TreapNode* old_current = current;
current = current->left_;
old_current->left_ = current->right_;
current->right_ = old_current;
}
void Treap::remove(const int key)
{
// your code goes here
}
const TreapNode* Treap::find(const int key) const
{
const TreapNode* current = root_;
while (current != 0 && current->get_key() != key)
if (key < current->get_key())
current = current->get_left();
else
current = current->get_right();
return current;
}
int Treap::height() const
{
return 0;
// your code goes here
}
int Treap::size() const
{
return 0;
// your code goes here
}
const TreapNode* Treap::get_root() const
{
return root_;
}
void Treap::print_preorder(std::ostream& o) const
{
print_preorder(o, root_);
}
void Treap::print_preorder(std::ostream& o, const TreapNode* current) const
{
if (current != 0) {
o << current->get_key() << " ";
print_preorder(o, current->get_left());
print_preorder(o, current->get_right());
}
}
void Treap::print_postorder(std::ostream& o) const
{
print_postorder(o, root_);
}
void Treap::print_postorder(std::ostream& o, const TreapNode* current) const {
if (current != 0) {
print_postorder(o, current->get_left());
print_postorder(o, current->get_right());
o << current->get_key() << " ";
}
}
void Treap::print(std::ostream& o) const
{
print(o, root_);
}
void Treap::print(std::ostream& o, const TreapNode* current) const
{
if (current != 0) {
print(o, current->get_left());
o << current->get_key() << " ";
print(o, current->get_right());
}
}
void Treap::pretty_print (std::ostream& o) const
{
// your code goes here
}
bool Treap::is_valid () const {
int min, max;
return (root_ == 0 || is_binary_search_tree (root_, min, max) && is_heap(root_));
}
bool Treap::is_binary_search_tree (const TreapNode* current, int& min, int& max) const {
assert (current != 0);
min = max = current->get_key();
int min_r = max;
int max_l = min;
bool ok_l = true;
bool ok_r = true;
if (current->get_left() != 0)
ok_l = is_binary_search_tree (current->get_left(), min, max_l);
if (current->get_right() != 0)
ok_r = is_binary_search_tree (current->get_right(), min_r, max);
return (ok_l && ok_r && max_l <= current->get_key() && current->get_key() <= min_r);
}
bool Treap::is_heap (const TreapNode* current) const {
assert (current != 0);
if (current->get_left() != 0)
if (!is_heap (current->get_left()) || current->get_priority() < current->get_left()->get_priority())
return false;
if (current->get_right() != 0)
if (!is_heap (current->get_right()) || current->get_priority() < current->get_right()->get_priority())
return false;
return true;
}
std::ostream& operator<< (std::ostream& o, const Treap& tree) {
tree.print(o);
return o;
}