BST, что и как?

Question

[Carzil]

Добрый день! Есть задача: отсортировать N элементов, при помощи бинарного дерева поиска. Если элемент уже есть в дереве, то его добавлять не надо. Я делаю так:

#!/usr/bin/python
#© Andreev Alexander (aka Carzil) 2011
class Node(object):
    def __init__(self, key, left, right):
        self.key = key
        self.left = left
        self.right = right
        
        
    def set_value(self, val):
        self.key = val
    
class Tree(object):
    def __init__(self):
        self.root = None
        
    def add_key(self, node, val):
        if node == None:
            return Node(val, None, None)
        elif val < node.key:
            return Node(node.key, self.add_key(node.left, val), node.right)
        elif val > node.key:
            return Node(node.key, node.left, self.add_key(node.right, val))
        else:
            return Node(node.key, node.left, node.right)
                            
                
    def insert(self, val):
        self.root = self.add_key(self.root, val)
        
    def traverse(self, node):
        global cnt
        if node == None:
            return
        else:
            cnt += 1
            self.traverse(node.left)
            self.traverse(node.right)
            
    def inorder_(self, node):
        if node != None:
            self.inorder_(node.left)
            print(node.key, end=" ")
            self.inorder_(node.right)
            
    def inorder(self):
        self.inorder_(self.root)
            
t = Tree()
for i in input().split():
    if i == "0":
        break 
    t.insert(int(i))
t.inorder()

Но, при сдаче в тестирующую систему, пишет, что неправильный ответ на 37 тестах из 60. В чём может быть проблема?

Answer 1

[Vas3K]

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

Comments

[Carzil]

Ввод-вывод стандартный
Ограничение по времени: 1 секунда
Ограничение по памяти: 64 мегабайта
На вход поступает не более 10 ^ 5 чисел (не считая заключительного нуля)

[Carzil]

Извиняюсь, я не тот исходник сначала выложил. Вот правильный. Но проблема та же.

Answer 2

[ntkt]

Уперлись в рекурсию. Первый код падал на 1100 элементах. Этот не работает в таком виде.

Comments

[Carzil]

#!/usr/bin/python
#© Andreev Alexander (aka Carzil) 2011
class Node(object):
    def __init__(self, key, left, right):
        self.key = key
        self.left = left
        self.right = right
        
        
    def set_value(self, val):
        self.key = val
    
class Tree(object):
    def __init__(self):
        self.root = None
        
    def add_key(self, val):
        if self.root == None:
            self.root = Node(val, None, None)
        current = self.root
        while current:
            if val < current.key:
                if current.left == None:
                    current.left = Node(val, None, None)
                    break
                current = current.left
            elif val > current.key:
                if current.right == None:
                    current.right = Node(val, None, None)
                    break
                current = current.right
            else:
                break
                    
                            
                
    def insert(self, val):
        self.add_key(val)
        
    def inorder_(self):
        if self.root == None:
            return None
        stack = []
        node = self.root
        while node or stack:
            if node != None:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                print(node.key, end=" ")
                node = node.right
            
    def inorder(self):
        self.inorder_()
            
t = Tree()
for i in input().split():
    if i == "0":
        break 
    t.insert(int(i))
t.inorder()

Переписал без использования рекурсии. Та же проблема.

Answer 3

[ntkt]

А в задании точно было сказано удалять дубликаты при сортировке? :)

[04:26]ntkt@nb:~/temp$ ./bst.py
'1 3 3 2 5 4 5'
1
2
3
4
5


И, как правило хорошего тона, лучше заворачивать код, который находится на верхнем уровне и не входит в классы, в условие вида:
...
class ...
...
if __name__=='main':
...

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

Comments

[ntkt]

Очепятка, пардон муар:
if __name__=='__main__':

[Carzil]

Да, нужно удалять дубликаты. Ок.

[Carzil]

#!/usr/bin/python
#© Andreev Alexander (aka Carzil) 2011
class Node(object):
    def __init__(self, key, left, right):
        self.key = key
        self.left = left
        self.right = right
        
        
    def set_value(self, val):
        self.key = val
    
class Tree(object):
    def __init__(self):
        self.root = None
        
    def add_key(self, val):
        if self.root == None:
            self.root = Node(val, None, None)
            return
        current = self.root
        while current:
            if val < current.key:
                if current.left == None:
                    current.left = Node(val, None, None)
                    break
                current = current.left
            elif val > current.key:
                if current.right == None:
                    current.right = Node(val, None, None)
                    break
                current = current.right
            else:
                break
                    
                            
                
    def insert(self, val):
        self.add_key(val)
        
    def inorder_(self):
        if self.root == None:
            return None
        stack = []
        node = self.root
        while node or stack:
            if node != None:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                print(node.key, end=" ")
                node = node.right
            
    def inorder(self):
        self.inorder_()
           
if __name__ == "__main__": 
    t = Tree()
    for i in input().split():
        if i == "0":
            break 
        t.insert(int(i))
    t.inorder()