Уведомления

Группа в Telegram: @pythonsu

#1 Авг. 15, 2011 18:37:06

Carzil
От:
Зарегистрирован: 2010-05-26
Сообщения: 106
Репутация: +  0  -
Профиль   Отправить e-mail  

Binary Search Tree

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

#!/usr/bin/python
#(c) Andreev Alexander (aka Carzil) 2011
n = int(input())
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 inorder_(self, node):
        if node != None:
            self.inorder_(node.left)
            print(node.key)
            self.inorder_(node.right)
            
    def inorder(self):
        self.inorder_(self.root)
            
t = Tree()
for i in range(n): 
    t.insert(int(input()))
t.inorder()
Но, при сдаче в тестирующую систему, пишет, что неправильный ответ на 37 тестах из 60. В чём может быть проблема?



Офлайн

#2 Авг. 16, 2011 09:15:00

Isem
От:
Зарегистрирован: 2010-08-27
Сообщения: 447
Репутация: +  7  -
Профиль   Отправить e-mail  

Binary Search Tree

Почему у вас при добавлении узла в дерево добавляется сразу несколько узлов?



Офлайн

#3 Авг. 17, 2011 01:03:44

Carzil
От:
Зарегистрирован: 2010-05-26
Сообщения: 106
Репутация: +  0  -
Профиль   Отправить e-mail  

Binary Search Tree

Я доработал немного код:

#!/usr/bin/python
#(c) 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()
Isem, всмысле?



Офлайн

#4 Авг. 17, 2011 05:36:22

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 9848
Репутация: +  853  -
Профиль   Отправить e-mail  

Binary Search Tree

        if self.root == None:
            self.root = Node(val, None, None)
        current = self.root
должен быть сразу выход



Отредактировано (Авг. 17, 2011 05:36:57)

Офлайн

#5 Авг. 17, 2011 09:14:19

Carzil
От:
Зарегистрирован: 2010-05-26
Сообщения: 106
Репутация: +  0  -
Профиль   Отправить e-mail  

Binary Search Tree

#!/usr/bin/python
#(c) 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()
Та же проблема.



Офлайн

#6 Авг. 17, 2011 09:28:21

Enchantner
От:
Зарегистрирован: 2009-02-11
Сообщения: 442
Репутация: +  0  -
Профиль   Отправить e-mail  

Binary Search Tree

Carzil
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2008/lecture-notes/

Раздел по BST, рекомендую :)



Офлайн

#7 Авг. 18, 2011 01:56:45

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 9848
Репутация: +  853  -
Профиль   Отправить e-mail  

Binary Search Tree

class Node:
    def __init__(self, key, left, right):
        self.key = key
        self.left = left
        self.right = right
        print('.')
    def set_value(self, val):
        self.key = val
    
class Tree:
    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:
            #print(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()
[guest@localhost tests]$ python3 t.py
3 4 5 6 7 8 3 4 2 12 3 4 5 6 7 8 3 4 2 11 3 4 5 6 7 8 3 4 2 13
.
.
.
.
.
.
.
.
.
.
2 3 4 5 6 7 8 11 12 13 [guest@localhost tests]$
существенных изменений не вносил

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



Офлайн

#8 Авг. 18, 2011 23:07:27

Carzil
От:
Зарегистрирован: 2010-05-26
Сообщения: 106
Репутация: +  0  -
Профиль   Отправить e-mail  

Binary Search Tree

Тот тест, который Вы привели, выполняется абсолютно верно. Если элемент в дереве уже есть, то его добавлять не надо.



Отредактировано (Авг. 18, 2011 23:42:21)

Офлайн

#9 Авг. 19, 2011 03:02:11

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 9848
Репутация: +  853  -
Профиль   Отправить e-mail  

Binary Search Tree

при сортировке бинарным деревом дубликаты из массива не должны удаляться
из-за этого тестирующая система может писать, что получен неправильный массив



Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version