Рекурсивное дерево поиска

@Raia · Регистрация: 16.04.2015

Студворк — интернет-сервис помощи студентам

Всем добра

На днях я решил познакомиться с Python и сейчас столкнулся со следующей проблемой: при создании вершин в дереве они создаются локально, без привязки к уже существующим вершинам, т.е число вроде и добавляется, но не в дерево, а непонятно куда

Что не так с функцией insert?

Python
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
class node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.color = 'red'
 
 
class rb:
    def __init__(self):
        self.root = None
        self.count = 0
 
    def insert(self, x):
        def add(n, x):
            if n is None:
                n = node(x)
            else:
                add(x > n.val and n.right or n.left, x)
 
        add(self.root, x)
 
    def find(self, x):
        def lookup(n, x):
            if n is None:
                return False
            else:
                if n.val == x:
                    return True
                return lookup(x > n.val and n.right or n.left, x)
        return lookup(self.root, x)

@smlprog · 29.04.2016, 09:32

Python
1
2
3
4
5
def add(n, x):
            if n is None:
                n = node(x)
            else:
                add(x > n.val and n.right or n.left, x)

Этот код не имеет смысла.

Python
1
n = node(x)

создаёт ноду и переопределяет привязку имени n в локальной области видимости функции add, ничего не делая собственно с деревом.

@Raia · 29.04.2016, 18:31 **[ТС]**

Я примерно об этом и писал в шапке топика..
Разве параметры не передаются по ссылке? Непонятно

Как тогда переписать этот код под реалии Питона?

@alex925 · 29.04.2016, 18:47

Сообщение от Raia

Разве параметры не передаются по ссылке?

По ссылке передаются изменяемые типы данных (списки, словари и т д), а числа, строки и т д копируются.

@smlprog · 29.04.2016, 20:01

Сообщение от Raia

Разве параметры не передаются по ссылке? Непонятно

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

Сообщение от Raia

Как тогда переписать этот код под реалии Питона?

Что-нибудь вроде

Python
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
class node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.color = 'red'
 
class rb:
    def __init__(self):
        self.root = node(None)
        self.count = 0
        
 
    def insert(self, x):
        def add(n, x):
            if n.val is None:
                n.val = x
                n.left = node(None)
                n.right = node(None)
            elif (x > n.val):
                add(n.right, x)
            else:
                add(n.left, x)
        add(self.root, x)
 
    def find(self, x):
        def lookup(n, x):
            if n is None:
                return False
            else:
                if n.val == x:
                    return True
                return lookup(x > n.val and n.right or n.left, x)
        return lookup(self.root, x)

Хочется конечно ADT, но увы.

@alex925 · 29.04.2016, 20:37

Сообщение от smlprog

Если вам говорили, что питон простой и прозрачный язык, то знайте, вас обманули.

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

Полная версия, есть тут
https://ru.wikipedia.org/wiki/... 0.B8.D1.8F

@Raia · 29.04.2016, 23:02 **[ТС]**

smlprog, спасибо за ответ. Только поясните, пожалуйста, в чем разница заключается..

@smlprog · 29.04.2016, 23:17

Сообщение от alex925

Если, что так, то одно из основных правил питона, это: "Простое лучше сложного, явного лучше не явного".

Ты ещё и наверное продавцам Гербалайфа веришь?

Добавлено через 7 минут

Сообщение от Raia

в чем разница заключается

В том, что внутрь add мы теперь всегда передаём объект типа node (с val = None, когда узел в оригинале был None), когда как до этого туда передавался None. node - уже объект с интересующими нас полями, и мы можем с ними работать и ходить по ним в lookup'е. В нормальных языках просто делается ADT типа (val*left*right | null) и проходятся паттерн-матчингом по нему, но тут другая атмосфера.

@Raia · 29.04.2016, 23:26 **[ТС]**

Сообщение от smlprog

В том, что внутрь add мы теперь всегда передаём объект типа node (с val = None, когда узел в оригинале был None), когда как до этого туда передавался None. node - уже объект с интересующими нас полями, и мы можем с ними работать и ходить по ним в lookup'е. В нормальных языках просто делается ADT типа (val*left*right | null) и проходятся паттерн-матчингом по нему, но тут другая атмосфера.

Странно, конечно, такое воспринимать, как-то в c# жить несколько проще

Еще раз спасибо.

Новые блоги и статьи Все статьи Все блоги /
Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .

@Raia 1 / 1 / 1 Регистрация: 16.04.2015 Сообщений: 14
	29.04.2016, 18:31 [ТС]
	Я примерно об этом и писал в шапке топика.. Разве параметры не передаются по ссылке? Непонятно Как тогда переписать этот код под реалии Питона? 0

@Raia 1 / 1 / 1 Регистрация: 16.04.2015 Сообщений: 14
	29.04.2016, 23:02 [ТС]
	smlprog, спасибо за ответ. Только поясните, пожалуйста, в чем разница заключается.. 0

Рекурсивное дерево поиска

Решение