DjangoBB LoFi version

Полная версия: Binary Search Tree

Начало » Центр помощи » Binary Search Tree

Carzil

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

Добрый день! Есть задача: отсортировать 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. В чём может быть проблема?

Isem

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

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

Carzil

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

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

#!/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, всмысле?

py.user.next

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

        if self.root == None:
            self.root = Node(val, None, None)
        current = self.root

должен быть сразу выход

Carzil

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

#!/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()

Та же проблема.

Enchantner

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

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

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

py.user.next

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

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. В чём может быть проблема?

в том, что удаляются дубликаты ?

Carzil

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

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

py.user.next

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

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