принцип работы деревьев в Си (?)

Discussion in 'С/С++, C#, Rust, Swift, Go, Java, Perl, Ruby' started by Дикс, 24 Jul 2007.

  1. Дикс

    Дикс Elder - Старейшина

    Joined:
    16 Apr 2006
    Messages:
    1,194
    Likes Received:
    227
    Reputations:
    26
    Изучил списки структур, стек, но не могу понять принцип работы с деревьями.
    Я скачал пример работы с ними - создание, чтение, сравнение, но когда разбираю пример создания - получается что запись всё время ведётся в левую ветвь. Поэтому не понимаю смысл такого дерева.

    Есть одна мысль о том что запись ведётся сначала в левую ветвь, потом в правую, затем они обретают ещё по две ветки и запись ведётся по очереди в новые 4 ветки. Так делается?

    и, если знаете, дайте ссылки пожалусто на внятные тексты по работе с деревьями.
     
  2. ZaCo

    ZaCo Banned

    Joined:
    20 Jun 2005
    Messages:
    737
    Likes Received:
    336
    Reputations:
    215
    а какие деревья тебя интересуют: двоичного поиска, сбалансированные, идеально сбалансированные, общего вида или какие? я так понял двоичного вида, но тогда добавление узла ты определяешь сам... будучи деревом поиска, то влево идем если значение ключа меньше текущего узла и вправо, если наоборот.
    если все время влево идет, то ты получается добавляешь в корень что-то типа последовательности "10 9 8 7"; тут дерево проявляет себя как список со сложностью поиска o(n) и смысла в дереве поиска нет вообще. читай про сбалансированные деревья.
    зы на википедии по-моему все более-менее внятно написано.
     
    2 people like this.
  3. Дикс

    Дикс Elder - Старейшина

    Joined:
    16 Apr 2006
    Messages:
    1,194
    Likes Received:
    227
    Reputations:
    26
    спасибо, узнал про дерево поиска. тока как его заполняют? предварительно отсортированным массивом? и даёт ли это прирост скорости в поиске.
     
  4. da_ff

    da_ff Elder - Старейшина

    Joined:
    11 Jul 2006
    Messages:
    118
    Likes Received:
    22
    Reputations:
    26
    заполнять нада по индексу дерево поиска с учетом что индекс каждой вершный уникален для данного дерева. условие заполнения следующее если индекс эллемента подлежащего включению в дерево меньше текущего элемента дерева то перемещаемся для анализа на его левого потомка, если больше то на правого и так до тех пор пока не найдем вершину у которой будет отсутствовать тот потомок который надо проанализировать на это место его и прикрепляем. а время полного перебора если не изменяет память Ln(кол-во узлов).
    не мое просто нашел на винте по теме Модуль с работы с деревьями
     
    #4 da_ff, 24 Jul 2007
    Last edited: 24 Jul 2007
Loading...