воскресенье, 23 августа 2015 г.

Find node in a binary search tree


template<typename T>
treenode<T> * find_node_by_data(treenode<T> * root, const T& value) {
 treenode<T> * node = root;
 while (node) {
  if (node->data == value)
   return node;
  if (value > node->data)
   node = node->right;
  else
   node = node->left;
 }
 return nullptr;
}

вторник, 4 августа 2015 г.

Create binary search tree from sorted array (asc order)


/* call example */
std::vector v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
treenode * root = generate_bst_tree(v);

/* implementation */
template<typename T>
treenode<T> * generate_bst_tree(const std::vector<T>& v, 
treenode<T> * node = nullptr, 
size_t from = 0, 
size_t to = 0) {
 
 treenode<T> * root = nullptr;

 if (!node) {
  if (v.size() == 0)
   return nullptr;

  root = node = new treenode();
  if (v.size() == 1) {
   root->data = v[0];
   return root;
  }
  to = v.size() - 1;
 }

 const size_t mid = (to - from) / 2 + from;
 node->data = v[mid];
 
 if ((mid - from) > 1) {
  node->left = new treenode<T>();
  generate_bst_tree(v, node->left, from, mid);
 }
 else {
  if ( from == 0 )
   node->left = new treenode<T>(v[from]);
 }

 if ((to - mid) > 1 ) {
  node->right = new treenode<T>();
  generate_bst_tree(v, node->right, mid, to);
 }
 else {
  if (to == v.size() - 1)
   node->right = new treenode<T>(v[to]);
 }

 return root;
}

Print binary tree by levels (breadth first)


template<typename T>
struct treenode {
 treenode<T> * left, *right, *parent;
 T data;
 treenode() : left(nullptr), right(nullptr), parent(nullptr) {}
 treenode(const T& param) 
: left(nullptr), right(nullptr), parent(nullptr), data(param) {}
};

template<typename T>
void print_tree(const treenode * root) {
 if (!root) {
  std::cout << "EMPTY\r\n";
  return;
 }
 
 std::queue<const treenode<T> * > q;
 q.push(root);

 const treenode<T>* node;
 size_t sz = 0; 
 
 while ((sz = q.size()) > 0) {
  for (size_t i = 0; i < sz; ++i) {
   node = q.front();
   std::cout  << node->data  << " ";
   q.pop();
   if (node->left)
    q.push(node->left);
   if (node->right)
    q.push(node->right);
  }
  std::cout  << std::endl;
 }
}

понедельник, 20 июля 2015 г.

Check if the binary tree is balanced


template<typename T>
struct treenode {
 treenode<T> * left, * right;
 T data;
 treenode(const T& param) 
: left(NULL), right(NULL), data(param) {}
};

template<typename T>
bool is_balanced(treenode<T> * node, int& height) {
 if (!node)
  return true;
 ++height;

 if (!is_balanced(node->left, height))
  return false;

 const int lh = height;
 height = 0;

 if (!is_balanced(node->right, height))
  return false;

 const int rh = height;
 return abs(lh - rh) <= 2;
}

четверг, 30 апреля 2015 г.

Binary search

Finds an index to put a element to if it's absent. Return true if it's there. Helps to find an index to insert an element. Not content with this one. Must be somehow redone. Looks like shit actually. Requires size_t slot be initialized by '0'


bool find_slot(const char * buffer, 
const size_t size, 
const char elem, 
size_t * slot) {

    const size_t m = (size_t)(size / 2);

    if ( m == 0 )
        return false;

    if ( elem > buffer[m - 1] ) {
        *slot += m;
        if ( elem < buffer[m] )
            return false;
        return find_slot(buffer + m, size - m, elem, slot);
    }

    if ( elem < buffer[m - 1] ) {
        if ( elem > buffer[m - 2] )
            return false;
        return find_slot(buffer, size - m, elem, slot);
    }
    return true;
}

вторник, 28 апреля 2015 г.

Reverse string


void reverse(char * str) {

    char temp;

    for ( int i = strlen(str) - 1, j = 0; 
              j < (int)(strlen(str) / 2); --i, ++j) {

        temp = str[i];
        str[i] = str[j];
        str[j] = temp;

    }
}

понедельник, 27 апреля 2015 г.

Permutations


void permute(permtype * p, const char * expr) {
    p->perms[0][0] = expr[0];

    for (size_t i = 1; i < p->LEN; ++i)
        merge(p, i, expr[i]);

}

void merge(permtype * p, const size_t index, const char elem) {

    const size_t Nprev = index > 0 ? factorial(index) : 0;
    assert(p->N > Nprev);
    size_t j = Nprev;

    for (size_t i = 0; i < Nprev; ++i) {
        for ( size_t k = 0; k < index; ++k )
            splice(&(p->perms[j++]), p->perms[i], elem, k, index);

        p->perms[i][index] = elem;
    }

}

четверг, 16 апреля 2015 г.

This brilliant code snippet takes a node offset by the index from the head and swaps its value with the node offset by the index from the tail.


void swapAt(Node *head, int index) {

    Node * node = head;
    Node * begin, trailer;

    for (int i = 0; node != NULL; node = node->next, ++i ) {

         if ( i == index ) {
            begin = node;
            trailer = head;
         }

         if ( i > index)
             trailer = trailer->next;

    }

    int temp = begin.val;
    begin.val = trailer.val;
    trailer.val = temp;
}