implementation of tree and in_order traversal (plus tree balancing)

#pragma once

#include<stack>
#include<iostream>
template<class T>
class CTreeNode
{
public:
T m_val;
CTreeNode* left;
CTreeNode* right;

CTreeNode(){left=NULL;right=NULL;}
~CTreeNode(void);
};

template<class T>
class CTree
{
public:
CTreeNode<T>* m_root;

CTree(T val){m_root=new CTreeNode<T>();m_root->m_val=val;}
~CTree(){}
void insert(T val);
void in_order();
};


template<class T>
void CTree<T>::insert(T val)
{
CTreeNode<T>* cur_node=m_root,*prev_node;
while(cur_node!=NULL)
{
prev_node=cur_node;
if(val<cur_node->m_val)
cur_node=cur_node->left;
else
cur_node=cur_node->right;

}
cur_node=new CTreeNode<T>();
cur_node->m_val=val;
if(val<prev_node->m_val)
prev_node->left=cur_node;
else
prev_node->right=cur_node;
}

template<class T>
void CTree<T>::in_order()
{
CTreeNode<T>* cur_node=m_root;
stack<CTreeNode<T>*> node_stack;
while(cur_node)
{
node_stack.push(cur_node);
cur_node=cur_node->left;
}
while(!node_stack.empty())
{
CTreeNode<T>* node=node_stack.top();
node_stack.pop();
std::cout<<node->m_val<<" ";
CTreeNode<T>* right=node->right;
while(right)
{
node_stack.push(right);
right=right->left;
}
}
}

tree balancing:

balanceFactor = height(left-subtree) - height(right-subtree). 

Right-Right case and Right-Left case:

• If the balance factor of P is -2 then the right subtree outweighs the left subtree of the given node, and the balance factor of the right child (R) must be checked. The left rotation with P as the root is necessary.
  • If the balance factor of R is -1 (or in case of deletion also 0), a single left rotation (with P as the root) is needed (Right-Right case).
  • If the balance factor of R is +1, two different rotations are needed. The first rotation is a right rotation with R as the root. The second is aleft rotation with P as the root (Right-Left case).

Left-Left case and Left-Right case:

• If the balance factor of P is 2, then the left subtree outweighs the right subtree of the given node, and the balance factor of the left child (L) must be checked. The right rotation with P as the root is necessary.
• If the balance factor of L is +1 (or in case of deletion also 0), a single right rotation (with P as the root) is needed (Left-Left case).
• If the balance factor of L is -1, two different rotations are needed. The first rotation is a left rotation with L as the root. The second is aright rotation with P as the root (Left-Right case).

http://en.wikipedia.org/wiki/AVL_tree

implement your own sizeof() operator

#define mysizeof(data) (char *)(&data+1)-(char *)(&data)

When you increment a T*, it moves sizeof(T) bytes.^† This is because it doesn't make sense to move any other value: if I'm pointing at an int that's 4 bytes in size, for example, what would incrementing less than 4 leave me with? A partial int mixed with some other data: nonsensical.

http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/BitOp/pointer.html

The formula used is rather simple. Assume that p1 and p2 are both pointers of type T *. Then, the value computed is:

    ( p2 - p1 ) == ( addr( p2 ) - addr( p1 ) ) / sizeof( T )

int c[3]={1,2,3};
cout<<&c+1<<" "<<&c<<endl;
cout<<(char*)(&c+1)-(char*)(&c)<<endl;//print 12  but if change to int* c it prints 4
int * arr[ 12 ] ;
int ** ptr = arr ;
cout<<(char*)(ptr+1)-(char*)ptr<<endl; //print 4

a more naive example:

int days[] = {1,2,3,4,5};
 int *ptr2 = days;
 printf("%u\n", sizeof(days));
 printf("%u\n", sizeof(ptr));

knapsack problem and set sum problem

http://en.wikipedia.org/wiki/Subset_sum

NP complete, pseudo-polynomial

The trick is: O(nW) looks like a polynomial time, but it is not, it is pseudo-polynomial. Time complexity measures the time that an algorithm takes as function of the length in bits of its input. The dynamic programming solution is indeed linear in the value of W but exponential in the length of W - and that's what matters.




inline bool set_sum(vector<int> input,int S)
{
sort(input.begin(),input.end());
int neg=0,pos=0;
for(vector<int>::iterator j=input.begin();j<input.end();j++)
{
if(*j<0)neg+=-*j;
else pos+=*j;
}
vector<vector<bool>> table;
int input_num=input.size();
table.resize(input_num+1);
int sum_range=pos+neg+1;
for(int i=0;i<=input_num;i++)
{
table[i].resize(sum_range);
if(i==0)
fill(table[i].begin(),table[i].end(),false);
}
for(int i=1;i<=input_num;i++)
{
for(int j=0;j<sum_range;j++)
{
int cur_sum=j-neg;
if(input[i-1]==cur_sum)
table[i][j]=true;
else if(table[i-1][j]==true)
table[i][j]=true;
else if(j-input[i-1]>=0 && j-input[i-1]<sum_range && table[i-1][j-input[i-1]])
table[i][j]=true;
}
}
return S+neg>=0 && S+neg<sum_range && table[input_num][S+neg];
}

deque

an example:


inline void test_deque()
{
std::deque<int> Q;
Q.push_back(3);
Q.push_front(1);
std::copy(Q.begin(),Q.end(),std::ostream_iterator<int>(std::cout," "));
std::cout<<std::endl;
for(std::deque<int>::iterator iter=Q.begin();iter<Q.end();iter++)
std::cout<<*iter<<" ";

}

continuous memory
const time to insert at front and the end.


inline void test_list()
{
std::list<int> L;
L.push_back(0);
L.push_front(1);
L.insert(++L.begin(),2);

std::copy(L.begin(),L.end(),std::ostream_iterator<int>(std::cout," "));
}


insert takes constant time but need to provide the iterator first.

cciv 3.6

#include<stack>
#include<vector>
#include<algorithm>
template<class T>

#define ALGO_2

inline void sortstack(std::stack<T>& stack)
{
//algorithm 1
#ifdef ALGO_1
std::vector<T> v;
while(!stack.empty())
{
T val=stack.top();
stack.pop();
v.push_back(val);
}
std::sort(v.begin(),v.end());
for(int i=0;i<v.size();i++)
stack.push(v[i]);
#endif
//algorithm 2
#ifdef ALGO_2
std::stack<T> s2;
while(!stack.empty())
{
T val=stack.top();
stack.pop();
while(!s2.empty() && val<s2.top())
{
T val2=s2.top();
s2.pop();
stack.push(val2);
}
s2.push(val);
//cout<<s2.top()<<endl;
}
stack=s2;
#endif
}

Solution to cracking coding interview 3.4

MyQueue.h


#pragma once
#include<stack>

template<class T>
class CMyQueue
{
std::stack<T> m_stack1;
std::stack<T> m_stack2;
public:
void push(const T& elem);
T pop();
CMyQueue(void);
~CMyQueue(void);
};

#include"MyQueue.cpp"

MyQueue.cpp



#include "MyQueue.h"

template<class T>
CMyQueue<T>::CMyQueue(void)
{

}

template<class T>
CMyQueue<T>::~CMyQueue(void)
{
}

template<class T>
void CMyQueue<T>::push(const T& elem)
{
m_stack1.push(elem);
}

template<class T>
T CMyQueue<T>::pop()
{
if(m_stack2.empty())
{
while(!m_stack1.empty())
{
T val=m_stack1.top();
m_stack1.pop();
m_stack2.push(val);
}
}
try
{
if(m_stack2.empty())
throw exception("out of range");
T val=m_stack2.top();
m_stack2.pop();
return val;
}
catch(exception e)
{
std::cout<<e.what();
exit(-1);
}
}

an interesting explanation of why pop() in stl does not return value

1. SGI explanation: http://www.sgi.com/tech/stl/stack.html One might wonder why pop() returns void, instead of value_type. That is, why must one use top() and pop() to examine and remove the top element, instead of combining the two in a single member function? In fact, there is a good reason for this design. If pop() returned the top element, it would have to return by value rather than by reference: return by reference would create a dangling pointer. Return by value, however, is inefficient: it involves at least one redundant copy constructor call. Since it is impossible for pop() to return a value in such a way as to be both efficient and correct, it is more sensible for it to return no value at all and to require clients to use top() to inspect the value at the top of the stack.
2. std::stack < T > is a template. If pop() returned the top element, it would have to return by value rather than by reference as per the of above explanation. That means, at the caller side it must be copied in an another T type of object. That involves a copy constructor or copy assignment operator call. What if this type T is sophisticated enough and it throws an exception during copy construction or copy assignment? In that case, the rvalue, i.e. the stack top (returned by value) is simply lost and there is no other way to retrieve it from the stack as the stack's pop operation is successfully completed!