CODEWITHSUNDEEP
pythonpython-3.xalgorithmbinary-search-tree
daniel
daniel

Reputation: 67

Bi-Directional Binary Search Trees?

I have tried to implement a BST. As of now it only adds keys according to the BST property(Left-Lower, Right-Bigger). Though I implemented it in a different way.

This is how I think BST's are supposed to be

Single Direction BST

How I have implemented my BST

Bi-Directional BST

The question is whether or not is it the correct implementation of BST? (The way i see it in double sided BST's it would be easier to search, delete and insert) 

import pdb; 
class Node:
    def __init__(self, value):
        self.value=value
        self.parent=None
        self.left_child=None
        self.right_child=None

class BST:

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

    def add(self,value):
        #pdb.set_trace()
        new_node=Node(value)
        self.tp=self.root                                                   
        if self.root is not None:                                         
                while True:
                    if self.tp.parent is None:
                        break
                    else:
                        self.tp=self.tp.parent
                                                                            #the self.tp varible always is at the first node.
                while True:
                    if new_node.value >= self.tp.value :

                        if self.tp.right_child is None:
                            new_node.parent=self.tp
                            self.tp.right_child=new_node
                            break
                        elif self.tp.right_child is not None:
                            self.tp=self.tp.right_child
                            print("Going Down Right")
                            print(new_node.value)
                    elif new_node.value < self.tp.value :
                        if self.tp.left_child is None:
                            new_node.parent=self.tp
                            self.tp.left_child=new_node
                            break
                        elif self.tp.left_child is not None:
                            self.tp=self.tp.left_child
                            print("Going Down Left")
                            print(new_node.value)
        self.root=new_node



newBST=BST()
newBST.add(9)
newBST.add(10)
newBST.add(2)
newBST.add(15)
newBST.add(14)
newBST.add(1)
newBST.add(3)

Edit: I have used while loops instead of recursion. Could someone please elaborate as why using while loops instead of recursion is a bad idea in this particular case and in general?

Upvotes: 0

Views: 1752

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59154

BSTs with parent links are used occasionally.

The benefit is not that the links make it easier to search or update (they don't really), but that you can insert before or after any given node, or traverse forward or backward from that node, without having to search from the root.

It becomes convenient to use a pointer to a node to represent a position in the tree, instead of a full path, even when the tree contains duplicates, and that position remains valid as updates or deletions are performed elsewhere.

In an abstract data type, these properties make it easy, for example, to provide iterators that aren't invalidated by mutations.

Upvotes: 1

Prune
Prune

Reputation: 77837

You haven't described how you gain anything with the parent pointer. An algorithm that cares about rewinding to the parent node, will do so by crawling back up the call stack.

I've been there -- in my data structures class, I implemented my stuff with bi-directional pointers. When we got to binary trees, those pointers ceased to be useful. Proper use of recursion replaces the need to follow a link back up the tree.

Upvotes: 0

Related Questions