Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > зачем нужны бинарные деревья?

Автор: Podarochek 7.3.2008, 00:07

Уважаемые, гуру, подскажите пожалуйста, зачем нужны бинарные деревья...ибо посмотрел (учить надобно), а мотивации нету smile

Автор: v2v 7.3.2008, 00:15

для поискать, сортировки.

Автор: andrew_121 7.3.2008, 01:02

Бинарное дерево, это единственная в своем роде структура представления данных.
Смотри:http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE

Автор: Podarochek 7.3.2008, 01:40

единственная то понятно...в чем есть гуд..т.е. какие Приимущества smile

Автор: jonie 7.3.2008, 01:52

напиши словарь (ну там словарь даля попарси). попробуй реализовать "базу данных" в дереве и в queue (ну или vector).... сделай поиск (выводя количество сравнений). почувствуй разницу)

Автор: andrew_121 7.3.2008, 03:50

Вот пример:

Код


A = 1 + 3 * (B - 7);

         A
         |
         *
        / \
       /    \
      /       \
     /          \
    +             -
   /  \         /   \
 1     3       B     7

Вот классический пример...
Удачного обучения...

Автор: Fazil6 7.3.2008, 10:02

andrew_121, разве так?

Автор: LED 7.3.2008, 12:23

Действительно, это выражение в дерево раскладывается так

Код


                  A
                  |
                  +
                /    \
              /        \
             1         *
                       /  \
                     /      \
                    3       -
                            /  \
                          /     \
                         B      7

а ты нарисовал дерево для A = (1+3)*(B-7)

Автор: sergejzr 7.3.2008, 12:58

Цитата(Podarochek @ 6.3.2008, 23:07

)

Уважаемые, гуру, подскажите пожалуйста, зачем нужны бинарные деревья...ибо посмотрел (учить надобно), а мотивации нету

Поиск - одно из применений. Если данные в таком дереве правильно расположены, то ты всегда знаешь, что находясь в любом узле дерева, слева от тебя все значения больше, а с права меньше, чем значение узла.

Код


        
         10
        / \
       /    \
      /       \
     /          \
    15             7
   /  \         /   \
 22     14       9     3

к примеру ищем число 9, Начинаем с корня. 9 меньше 10 (9<10) а значит следующий шаг надо сделать неправо. Попадаем в 7, 9 больше семи, значит следующий шаг делаем налево. Ура, нашли smile

А если детей у узла больше нет, значит и искомого в дереве нет.
В обоих случаях мы за два шага мы проверили целое дерево.

Автор: baldina 7.3.2008, 14:09

бинарные деревья - наиболее общая (и простая) "деревянная" структура (любое дерево можно привести к бинарному).
Вообще деревья характеризуются удачным соотношением временнОй сложности основных операций: вставка, удаление, поиск.
std::map и std::set нередко построены на RB-деревьях (red/black, есть такая разновидность)
Вобщем полезная структура данных, изучай.