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
*/

Обхождане на двоично дърво в Java

Как се реализира двоично дърво можете да видите в книгата на Светлин Наков, а ето как да се обходи по три начина като 2 не са реализирани в книгата.
Съответно ЛДК (Ляво-Корен-Дясно/Pre-order), КЛД (Корен-Ляво-Дясно/In-order), ЛДК (Ляво-Дясно-Корен/Post-order)

public void printPreOrder(BinaryTreeNode<T> root) {
if (root == null) {
return;
}
printPreOrder(root.getLeftChild());

System.out.print(root.value + " ");

printPreOrder(root.getRightChild());
}

public void printPreOrder() {
printPreOrder(this.root);
}

public void printInOrder(BinaryTreeNode<T> root) {
if (root == null) {
return;
}
System.out.print(root.value + " ");

printInOrder(root.getLeftChild());

printInOrder(root.getRightChild());
}

public void printInOrder() {
printInOrder(this.root);
}

public void printPostOrder(BinaryTreeNode<T> root) {
if (root == null) {
return;
}
printPostOrder(root.getLeftChild());
if (root.leftChild != null) {
System.out.print(root.leftChild.value + " ");
}
if (root.rightChild != null) {
if (root.rightChild.leftChild != null) {
printPostOrder(root.rightChild);
}
System.out.print(root.rightChild.value + " ");
}
}

public void printPostOrder() {
printPostOrder(this.root);
System.out.println(this.root.value);
}

Проблем при сравнение на числа с плаваща запетая при MySQL

Докато работих по един клиентски проблем се оказа, че има проблем при “сравнение” на числата с плаваща запетая поне при MySQL. Може и да не е проблем, но някои хора може да се сблъскат с този проблем.
Да кажем, че искате да направите сайт за аукциони и искате да има графа “аукциони от 1 стотинка”. Това означава, че искате да вземете всички аукциони, които имат начална цена 0.01.
Обикновено вие (както и аз) бихте направили това:
SELECT * FROM auctions WHERE auction_start_price=0.01
Далеч не ви препоръчвам да си пишете така заявките, но това е друг въпрос. Реално няма да има никакви резултати дори в auctions.auction_start_price да има 0.01 в някои от редовете. Затова ще променим заявката така:
SELECT * FROM auctions WHERE ROUND(auction_start_price,2)=0.01
Сега всичко ще е наред. Друго решение е просто да посочите, че auction_start_price<0.02 и всичко щеше да е ок, но в някои случаи, ще е по-добър вариант закръглянето :)

Указатели (референции и дереференции) в 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;

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

Оптимизиране на вашата MySQL база данни

Тук ще ви дам няколко съвета за оптимизиране на вашите бази данни за по-добро бързодействие:

– Пишете кои полета искате да вземете при дадена SELECT заявка:

Примерно пишете SELECT product_id, product_price, product_name FROM products вместо SELECT * FROM products

– Използвайте колкото се може по-малко функции в дадена заявка

Не използвайте много функции, освен, ако не е супер наложително.

– Иползвайте индекс (index)

Индексите значително подобряват скоростта. Когато имате полета от дадена таблица, които участват често в WHERE клауза, им сложете по един index. Няма точна граница, но нека не са прекалено много. Ако предимно ще ъпдейтвате, триете, добавяте иформация във вашата база данни, то повечето индекси може да я забавят.

– Определяйте добре типовете данни

Примерно опделяйте добре дали дадено поле ще е int, tinyint, smallint, bigint, mediumint. Ако примерно дадено поле ще приема стойности от рода на от 0 до 25 то е хубаво това поле да е tinyint, тъй като приема стойности от -128 до +128, а по-големи числа няма да са ви нужни.

– Не правете подзаявки

Много често се случва, че вместо подзаявка, можете да направите всичко с 1 заявка и в допълнение JOIN.

– Вместо търсене с “Like” ползвайте Full-Text Search

С големи количества данни like работи изключително бавно. Сами по себе си двете търсения се различават. За да добиете по-добра представа е добре да прочетете документациите и на двете.

Тъй като е малко късно и ме мързи да пиша повече, това ще е засега. Скоро се предполага, че ще напиша още малко за оптимизиране на MySQL базите данни (наблягам на MySQL). Всичко друго – как се организира, структурира, зависи само от вас :)

Грешка с енкодинга при viroshop (ecommerce плугин за WordPress)

Наскоро имах поръчка да разширя възможностите на една ecommerce тема за wordpress – viroshop. Сблъсках се с проблема, че кукито се създава чрез javascript и има проблем с енкодинга. Не съм много на “ти” с енкодингите, но можеби това е стандартен unicode енкодинг. Общо взето всички символи излизат като %u0440 и подобни числа + букви. Ето и функцийка написана от мен за справяне с този проблем.

function fixen($title) {
$search = ‘%u0410,%u0411,%u0412,%u0413,%u0414,%u0415,%u0416,%u0417,%u0418,
%u0419,%u041A,%u041B,%u041C,%u041d,%u041E,
%u041F,%u0420,%u0421,%u0422,%u0423,%u0424,%u0425,%u0426,%u0427,
%u0428,%u0429,%u042A,%u042B,%u042C,
%u042E,%u042F,%u0430,%u0431,%u0432,%u0433,%u0434,%u0435,%u0436,
%u0437,%u0438,%u0439,%u043A,%u043B,
%u043C,%u043D,%u043E,%u043F,%u0440,%u0441,%u0442,%u0443,%u0444,
%u0445,%u0446,%u0447,%u0448,%u0449,
%u044A,%u044C,%u044E,%u044F’;
$replace = ‘А,Б,В,Г,Д,Е,Ж,З,И,Й,К,Л,М,Н,О,П,Р,С,Т,У,Ф,Х,Ц,Ч,Ш,Щ,Ъ,Ы,Ь,Ю,Я,а,б,в,
г,д,е,ж,з,и,й,к,л,м,н,о,п,р,с,т,у,ф,х,ц,ч,ш,щ,ъ,ь,ю,я’;
$search = explode(‘,’,$search);
$replace = explode(‘,’,$replace);
$title = str_replace($search, $replace, $title);
return $title;
}

Дано е помогнала.

Референции в 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++, има и доста онлайн уроци! Учетете и се развивайте!