Форум программистов, компьютерный форум CyberForum.ru

Splay-tree (написать программу, которая будет искать в файле сущности (целые числа) и заносить их в дерево) - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Синтаксический анализатор http://www.cyberforum.ru/cpp-beginners/thread878544.html
Помогите решить, пожалуйста. Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом (функция M воз-вращает максимальный из своих параметров, а функция m — минимальный): <выражение> ::= <цифра> | M(<выражение> , <выражение>) | m(<выражение> , <выражение>)
C++ Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной народ помогите пожалуйста написать программу на с++ на графы дана матрица смежности и неориентированный граф. выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной. http://www.cyberforum.ru/cpp-beginners/thread878542.html
C++ ACCESS_VIOLATION при решении задачи
Здравствуйте!Тут решал одну простую задачу, но на dl.gsu.by она не проходит последний тест:не пройден 10-й тест. Решение вызвало ошибку ACCESS_VIOLATION Вот сама задача: Входной файл: input.txt Выходной файл: output.txt Время на тест: 2 секунды Ограничение на память: 16 МБ Задан неориентированный взвешенный граф G. В графе возможно наличие нескольких ребер между одной и той же парой...
C++ Перегрузка (бинарный, дружественный оператор)
В классе Ellipse перегрузить оператор - (бинарный, дружественный оператор)
C++ Указатели. Из трех введенных с клавиатуры чисел преподнести в квадрат отрицательние а положительные оставити без изменений http://www.cyberforum.ru/cpp-beginners/thread878479.html
Из трех введенных с клавиатуры чисел преподнести в квадрат отрицательние а положительные оставити без изменений
C++ Преобразовать массив таким образом, чтобы в его первой половине расположились элементы, стоящие в четных позициях Всем привет. Не знаю как сделать одно из 4 заданий по работе с массивами: 4)превратить массив таким образом, чтобы в его первой половине расположились элементы, стоящие в четных позициях, а во второй половине-элементы стоящие в нечетных позициях Подскажите пожалуйста,что и как делать.Буду очень благодарен подробнее

Показать сообщение отдельно
Sato
0 / 0 / 0
Регистрация: 10.12.2012
Сообщений: 18
26.05.2013, 17:39  [ТС]     Splay-tree (написать программу, которая будет искать в файле сущности (целые числа) и заносить их в дерево)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
struct node // структура для представления узлов дерева
{
    int key;
    unsigned char height;
    node* left;
    node* right;
    node(int k) { key = k; left = right = 0; height = 1; }
};
 
unsigned char height(node* p)
{
    return p?p->height:0;
}
 
int bfactor(node* p)
{
    return height(p->right)-height(p->left);
}
 
void fixheight(node* p)
{
    unsigned char hl = height(p->left);
    unsigned char hr = height(p->right);
    p->height = (hl>hr?hl:hr)+1;
}
 
node* rotateright(node* p) // правый поворот вокруг p
{
    node* q = p->left;
    p->left = q->right;
    q->right = p;
    fixheight(p);
    fixheight(q);
    return q;
}
 
node* rotateleft(node* q) // левый поворот вокруг q
{
    node* p = q->right;
    q->right = p->left;
    p->left = q;
    fixheight(q);
    fixheight(p);
    return p;
}
 
node* balance(node* p) // балансировка узла p
{
    fixheight(p);
    if( bfactor(p)==2 )
    {
        if( bfactor(p->right) < 0 )
            p->right = rotateright(p->right);
        return rotateleft(p);
    }
    if( bfactor(p)==-2 )
    {
        if( bfactor(p->left) > 0  )
            p->left = rotateleft(p->left);
        return rotateright(p);
    }
    return p; // балансировка не нужна
}
 
node* insert(node* p, int k) // вставка ключа k в дерево с корнем p
{
    if( !p ) return new node(k);
    if( k<p->key )
        p->left = insert(p->left,k);
    else
        p->right = insert(p->right,k);
    return balance(p);
}


На просторах Хабра была найдена вот такая реализация АВЛ дерева, но с ней возникли те же проблемы, что и со Splay-ем. В частности, совершенно не понимаю добавления элемента\вывода элементов на экран. В своё время с горем пополам разобрался с линейный списком, но там всё было куда более прозаичным. Опять же, вроде алгоритмически понятно что сделано в примере и как к этому подключиться, но на практике сталкиваюсь с тем, что понятия не имею, как собственные значения направить в дерево.
 
Текущее время: 01:14. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru