1
\$\begingroup\$

I am reading about algorithms and got to the binary search trees. I wanted to ask if the following implementation of a Binary Tree is correct.

import random

class Tree(object):

    def __init__(self):

        self.root = Node()

    def insert(self,data):

        self.root.insert(data)

    def delete(self,data):

        self.root.delete(data)

    def print_elements(self):

        return self.root.print_element()

class Node(object):

    def __init__(self,data = None, parent = None):

        self.parent = parent
        self.data = data
        self.left = None
        self.right = None

    def insert(self,data):

        if self.data == None:

            self.data = data
        else:
            if data < self.data:
                if self.left == None:
                    self.left = Node(data,self)
                else:
                    self.left.insert(data)
            else:
                if data > self.data:
                    if self.right == None:
                        self.right = Node(data,self)
                    else:
                        self.right.insert(data)

    def delete(self,data):

        if self.data == data:

            if self.right == None and self.left == None:        

                if self.parent.left.data == data:

                    self.parent.left = None
                else:

                    self.parent.right = None
            elif self.right == None or self.left == None:

                if self.right == None:

                    self.data , self.left = self.left.data , self.left.left

                else:

                    self.data, self.right = self.right.data , self.right.right

            else:

                counter = self.right
                while True:
                    if counter.right == None:
                        break
                    else:
                        counter = counter.left
                self.data = counter.data
                counter.delete(counter.data)

        else:
            if data < self.data:
                self.left.delete(data)
            else:
                self.right.delete(data)


    def search(self,data):

        if self.data == data:
            return self.data
        else:
            if data < self.data:
                return self.left.search(data)
            else:
                return self.right.search(data)

    def print_element(self):

        if self.parent:

            print self.data, 'is below %s' % (self.parent.data)
        else:
            print self.data

        if self.right != None:
            self.right.print_element()
        if self.left != None:
            self.left.print_element()

The other thing I want to ask is, when I am implementing these data structures (also happened with linked lists) I find it easier to implement the methods in the Node class and not in the BT/LL class. Is this normal with Python ? I mean, I see the guides with C++ and the methods are mostly implemented in the BT/LL classes , but they use pointers and pointers are not available in Python. Am I doing it wrong ?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Is it on purpose that your implementation can not hold more than one identical value? I mean, t = Tree(); t.insert(1); t.insert(1) result in t containing only one node. Why? \$\endgroup\$ Commented Dec 3, 2016 at 11:43
  • \$\begingroup\$ Yep, I am not sure how I should handle the same value more than once and this is why I did not include it in the implementation \$\endgroup\$ Commented Dec 3, 2016 at 12:28
  • 1
    \$\begingroup\$ (I wanted to ask … not holding my breath 'til you do…) Tag python-2x. \$\endgroup\$
    – greybeard
    Commented Nov 4, 2021 at 9:13

1 Answer 1

1
\$\begingroup\$

[is below] implementation of a Binary Tree [correct?]
Without a specification of how a Binary (Search) Tree is to behave, that is difficult to tell, Asian style.
Try

if __name__ == '__main__':
    t = Tree()
    t.insert(0)
    t.delete(1)
    t.delete(0)

: While it may be possible to hand-wave failure to delete something not in the tree,
not being able to delete what's in a single-item tree is not correct.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.