C++ implementation of an AVL tree

A simple implementation of an AVL tree:

#include 
using namespace std;
#define MAX 10000

struct binary_tree {
    binary_tree * parent;
    binary_tree * left;
    binary_tree * right;
    int value;
    int index;
};

binary_tree * root = NULL;
binary_tree * nil;
int h[MAX]; // keep values for the heights of the sub trees
int tree_size;

void init_tree() {
    nil = new binary_tree[1];
    nil->left = nil->right = nil->parent = NULL;
    nil->index = 0;
    root = nil;
    tree_size = 0;
}

// does a single left rotation
void left_rotate(binary_tree * x) {
    binary_tree * y = x->right;
    x->right = y->left;
    if (y->left != nil) {
        y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == nil) {
        root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}

// does a single right rotation
void right_rotate(binary_tree * x) {
    binary_tree * y = x->left;
    x->left = y->right;
    if (y->right != nil) {
        y->right->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == nil) {
        root = y;
    } else if (x == x->parent->right) {
        x->parent->right = y;
    } else {
        x->parent->left = y;
    }
    y->right = x;
    x->parent = y;
}

// returns the height of the subtree with root x
int height(binary_tree * x) {
    if (x == nil) return 0;
    return max(height(x->left),height(x->right))+1;
}

// balances the tree after insert from leaves to the root
// currently you could observe that there is a problem in this code:
// we traverse the tree and begin balacing from every leaf when that's not actually neeeded
// instead we could keep a reference to the leaf node we have added and balance the tree upwards. The author leaves this to the reader
void balance(binary_tree * x) {
    if (x == nil) return;
    balance(x->left);
    balance(x->right);
    int h1 = height(x->left);
    h[x->left->index] = h1;
    int h2 = height(x->right);
    h[x->right->index] = h2;
    if (h1 - h2 == 2) {
        int lh = h[x->left->left->index];
        int rh = h[x->left->right->index];
        if (lh-rh == 1) {
            right_rotate(x);
        } else {
            // zig zag case
            left_rotate(x->left);
            right_rotate(x);
        }
    } else if (h1 - h2 == -2) {
        int lh = h[x->right->left->index];
        int rh = h[x->right->right->index];
        if (lh-rh == -1) {
            left_rotate(x);
        } else {
            // zig zag case
            right_rotate(x->right);
            left_rotate(x);
        }
    }
}

void add_to_binary_tree(int a) {
    binary_tree * x = root;
    binary_tree * y = nil;
    binary_tree * z = new binary_tree[1];
    z->value = a;
    z->left = z->right = nil;
    z->index = ++tree_size;
    while (x != nil) {
        y = x;
        if (z->value < x->value) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    z->parent = y;
    if (y == nil) {
        root = z;
    } else if(z->value < y->value) {
        y->left = z;
    } else {
        y->right = z;
    }
    balance(root);
}

// in-order print
void print(binary_tree * el, int i) {
    cout < < el->value < < " " << ++i << endl;
    if (el->left != nil) print(el->left,i);
    if (el->right != nil) print(el->right,i);
}

binary_tree * search(int x) {
    binary_tree * temp = new binary_tree[1];
    temp = root;
    while (true) {
        if (temp == nil) {
            return nil;
        }
        if (temp->value == x) {
            return temp;
        }
        if (temp->value < x) {
            temp = temp->right;
            continue;
        }
        if(temp->value > x) {
            temp = temp->left;
            continue;
        }
    }
}

void transplant(binary_tree * node1, binary_tree * node2) {
    if (node1->parent == nil) {
        root = node2;
    } else if (node1->parent->left == node1) {
        node1->parent->left = node2;
    } else {
        node1->parent->right = node2;
    }
    node2->parent = node1->parent;
}

binary_tree * minimum(binary_tree * node) {
    while (node->left != nil) node = node->left;
    return node;
}

void delete_balance(binary_tree * x) {
    int h1 = height(x->left);
    h[x->left->index] = h1;
    int h2 = height(x->right);
    h[x->right->index] = h2;

    if (h1-h2 == 2) {
        if (h[x->left->left->index]-h[x->left->right->index] == -1) {
            // zig zag cas
            left_rotate(x->left);
        }
        right_rotate(x);
    } else if (h1-h2 == -2) {
        if (h[x->right->left->index]-h[x->right->right->index] == 1) {
            // zig zag case
            right_rotate(x->right);
        }
        left_rotate(x);
    }
    if (x == root) return;
    delete_balance(x->parent);
}

void delete_from_binary_tree(int val) {
    binary_tree * x = new binary_tree[1];
    binary_tree * y = new binary_tree[1];
    binary_tree * q = new binary_tree[1];
    x = search(val);
    if (x == nil) {
        cout < < "NOT FOUND" << endl;
        return;
    }
    q = x;
    if (x->left == nil) {
        transplant(x,x->right);
    } else if (x->right == nil) {
        transplant(x,x->left);
    } else {
        y = minimum(x->right);
        if (y->parent != x) {
            transplant(y,y->right);
            y->right = x->right;
            y->right->parent = y;
        }
        transplant(x,y);
        y->left = x->left;
        y->left->parent = y;
    }
    delete_balance(q);
}

int main() {
    int n,a;
    init_tree();
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        add_to_binary_tree(a);
    }
    delete_from_binary_tree(0);
    delete_from_binary_tree(-5);
    delete_from_binary_tree(100);
    delete_from_binary_tree(150);
    print(root,0);

}

/*
10
10 5 7 0 -5 6 100 70 125 150
*/

Stochastic gradient descent c++ implementation

This is an implementation of the Stochastic gradient descent. Feel free to copy and examine it.
It computes the approximate weights w0 to wn for the function: w0 + w1x1 + w2x2 + … + wnxn = c

#include 
using namespace std;

#define MAX_TE 50 // maximum training examples
#define MAX_W 50 // maximum weights

// gradient descent for the expression w0 + w1x1 + w2x2 + w3x3 + w4x4 + ... + wnxn = ai

double a = 0.005; // learning rate 0.005 would converge to a global minima; however it takes more iterations
// You could also set the variable a to 0.0005 * (sum of ai) / i where (sum of ai) / i is actually the arithmetic
//of all examples. Then do a check whether a exceeds 1.0. If it exceeds 1.0 then it would be best to set 1.0, because //we will have pretty large values for the functions and we might not find a global minima enough fast(with less //iterations)

double examples[MAX_TE][MAX_W]; // training examples and x values for all of them
double ans[MAX_TE]; // answers of the functions
double weights[MAX_W];
int e,w;

double eval(int i)
{
    // evaluates the output with the current weights for example i
    double current = weights[0];
    for (int j = 1; j < w; ++j)
    {
        current += weights[j]*examples[i][j];
    }
    return current;
}

int main()
{
    cin >> e >> w;
    for (int i = 0; i < e; ++i)
    {
        for (int j = 1; j < w; ++j)
        {
            cin >> examples[i][j];
        }
        cin >> ans[i];
    }
    for (int i = 0; i < w; ++i)
    {
        // sets all weights to 0.0; we could set them any small random value: 0.001 0.1 0.02 and so on
        weights[i] = 0.0;
    }
    for (int p = 0; p < 500000; ++p)
    {
        // we will run the algorithm 500000 times in order to be sure that we have found the perfect weights.
        // you could add some more code to find convergence
        for (int i = 0; i < e; ++i)
        {
            double y = eval(i);
            // compute w0
            weights[0] = weights[0] +  a*(ans[i]-y);
            for (int j = 1; j < w; ++j)
            {
                // compute all weights from 1 to w
                weights[j] = weights[j] + a * (ans[i] - y) * examples[i][j];
            }
        }
    }
    for (int i = 0; i < w; ++i)
    {
        cout << "w" << i << " = " << weights[i] << " ";
    }
    return 0;
}

/*
EXAMPLE INPUT:
4 2
-1 0
0 1
1 2
2 1

OUTPUT:
w0 = 0.8 w1 = 0.4
*/

Указатели (референции и дереференции) в C++

След първоначалния урок за “референции” в C++“, който общо взето не говори нищо, реших да направя нов по-пълен “урок”. Ще се опитам да обясня защо те са много важни и къде се използват. Всяка променлива,константа,функция,масив,клас,структура и т.н. е записана в паметта в дадено “депо”.
Ето примерен код:

// Създаваме указател от тип int. Създаденият указател трябва да има същия тип на променливата към, която ще сочи.
int * pointer;
// Създаваме две променливи от тип int.
int ref1,ref2;
// Указателят сочи към адреса на ref1 (Указателят присвоява адреса на ref1 в паметта)
pointer = &ref1;
// Променяме съдържанието на на променливата, към чието място в паметта сочи указателя pointer
* pointer = 10;
// Указателят сочи към адреса на ref2 (Указателят присвоява адреса на ref2 в паметта)
pointer = &ref2;
// Променяме съдържанието на на променливата, към чието място в паметта сочи указателя pointer
* pointer = 20;

Указателите са изключително полезни при c/c++. Така вие имате достъп до паметта. Тук се включва и така наречената указателна аритметика. Това означава, че на даден указател можем да присвоим адреса на паметта на promenliva1. След това увеличаваме стойността на указателя и имаме достъп до promenliva2. Ще ви дам пример с масиви.

// създаваме указател
int * pointer;
// създаваме масив
int arr[5];
// на указателя се записва адреса на първия елемент на масива
pointer = &arr;
// на указателя се записва адреса на втория елемент на масива
pointer++
// на указателя се записва адреса на третия елемент на масива
pointer = &arr[2];
// ще променим стойността на четвъртия елемент на масива
*(pointer+1) = 20;
// ще присвоим на на указателя адреса на петия елемент
pointer = &arr + 4;

Ето така можем да сменяме стойностите на масив, както и на променливи.

Чрез указатели може да се заделя и динамична памет. В другия урок ще обясня за нея.
Могат да се създават указатели и на указатели.

int **p,*p2;
int a=5;
p2 = &a;
p = &p2;

Има и доста други възможности на указателите. Подробности за тях можете да видите тук :)

Референции в c++

Тук ще ви въведа в референциите в c++. Това са 2 много силни оператора в c++, които трябва да знаете за да продължите своето професионално развитие.
Референцията така да се каже е положението на даден запис в паметта. Примерно създаваме променлива а. За да покажем нейното съдържание просто пишем cout < < a; и готово. Но тази променлива има отредено място в паметта, която се опраделя от операционната система. За щастие ние програмистите не трябва да определяме нейното място, защото щеше да стане наистина доста по-сложно. В някои случаи се налага да видим нейният адрес в паметта и това става чрез специалния оператор &. Примерно пишем.

int a = 15;
int b = a;
int c = &a;

В нашия код a е равно на 15, b=15, но c е равно на адреса на променливата a, който примерно е 0x22ff74.
Това е всичко за референциите в c++. В следващия урок ще ви покажа повечко за дереференциите. Не карам уроците много-много под ред, тъй като трябва да покажа още доста неща преди референциите като основни математически операции, цикли, условни оператори.

C++ – структура на една програма

Ето първо малко код

#include <iostream>
using namespace std;
int main ()
{
int a,b;
cout < < “Vuvedi stoinost za a n”;
cin >> a;
cout < < “Vuvedi stoinost za b n”;
cin >> b;
cout < < a + b << endl;
system(“pause”);
return 0;
}

Сега ще обясня ред по ред:
#include <iostream> – инклудваме библиотеката iostream – която поддържа функциите cin и cout (за въвеждане и изкарване на информация. вход и изход.). Примерно можем да добавим само библиотеката ostream. Така ще можем да използваме функията cout. Можем също да инклудем и библиотеката istream. Така ще можем да използваме функцията cin.
В c++ има още много библиотеки и в зависимост какво искате да правите, те трябва да се включват. Включването на библиотеки е прието да става единствено в най-горният ред (по друг начин ще ви даде най-вероятно грешка).
using namespace std; – неймспейсовете (namespaces) са кутийки, които съдържат класове, функции, променливи. Ако напишете using namespace std; за всички класове, функции, променливи ще се ползва неймспейса std и няма да пишете примерно:

cout<<mynamespace:promenliva

. Отделно можете да създавате още “кутийки”, които да съдържат променливи, функции и класове и да ги викаш. Така при създаване на 2 променливи в 2 кутиийки те няма да се презапишат взаимно.
int main () { } – това е като основна функция.
int a,b; – декларираме променливите. Т.е. придаваме им какъв тип ще са (int – целочислено число) и какво име ще имат. В нашия случай ние създаваме променливите a и b, които са целочислени числа (16,0,15,-16,99999). На тези две променливи можем да придадем и друг тип – float, double, char и други. За тях може да се зададе и дали са unsigned или signed. Прието е променливите да са signed. Примерно ако a е signed int, то тази промелива може да обхваща числа от -2,147,483,648 до +2,147,483,648. Ако обаче е unsgined ще обхваща числа от 0 до 4,294,967,295. Внимавайте какви типове данни задавате на вашите променливи. Unsigned типовете заемат 2 пъти повече памет от signed. Ако числата ще са малки използвайте short int и т.н.
cout < < “Vuvedi stoinost za a n”; – изкарва информация в програмата. Примерно:

cout << “Hello World!” << “This is my first c++ program n”;
Можем да го запишем и директно
cout << “Hello World! This is my first c++ program n”;
n означа нов ред.
cout << “Hello World! This is my first c++ program n”;
е еквивалентно на
cout << “Hello World! This is my first c++ program”<<endl;

cin >> b; е за въвеждане на информация от потребителя. Примерно при изпълнение на този код от нас ще се иска да въведем число за b и да натиснем enter за да продължи изпълнението на програмата.
system(“pause”); – този ред означава, че програмата няма да се затвори автоматично при изпълнение.
return 0; – връща 0. Т.е. това е краят на програмата!
Е разгледайте кода, посетете официалния сайт на c++, има и доста онлайн уроци! Учетете и се развивайте!

Въведение в C++

Какво е c++?
C++ е език за програмиране от трета генерация.
Защо да изберете c++ ?
Защото пишейки на c++ ще се научите наистина да разбирате що е програмиране и какво представлява. Пишейки на c++ вие ще научите и повече за hardware-a – как рабооти, кое за какво. C++ е както базов, така и език за много напреднали. Т.е. на c++ можете да направите всичко, но за някои неща с други езици ще се справите по-бързо. И нещо по-интересно: PHP е писан на C (като c++ но минуси – по-малко възможни парадигми, проблеми с неймспейсове и т.н.), а facebook ще бъде пренаписан на c/c++ за да работи още по-бързо. Пишейки на c++ вие имате директен достъп до hardware-a на даден компютър и можете да се възползвате от всичката памет!
Ако сте писали на друг език php, java, pascal, basic или там квото друго можете да сте напипали през годините, то ще ви е по-лесно да работите на c++, особено ако сте писали на java макар и моделът малко да се различава.
Първоначално ще ви покажа една проста програмка за въвеждане на 2 числа от клавиатурата и връщане на техния сбор

#include <iostream>
using namespace std;
int main ()
{
int a,b;
cout < < "Vuvedi stoinost za a n"; cin >> a;
cout < < "Vuvedi stoinost za b n"; cin >> b;
cout < < a + b << endl; system("pause"); return 0; }

Това е една проста програмка. Най-вероятно нищо няма да разберете, но ви уверявам, че след няколко урока ще усвоите добре някои от основните неща в c++.
Само да спомена като допълнение. C++ се изучава в голяма част от училищата и в повечето университети. Така че е във ваш плюс да го научите :)