Set implementation in C++ (using binary tree).

set.cpp

#include <cassert>
#include <initializer_list>
#include <iostream>

using node_t = struct node*;

struct node {
  int elem;
  node_t left, right;

  node(int elem) : elem(elem), left(nullptr), right(nullptr) {}
};

node_t remove_node(node_t root) {
  node_t current;
  if(!root->left) {
    current = root->right;
  } else {
    node_t previous = root;
    current = root->left;
    while(current->right) {
      previous = current;
      current = current->right;
    }
    if(previous != root) {
      previous->right = current->left;
      current->left = root->left;
    }
    current->right = root->right;
  }
  delete root;
  return current;
}

void delete_node(node_t root) {
  if(root->left) delete_node(root->left);
  if(root->right) delete_node(root->right);

  delete root;
}

class set {
  node_t root;
  size_t size_;

public:
  set() : root(nullptr), size_(0) {}
  set(const std::initializer_list<int>& il) : set() {
    for(const int elem : il) insert(elem);
  }
  ~set() {
    if(root) delete_node(root);
  }

  bool empty() {
    return !root;
  }
  size_t size() {
    return size_;
  }

  void insert(int elem);
  void remove(int elem);
  bool member(int elem);
};

void set::insert(int elem) {
  node_t* current = &root;
  while(*current) {
    if(elem == (*current)->elem) return;
    if(elem < (*current)->elem)
      current = &(*current)->left;
    else
      current = &(*current)->right;
  }
  *current = new node(elem);
  ++size_;
}

void set::remove(int elem) {
  node_t* current = &root;
  while(*current) {
    if(elem == (*current)->elem) {
      *current = remove_node(*current);
      --size_;
      return;
    }
    if(elem < (*current)->elem)
      current = &(*current)->left;
    else
      current = &(*current)->right;
  }
}

bool set::member(int elem) {
  node_t* current = &root;
  while(*current) {
    if(elem == (*current)->elem) return true;
    if(elem < (*current)->elem)
      current = &(*current)->left;
    else
      current = &(*current)->right;
  }
  return false;
}

int main() {
  set s;
  assert(s.empty());

  s.insert(1);
  assert(!s.empty());

  s.remove(4);
  assert(!s.empty());

  s.insert(2);
  s.insert(3);
  assert(s.member(1));
  assert(s.member(2));
  assert(s.member(3));
  assert(!s.member(4));
  assert(s.size() == 3);

  s.remove(1);
  s.remove(2);
  s.remove(3);
  assert(s.empty());

  return 0;
}