Skip to content

Instantly share code, notes, and snippets.

@vy
Created November 29, 2012 21:17
Show Gist options
  • Save vy/4171977 to your computer and use it in GitHub Desktop.
Save vy/4171977 to your computer and use it in GitHub Desktop.
Merging Two Binary Search Trees in O(logn) Space
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <stack>
#include "Node.hpp"
#include "NodeStream.hpp"
#include "MergeNodeAlgorithm.hpp"
#include "MergeNodeStream.hpp"
#include "MergeNodeVector.hpp"
using namespace std;
static Node<int>* randomTree(size_t depth, int lo, int hi) {
if (!depth) return NULL;
int data = lo + rand() % (hi - lo + 1);
return new Node<int>(
data,
randomTree(depth-1, lo, data),
randomTree(depth-1, data, hi));
}
static void validate(
const Node<int>* lhn,
const Node<int>* rhn,
MergeNodeAlgorithm<int>& mna) {
bool error = false;
if (!mna.empty())
for (int prev = mna.get(); !mna.empty(); prev = mna.get(), mna.pop())
if (prev > mna.get()) {
error = true;
cout << "[ERROR] prev: " << prev << ", curr: " << mna.get() << endl;
}
if (error) {
cout << "lhn: " << *lhn << endl;
cout << "rhn: " << *rhn << endl;
}
}
int main(int argc, char *argv[]) {
if (argc != 2 && argc != 3) {
cerr << "Usage: " << argv[0] << " <DEPTH> [<USE-STREAM>]" << endl;
exit(1);
}
size_t depth = atoi(argv[1]);
bool useStream = argc == 2;
srand(time(NULL));
Node<int>* lhn = randomTree(depth, 0, RAND_MAX);
Node<int>* rhn = randomTree(depth, 0, RAND_MAX);
if (useStream) {
NodeStream<int> lhs(lhn);
NodeStream<int> rhs(rhn);
MergeNodeStream<int> mns(lhs, rhs);
validate(lhn, rhn, mns);
} else {
MergeNodeVector<int> mnv(lhn, rhn);
validate(lhn, rhn, mnv);
}
delete lhn;
delete rhn;
return 0;
}
#ifndef MERGE_NODE_ALGORITHM_HPP
#define MERGE_NODE_ALGORITHM_HPP
template <class T>
class MergeNodeAlgorithm {
public:
virtual bool empty() const = 0;
virtual void pop() = 0;
virtual T get() const = 0;
};
#endif
#ifndef MERGE_NODE_STREAM_HPP
#define MERGE_NODE_STREAM_HPP
template <class T>
class MergeNodeStream : public MergeNodeAlgorithm<T> {
public:
MergeNodeStream(NodeStream<T>&, NodeStream<T>&);
bool empty() const;
void pop();
T get() const;
private:
NodeStream<T>& _xs;
NodeStream<T>& _ys;
};
template <class T>
MergeNodeStream<T>::MergeNodeStream(NodeStream<T>& xs, NodeStream<T>& ys)
: _xs(xs), _ys(ys) {}
template <class T>
bool MergeNodeStream<T>::empty() const {
return _xs.empty() && _ys.empty();
}
template <class T>
void MergeNodeStream<T>::pop() {
if (!_xs.empty() && !_ys.empty()) {
NodeStream<T>& smallest = _xs.get() < _ys.get() ? _xs : _ys;
smallest.pop();
}
if (_xs.empty() || _ys.empty()) {
NodeStream<T>& nonempty = _xs.empty() ? _ys : _xs;
nonempty.pop();
}
}
template <class T>
T MergeNodeStream<T>::get() const {
if (!_xs.empty() && !_ys.empty()) {
NodeStream<T>& smallest = _xs.get() < _ys.get() ? _xs : _ys;
return smallest.get();
}
if (_xs.empty() || _ys.empty()) {
NodeStream<T>& nonempty = _xs.empty() ? _ys : _xs;
return nonempty.get();
}
return NULL;
}
#endif
#ifndef MERGE_NODE_VECTOR_HPP
#define MERGE_NODE_VECTOR_HPP
template <class T>
class MergeNodeVector : public MergeNodeAlgorithm<T> {
public:
MergeNodeVector(const Node<T>*, const Node<T>*);
~MergeNodeVector();
bool empty() const;
void pop();
T get() const;
private:
NodeStream<T>* _lhs;
int* _rhv;
size_t _nrh;
size_t _rhp;
};
template <class T>
MergeNodeVector<T>::MergeNodeVector(const Node<T>* lhn, const Node<T>* rhn) {
assert(lhn && rhn);
_lhs = new NodeStream<T>(lhn);
_rhp = 0;
_nrh = rhn->size();
_rhv = new int[_nrh];
NodeStream<int> rhs(rhn);
for (size_t i = 0; i < _nrh; ++i) {
_rhv[i] = rhs.get();
rhs.pop();
}
}
template <class T>
MergeNodeVector<T>::~MergeNodeVector() {
delete _lhs;
delete _rhv;
}
template <class T>
bool MergeNodeVector<T>::empty() const {
return _lhs->empty() && _rhp == _nrh;
}
template <class T>
void MergeNodeVector<T>::pop() {
if (!_lhs->empty() && _rhp < _nrh) {
if (_rhv[_rhp] < _lhs->get())
_rhp++;
else
_lhs->pop();
}
else if (!_lhs->empty())
_lhs->pop();
else if (_rhp < _nrh)
_rhp++;
}
template <class T>
T MergeNodeVector<T>::get() const {
if (!_lhs->empty() && _rhp < _nrh) {
if (_rhv[_rhp] < _lhs->get())
return _rhv[_rhp];
else
return _lhs->get();
}
if (!_lhs->empty())
return _lhs->get();
if (_rhp < _nrh)
return _rhv[_rhp];
return NULL;
}
#endif
#ifndef NODE_HPP
#define NODE_HPP
template <class T>
class Node {
public:
Node(T);
Node(T, Node<T>*, Node<T>*);
T data() const;
Node<T>* left() const;
Node<T>* right() const;
size_t size() const;
~Node();
private:
T _data;
Node<T>* _left;
Node<T>* _right;
};
template <class T>
Node<T>::Node(T data) : _data(data), _left(NULL), _right(NULL) {}
template <class T>
Node<T>::Node(T data, Node<T>* left, Node<T>* right)
: _data(data), _left(left), _right(right) {}
template <class T>
T Node<T>::data() const { return _data; }
template <class T>
Node<T>* Node<T>::left() const { return _left; }
template <class T>
Node<T>* Node<T>::right() const { return _right; }
template <class T>
size_t Node<T>::size() const {
size_t size = 1;
if (_left) size += _left->size();
if (_right) size += _right->size();
return size;
}
template <class T>
Node<T>::~Node() {
if (_left) delete _left;
if (_right) delete _right;
}
template <class T>
std::ostream& operator<<(std::ostream& stream, const Node<T>& node) {
if (node.left() && node.right())
return stream
<< "Node("
<< *node.left() << ", "
<< node.data() << ", "
<< *node.right() << ")";
else if (node.left())
return stream
<< "Node("
<< *node.left() << ", "
<< node.data() << ", X)";
else if (node.right())
return stream
<< "Node(X, "
<< node.data() << ", "
<< *node.right() << ")";
else
return stream << "Node("<< node.data() << ")";
}
#endif
#ifndef NODE_STREAM_HPP
#define NODE_STREAM_HPP
template <class T>
class NodeStream {
public:
NodeStream(const Node<T>*);
bool empty() const;
void pop();
T get() const;
private:
std::stack<const Node<T>*> nodes;
void consume(const Node<T>*);
};
template <class T>
NodeStream<T>::NodeStream(const Node<T>* root) {
consume(root);
}
template <class T>
bool NodeStream<T>::empty() const {
return nodes.empty();
}
template <class T>
void NodeStream<T>::pop() {
const Node<T>* node = nodes.top();
nodes.pop();
consume(node->right());
}
template <class T>
T NodeStream<T>::get() const {
return nodes.top()->data();
}
template <class T>
void NodeStream<T>::consume(const Node<T>* root) {
if (root) {
nodes.push(root);
consume(root->left());
}
}
#endif
import Ordering.Implicits._
case class Tree[T: Ordering](data: T, left: Option[Tree[T]] = None, right: Option[Tree[T]] = None) {
def this(data: T) = this(data, None, None)
def stream: Stream[T] = this match {
case Tree(d, Some(l), Some(r)) => l.stream ++ Stream.cons(data, r.stream)
case Tree(d, Some(l), None) => l.stream :+ d
case Tree(d, None, Some(r)) => d +: r.stream
case Tree(d, None, None) => Stream(d)
}
def merge(that: Tree[T]): Stream[T] = {
def reduce(xs: Stream[T], ys: Stream[T]): Stream[T] = {
if (xs.isEmpty) ys
else if (ys.isEmpty) xs
else if (xs.head < ys.head) xs.head +: reduce(xs.tail, ys)
else ys.head +: reduce(xs, ys.tail)
}
reduce(this.stream, that.stream)
}
}
val xs = Tree(3, Some(Tree(2)), Some(Tree(6)))
val ys = Tree(4, Some(Tree(1)), Some(Tree(5)))
println(xs.merge(ys).force)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment