Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Rec_cm
1 / 1 / 3
Регистрация: 15.08.2016
Сообщений: 97
Завершенные тесты: 1
1

Реализация бинарного древа с помощью рекурсии чревата переполнением стека?

25.05.2017, 21:55. Просмотров 394. Ответов 9
Метки нет (Все метки)

В реализации бинарного древа с помощью рекурсии (использования рекурсии в процессе написании функций бинарного древа) черевато переполнением стека? Зачем тогда ввели такую реализацию (теперь потянуло на демагогию). А почему, тогда при обычной реализации, заменяя рекурсию стеком у нас не выходит такой же вылет? Ведь у памяти и там и там фиксированный размер.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.05.2017, 21:55
Ответы с готовыми решениями:

Реализация стека с помощью массива
Извиняюсь. Неправильно тему назвал :) Стек – KStack Методы: конструкторы, деструктор;...

Редкая ошибка, связанная с переполнением стека
Значит ситуация такая, вот весь код он полностью рабочий, но для перегрузки потокового ввода...

Ошибка с переполнением стека
Тут такое дело...в-общем, вот условие: В исходном файле сначала идёт число n - общее количество...

Как бороться с переполнением стека
Мне нужно понять как бороться с переполнением стека. Есть управляющая процедура. изначально она...

Как бороться с переполнением стека
Доброго времени суток! Помогите, пожалуйста, с программой! В паскале происходит переполнение...

9
Nikitko_Cent
145 / 115 / 37
Регистрация: 27.10.2011
Сообщений: 690
Завершенные тесты: 3
25.05.2017, 22:05 2
Цитата Сообщение от Rec_cm Посмотреть сообщение
А почему, тогда при обычной реализации, заменяя рекурсию стеком у нас не выходит такой же вылет? Ведь у памяти и там и там фиксированный размер.
Системный стек сверху ограничен несколькими мегабайтами (1-2 обычно), пользовательская реализация - несколькими гигабайтами (если учитывать только размер оперативной памяти, и не приплетать сюда подкачку и прочее)

Добавлено через 4 минуты
Цитата Сообщение от Rec_cm Посмотреть сообщение
В реализации бинарного древа с помощью рекурсии (использования рекурсии в процессе написании функций бинарного древа) черевато переполнением стека?
Обход дерева (необязательно бинарного) в глубину с использованием стека чревато
1
Rec_cm
1 / 1 / 3
Регистрация: 15.08.2016
Сообщений: 97
Завершенные тесты: 1
25.05.2017, 22:09  [ТС] 3
Nikitko_Cent, Спасибо)
0
Геомеханик
811 / 614 / 940
Регистрация: 26.06.2015
Сообщений: 1,409
26.05.2017, 05:31 4
На практике вставка, удаление, прохождение по всему дереву не используется рекурсия, а заводиться в узле(Node) дополнительный указатель на родителя parent.
Цитата Сообщение от Rec_cm Посмотреть сообщение
Зачем тогда ввели такую реализацию (теперь потянуло на демагогию).
Для наглядного представления начинающим программистам!
0
Antikl
с++
663 / 378 / 180
Регистрация: 15.07.2015
Сообщений: 2,026
Завершенные тесты: 6
26.05.2017, 08:08 5
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<iostream>
using namespace std;
struct  node
{
  int Key;
  int Count;
  node *Left;
  node *Right;
};
 
class TREE
{
  private:
    node *Tree; //Указатель на корень дерева.
    void Search (int,node**);
  public:
    TREE() {Tree=NULL;}
    node** GetTree () {return &Tree;} //Получение вершины дерева.
    void BuildTree ();
    void CleanTree (node **);
    void ObhodEnd (node **);
    void ObhodLeft (node **);
    void ObhodBack (node **);
    void Vyvod (node**,int);
    int Height (node**);
};
 
void main ()
{
    setlocale(LC_ALL,"");
  TREE A;
 
  A.BuildTree ();
  cout<<"\nВывод дерева:\n";
  A.Vyvod (A.GetTree(),0);
  cout<<"\nВысота дерева:"<<A.Height(A.GetTree())<<endl;
  cout<<"\nЛевосторонний обход дерева: ";
  A.ObhodLeft (A.GetTree());
  cout<<"\nКонцевой обход дерева: "; A.ObhodEnd (A.GetTree());
  cout<<"\nОбратный обход дерева: "; A.ObhodBack (A.GetTree());
  A.CleanTree (A.GetTree());
}
 
void TREE::BuildTree ()
// Построение бинарного дерева (рекурсивный алгоритм).
// Tree - указатель на корень дерева.
{
  int el;
 
  cout<<"Вводите ключи вершин дерева ...\n";
  cin>>el;
  while  (el!=0)
  { Search (el,&Tree); cin>>el; }
}
 
void TREE::Search (int x,node **p)
//  Поиск вершины с ключом x в дереве со вставкой
//             (рекурсивный алгоритм).
// *p - указатель на корень дерева.
{
  if  (*p==NULL)
  {// Вершины в дереве нет; включить ее.
    *p = new(node);
    (**p).Key = x;     (**p).Count = 1;
    (**p).Left = NULL; (**p).Right = NULL; }
  else
    if  (x<(**p).Key) Search (x,&((**p).Left));
    else
      if  (x>(**p).Key) Search (x,&((**p).Right));
      else  (**p).Count = (**p).Count + 1;
}
 
void TREE::ObhodLeft (node **w)
//Левосторонний обход дерева.
//*w - указатель на корень дерева.
{
  if  (*w!=NULL)
  {
    cout<<(**w).Key<<" ";
    ObhodLeft (&((**w).Left));
    ObhodLeft (&((**w).Right));
  }
}
 
void TREE::ObhodEnd (node **w)
//Концевой обход дерева.
//*w - указатель на корень дерева.
{
  if  (*w!=NULL)
  { ObhodEnd (&((**w).Left));
    ObhodEnd (&((**w).Right));
    cout<<(**w).Key<<" "; }
}
 
void TREE::ObhodBack (node **w)
//Обратный обход дерева.
//*w - указатель на корень дерева.
{
  if  (*w!=NULL)
  { ObhodBack (&((**w).Left));
    cout<<(**w).Key<<" ";
    ObhodBack (&((**w).Right)); }
}
 
void TREE::CleanTree (node **w)
//Очистка дерева.
//*w - указатель на корень дерева.
{
  if  (*w!=NULL)
  { CleanTree (&((**w).Left));
    CleanTree (&((**w).Right));
    delete *w; }
}
 
void TREE::Vyvod (node **w,int l)
//Изображение дерева *w на экране дисплея
//          (рекурсивный алгоритм).
//*w - указатель на корень дерева.
{
  int i;
 
  if  (*w!=NULL)
  { Vyvod (&((**w).Right),l+1);
    for  (i=1; i<=l; i++) cout<<"   ";
    cout<<(**w).Key<<endl;
    Vyvod (&((**w).Left),l+1); }
}
 
int TREE::Height (node **w)
//Определение высоты бинарного дерева.
//*w - указатель на корень дерева.
{
  int h1,h2;
  if  (*w==NULL) return (-1);
  else
  {
    h1 = Height (&((**w).Left));
    h2 = Height (&((**w).Right));
    if  (h1>h2) return (1 + h1);
    else  return (1 + h2);
  }
}
0
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
8033 / 3929 / 541
Регистрация: 04.12.2011
Сообщений: 11,494
Записей в блоге: 9
26.05.2017, 15:46 6
Цитата Сообщение от Геомеханик Посмотреть сообщение
Для наглядного представления начинающим программистам!
А мне нравится.
Если не сбалансированное то может быть и плохо. И повторений не должно быть много (иначе плохой предикат сравнения). Это точно. А иначе количество уровней (рекурсий) это бинарный логарифм количества нодов. То есть не так всё плохо как, наоборот - хорошо. Траверс в глубину это вещь (мудрая мысль!). Ведь (рекурсивно == быстро) это единица?
0
Rec_cm
1 / 1 / 3
Регистрация: 15.08.2016
Сообщений: 97
Завершенные тесты: 1
26.05.2017, 22:43  [ТС] 7
IGPIGP, Т.е. вы склоняетесь к мнению что рекурсия это хорошо, в бинарном древе? Например, задача запрограммировать библиотеку или разместить числа по возрастанию? Кстати, набрел на вопрос. Вот нам дан массив элементов, адекватно его записывать в бинарное древо и сортировать или проще воспользоваться быстрой сортировкой, элементов у нас, например 1*10^12?
0
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
8033 / 3929 / 541
Регистрация: 04.12.2011
Сообщений: 11,494
Записей в блоге: 9
26.05.2017, 23:02 8
Цитата Сообщение от Rec_cm Посмотреть сообщение
IGPIGP, Т.е. вы склоняетесь к мнению что рекурсия это хорошо, в бинарном древе?
Как сказали вначале, для новичков хорошо. И плохо. Хорошо потому что они (новички) не задумываются о размере стека и можно учить суть не загромождая голову лишними (вначале) деталями. А плохо потому, что редкий новичок напишет R&B или AVL. То есть без само-балансировки вопрос глубины рекурсии - вопрос вероятности, - деревья и хеш-массивы имеют общую слабость. Они зависят от порядка заполнения.
А для самобалансированной (и без повторений) структуры размер равен 2^n где n -количество уровней . Если предельный размер массива/вектора это unsigned int (size_type зависит от реализации но допустим ->) то это 2^32.
То есть для размещения числа UINT_MAX элементов потребуется структура не превышающая 32 уровня. Если я не ошибаюсь (что происходит частенько, надо сказать).

Добавлено через 5 минут
Цитата Сообщение от Rec_cm Посмотреть сообщение
Вот нам дан массив элементов, адекватно его записывать в бинарное древо и сортировать или проще воспользоваться быстрой сортировкой, элементов у нас, например 1*10^12?
Если уже есть массив то быстрая сортировка лучше.(imho)
Тем более она уже есть в алгоритмах.
Правда я не могу понять как создать такой большой массив. Но наверно, на системе где это возможно, можно использовать и qsort. А дереву это нестрашно.
1
Rec_cm
1 / 1 / 3
Регистрация: 15.08.2016
Сообщений: 97
Завершенные тесты: 1
26.05.2017, 23:51  [ТС] 9
IGPIGP, а база данных (например psql) построенна на принципе бинарного древа? где оно может быть полезно (вопрос глупый, но интересный )
0
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
8033 / 3929 / 541
Регистрация: 04.12.2011
Сообщений: 11,494
Записей в блоге: 9
27.05.2017, 00:09 10
Цитата Сообщение от Rec_cm Посмотреть сообщение
IGPIGP, а база данных (например psql) построенна на принципе бинарного древа?
База данных это как минимум три уровня начиная от хранения. Размещение в памяти может быть и деревом наверное. Тем более что параметр для сравнения это ключ уникальность которого гарантируется (или по кр мере очень маловероятна не уникальность), как я понимаю. То есть вырождение в список не угрожает ни на одном из участков.
Цитата Сообщение от Rec_cm Посмотреть сообщение
где оно может быть полезно (вопрос глупый, но интересный )
Как структура поиска и хранения. Легче всего искать в массиве (упорядоченном), но в него сложно добавлять. В список легко добавлять, но сложно искать. BST это хороший компромисс. В нем относительно гадко и то и другое. Но лучше чем или то или другое.
1
27.05.2017, 00:09
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.05.2017, 00:09

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

Переполнением стека при вычислении функции с через рекурсию!
Нужно написать программу для вычисления с помощью рекурсии: 1/a+1/a*(a+1)+...+1/a*(a+1)*...*(a+n)!...

Реализация стека целых чисел. Процедура добавления нового элемента, удаление, вывод стека
Попросили написать программку, но, паскаль очень давно не практикую, поэтому прошу тут: Надо...

Организовать поиск и печать ветвей генеалогического древа с помощью обхода графа в «глубину»
Генеалогическое дерево некоторого рода представлено графом не более 12 вершин. Узел каждой вершины...


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

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

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