Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
0 / 0 / 0
Регистрация: 08.10.2018
Сообщений: 4
1

Оценка времени поиска и удаления в упорядоченном бинарном дереве

22.02.2019, 14:50. Показов 567. Ответов 0
Метки нет (Все метки)

В общем и целом, моя проблема следующая, делаю сейчас лабораторную работу по дисциплине ТРПС, в ней требуется рассчитать (после того, как написали алгоритм) количество тактов данного алгоритма (время поиска, среднее). Мне досталось бинарное упорядоченное дерево. Алгоритм поиска у меня последовательный, я реализовал прямой обход дерева - слева направо.

Вот листинг:
C++
1
2
3
4
5
6
7
void find(int a, node **t)
{
    if ((*t)->info == a) cout << endl << (*t)->info << endl;
 
    if ((*t)->left != NULL) find(a, &(*t)->left);
    if ((*t)->right != NULL) find(a, &(*t)->right);
}
В условии удаления по лабе - исключение неполной вершины. Я решил сделать это по аналогии поиска, то есть вбиваем ключ, который мы хотим удалить и если эта вершина является неполной в дереве, то мы удаляем листья этой вершины, а потом саму вершину.

Вот листинг:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void del(int a, node **t)
{   
    if ((*t)->info == a && ((*t)->left == NULL || (*t)->right == NULL) || (*t)->left == NULL && (*t)->right == NULL && (*t)->info == a)
    {
        if ((*t)->left != NULL) del(a, &(*t)->left);
        if ((*t)->right != NULL) del(a, &(*t)->right);
        (*t) = NULL;
        return;
    };
 
    if ((*t)->left != NULL) del(a, &(*t)->left);
    if ((*t)->right != NULL) del(a, &(*t)->right);
}
Основная структура дерева:
C++
1
2
3
4
5
struct node
{
    int info;
    node *left, *right;
};
Алгоритм построения упорядоченного дерева:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void push(int a, node **t)
{
    if ((*t) == NULL)
    {
        (*t) = new node;
        (*t)->info = a;
        (*t)->left = (*t)->right = NULL;
        return;
    }
 
    if (a > (*t)->info) push(a, &(*t)->right);
    else push(a, &(*t)->left);
}

Помогите пожалуйста вывести формулу для среднего времени поиска и удаления по этим алгоритмам.
В интернетах ничего не нашел, вообще не знаю как это сделать :c
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.02.2019, 14:50
Ответы с готовыми решениями:

Поиск в случайном бинарном дереве. Оценка алгоритма
Здравствуйте! Подскажите пожалуйста, каким образом можно оценить этот алгоритм(поиск в...

Вывести К-тый отрицательный элемент в упорядоченном дереве поиска с просмотром TLR
Должен выводиться К-тый отрицательный элемент в упорядоченном дереве поиска с просмотром TLR ...

Рекурсия в бинарном дереве поиска
public boolean add(E e) { if(this.root == null) { this.root = new Node(e, null) ; return...

Функция поиска в бинарном дереве
Я понимаю как реализовать эту функцию если в бинарном дереве хранятся обычные числа(последовательно...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.02.2019, 14:50

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Алгоритм поиска в бинарном дереве
Помогите написать программу на Delphi, please

Индексатор в бинарном дереве поиска
Сделал бинарное дерево поиска на C#, есть перечисление (IEnumerable) элементов в порядке...

Поиск ключа в бинарном дереве поиска
Здравствуйте! Помогите ещё с задачками) 1.Поиск ключа в бинарном дереве поиска (точное...

Необычная функция в бинарном дереве поиска
Здравствуйте, уважаемые форумчане. Очень прошу Вашей помощи. Задание: Реализовать структуру...

Найти сумму листьев в бинарном дереве поиска
Дано бинарное дерево поиска(ключи-целые числа).Найти сумму листьев. Вот мой код.Но он не...

Нахождение следующего и предыдущего элемента в бинарном дереве поиска
Нужны 2 ф-ции: нахождение следующего и предыдущего элемента в дереве. Вот мой код. Помогите...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.