2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Двоичное дерево поиска
Сообщение11.08.2017, 13:48 


21/05/16
4292
Аделаида
Пожалуйста, помогите понять следующий код:
код: [ скачать ] [ спрятать ]
Используется синтаксис Python
class Tree:
 
    def __init__(self, value, root=None):
        self.lchild = None
        self.rchild = None
        self.value = value
        self.root = root
 
    def add(self, value):
        current_node = self
        last_node = None
        while current_node:
            last_node = current_node
 
            if value > current_node.value:
               current_node = current_node.rchild
            elif value < current_node.value:
                 current_node = current_node.lchild
            else:
                return False
     new_node = Tree(value, last_node)
        if value > last_node.value:
           last_node.rchild = new_node
        else:
            last_node.lchild = new_node
            return True

Спасибо!

 Профиль  
                  
 
 Re: Двоичное дерево поиска
Сообщение11.08.2017, 13:50 
Заслуженный участник
Аватара пользователя


06/10/08
6422
А что именно Вы в этом коде не понимаете?

 Профиль  
                  
 
 Re: Двоичное дерево поиска
Сообщение11.08.2017, 13:52 


21/05/16
4292
Аделаида
Конкретно:
kotenok gav в сообщении #1239959 писал(а):
root=None

kotenok gav в сообщении #1239959 писал(а):
current_node = self
last_node = None

kotenok gav в сообщении #1239959 писал(а):
while current_node:

 Профиль  
                  
 
 Re: Двоичное дерево поиска
Сообщение11.08.2017, 14:36 
Заслуженный участник
Аватара пользователя


06/10/08
6422
А где Вы этот код взяли? Неужели никаких пояснений нет?

Насколько я понял, root - это указание родителя вершины. По умолчанию мы создаем новое дерево, и root ставим None - новое дерево ни к чему не привязано. А вот например в строке new_node = Tree(value, last_node) мы создаем новую вершину в существующем дереве.

current_node и last_node - что Вам непонятно? мы идем по дереву, храня текущее место и предыдущее. В начале current_node - это вершина, для которой вызвали add, т.е. self, а last_node ненужна, поэтому мы устанавливаем ее в None
Вообще, две переменные не обязательны, можно использовать только одну, разберитесь сами, как.

while current_node: - это использует то, что в питоне None - это ложное значение, а определенные пользователем объекты - истинные, если не сказано иначе. Чтобы было понятнее, можно переписать как while current_node is not None:

 Профиль  
                  
 
 Re: Двоичное дерево поиска
Сообщение11.08.2017, 14:43 


21/05/16
4292
Аделаида
Спасибо!
Кстати, а что такое "elif"?

 Профиль  
                  
 
 Re: Двоичное дерево поиска
Сообщение11.08.2017, 14:46 
Заслуженный участник


09/05/12
25179
kotenok gav в сообщении #1239994 писал(а):
Кстати, а что такое "elif"?
"Сокращение" от else if.

 Профиль  
                  
 
 Re: Двоичное дерево поиска
Сообщение14.08.2017, 19:27 
Аватара пользователя


17/04/11
658
Ukraine
Xaositect в сообщении #1239993 писал(а):
Вообще, две переменные не обязательны, можно использовать только одну, разберитесь сами, как.

Вы не представляете, как это выглядит со стороны. :lol: «Объясните, пожалуйста». — «Разбирайтесь сами».

-- Mon Aug 14, 2017 19:47:25 --

Мне тоже было трудно понять код. На функциональном япе он выглядит элегантнее, потому что там разделены изменяемые и неизменяемые типы данных. Вообще императивность не добавляет ясности. Для сравнения привожу код на Standard ML:
Используется синтаксис OCaml
datatype 'a tree_set = tip |
         node of {value : 'a,
                  left : 'a tree_set ref, right : 'a tree_set ref};
fun add a =
  let fun loop t =
        case ! t of
            tip => (t := node {value = a,
                               left = ref tip, right = ref tip};
                    true)
          | node n => if a < #value n then loop (#left n)
                      else if a > #value n then loop (#right n)
                      else false
  in loop end

В узле дерева лежат не просто поддеревья, а ячейки («ref»), содержащие поддеревья. Содержимое ячеек менять можно, компоненты узла дерева менять нельзя. Функция «add» находит ячейку, которая должна содержать «a». Если эта ячейка содержит «tip» (аналогичен «None» в Python), тогда заменяем её содержимое на новый узел, содержащий «a». В Python метод «add» находит некий «last_node». Так вот, та ячейка, которую находит функция «add» в Standard ML, соответствует правому или левому компоненту «last_node». Какому именно компоненту, определяется последним «if». Этот «if» лишний с точки зрения Standard ML.

В Standard ML можно манипулировать ячейкой. Аналогичный код можно написать на C, в качестве ячейки будет указатель на компонент узла дерева. В Python так сделать нельзя, потому что в Python сборка мусора автоматическая, и для сборщика мусора нужно, чтобы каждый указатель указывал на целый объект кучи, а не на его компоненты.

 Профиль  
                  
 
 Re: Двоичное дерево поиска
Сообщение15.08.2017, 11:39 


21/05/16
4292
Аделаида
Xaositect в сообщении #1239993 писал(а):
while current_node: - это использует то, что в питоне None - это ложное значение, а определенные пользователем объекты - истинные, если не сказано иначе. Чтобы было понятнее, можно переписать как while current_node is not None:

А бесконечного цикла, случайно, не получится? А то во время while, current_node разве когда-нибудь станет None?

 Профиль  
                  
 
 Re: Двоичное дерево поиска
Сообщение15.08.2017, 11:43 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Дерево-то у нас конечное, рано или поздно доберёмся до листьев.

 Профиль  
                  
 
 Re: Двоичное дерево поиска
Сообщение15.08.2017, 12:02 


21/05/16
4292
Аделаида
А почему в листьях current_node будет None?

 Профиль  
                  
 
 Re: Двоичное дерево поиска
Сообщение15.08.2017, 12:10 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Потому что не будет соответствующих lchild И rchild, насколько я понимаю код.

 Профиль  
                  
 
 Re: Двоичное дерево поиска
Сообщение15.08.2017, 12:19 


21/05/16
4292
Аделаида
Я сейчас немного модифицировал этот код, чтобы он осуществлял сортировку бинарным деревом. Он будет работать?
код: [ скачать ] [ спрятать ]
Используется синтаксис Python
class Tree:
    def _init_(self, value, root = None):
        self.lchild = None
        self.rchild = None
        self.value = value
        self.root = root
    def add(self, value):
        current_node = self
        last_node = None
        while current_node:
            last_node = current_node
            if value < current_node.value:
                current_node = current_node.lchild
            else:
                current_node = current_node.rchild
        new_node = Tree(value, last_node)
        if value > last_node.value:
            last_node.rchild = new_node
        else:
            last_node.rchild = new_node
    def write(self):
        if self.lchild == None:
            if self.rchild == None:
                return self.value
            else:
                return self.value + self.write(self.rchild)
        else:
            if self.rchild == None:
                return self.write(self.lchild) + self.value
            else:
                return self.write(self.lchild) + self.value + self.write(self.rchild)
print('Insert number of numbers')
n = int(input())
print('Insert 1-st number')
a1 = float(input())
root = Tree(a1)
for i in range(2, n + 1):
    a = float(input())
    root.add(a)
root.write()

 Профиль  
                  
 
 Re: Двоичное дерево поиска
Сообщение15.08.2017, 12:35 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
А вы проверьте ;-)

(Спойлер)

Одна ошибка, не дающая программе продолжить работу, вылезет сразу.

 Профиль  
                  
 
 Re: Двоичное дерево поиска
Сообщение15.08.2017, 12:49 


21/05/16
4292
Аделаида
Eclipse сказал, что в строчке "root = Tree(a1)" нет аргументов.
Но a1 - аргумент, ведь так?
Тогда почему код выдает ошибку?

 Профиль  
                  
 
 Re: Двоичное дерево поиска
Сообщение15.08.2017, 12:59 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Нашёл очень смешную ошибку. Вы откуда код копировали-то? В определении класса у вас _init_ там, где должно быть __init__.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 31 ]  На страницу 1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group