Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Best practise for creating BST : python

So I am implementing a Binary Search Tree but am confused as to whether I should have a Node class as well as a Bst class or just one class.

The reason why is because I know a BST is made up of nodes but at any point you can take a node and all the nodes beneath it and that essentially is a BST too.

If I have the following code where its one thing then I when inserting I can call my code like so self.left.insert(data)

class Bst():
def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None

def insert(self, data):
    node_to_insert = Bst(data)
    if data < self.data:
        if self.left is None:
            self.left = Bst(data)
        else:
            self.left.insert(data)
    else:
        if self.right is None:
            self.right = Bst(data)
        else:
            self.right.insert(data)

If I do it the other way where they are two seperate things a Node and a BST then in my insert method I have self.insert(data, node.left):

class Node():
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class Bst():
    def __init__(self, root=None):
        self.root = root

    def insert(self, data, node):
        node_to_insert = Node(data)

        if node is None:
            node = node_to_insert
        else:
            if data < node.data:
                if node.left is None:
                    node.left = node_to_insert
                else:
                    self.insert(data, node.left)
            else:
                if node.right is None:
                    node.right = node_to_insert
                else:
                    self.insert(data, node.right)

So my question is which is better code self.insert(data, node.left) or self.left.insert(data).

I would assume self.left.insert(data) as when the user is inserting they just have to write bst.insert(5) where as with the other one they say bst.insert(bst.root, 5)

like image 969
user3115352 Avatar asked Nov 10 '22 16:11

user3115352


1 Answers

The second is better I think. Algorithm separate with data structure, which brings more flexibility. For example the delete operation, which involves parent nodes, is easier to implement in the second than the first.

like image 131
qiangwang Avatar answered Nov 14 '22 22:11

qiangwang