Binary Search Tree

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
User avatar
Posts: 58
Joined: Thu Nov 17, 2011 11:21 am
Location: Cuba
Gender: None specified

Binary Search Tree

Postby Phantom » Sun Jun 03, 2012 11:52 pm

Here is my implementation of a Binary Search Tree in Python. You can post your implementation in another language or… if you want… A AVL or Black Red Tree or... a B-Tree!! My Binary Search Tree is a normal BST…:

Code: Select all

class ABB(object):
----def __init__(self, value=None, __father=None):
--------self.__left = self.__right = None
--------self.__count, self.__father = 0, __father
--------if value is not None: self.__value, self.__count = value, 1

----def Insert(self, value):
--------if not self.__count:
------------self.__count += 1
------------self.__value = value
--------comp = cmp(value, self.__value)
--------if not comp: self.__count += 1
--------elif comp > 0:
------------if self.__right: self.__right.Insert(value)
------------else: self.__right = ABB(value, self)
--------elif self.__left: self.__left.Insert(value)
--------else: self.__left = ABB(value, self)

----def Search(self, value):
--------if not self.__count: return False
--------comp = cmp(value, self.__value)
--------if comp > 0: return self.__right.Search(value) if self.__right else False
--------if comp < 0: return self.__left.Search(value) if self.__left else False
--------return True

----def Remove(self, value):
--------if not self.__count: return
--------comp = cmp(value, self.__value)
--------if not comp:
------------self.__count -= 1
------------if not self.__count: self.__RemoveNode()
--------elif comp > 0: self.__right.Remove(value)
--------else: self.__left.Remove(value)

----def __RemoveNode(self):
--------cmpParent = cmp(self.__value, self.__father.__value) if self.__father else 0
--------if not self.__right:
------------if cmpParent > 0: self.__father.__right = self.__left
------------elif cmpParent: self.__father.__left = self.__left
------------elif self.__left: self.__CopyProp(self.__left)
--------elif not self.__left:
------------if cmpParent > 0: self.__father.__right = self.__right
------------elif cmpParent: self.__father.__left = self.__right
------------majMin = self.__left.__Major()
------------majMin.__father = self.__father
------------majMin.__left, majMin.__right = self.__left, self.__right
------------if cmpParent > 0: self.__father.__right = majMin
------------elif cmpParent: self.__father.__left = majMin
------------else: self.__CopyProp(majMin)

----def __CopyProp(self, other):
--------self.__left, self.__right = other.__left, other.__right
--------self.__count, self.__value = other.__count, other.__value

----def __Major(self): return self if not self.__right else self.__right.__Major()

----def IsLeaf(self): return not(self.__left or self.__right)

----def ToWidthOrder(self):
--------queue = [self]
--------while queue:
------------act = queue.pop(0)
------------count = act.__count
------------while count:
----------------yield act.__value
----------------count -= 1
------------if act.__left: queue.append(act.__left)
------------if act.__right: queue.append(act.__right)

----def AmongOrder(self):
--------if self.__left:
------------for i in self.__left.AmongOrder(): yield i
--------count = self.__count
--------while count:
------------yield self.__value
------------count -= 1
--------if self.__right:
------------for i in self.__right.AmongOrder(): yield i

----def PreOrder(self):
--------count = self.__count
--------while count:
------------yield self.__value
------------count -= 1
--------if self.__left:
------------for i in self.__left.PreOrder(): yield i
--------if self.__right:
------------for i in self.__right.PreOrder(): yield i

----def PosOrder(self):
--------if self.__left:
------------for i in self.__left.PreOrder(): yield i
--------if self.__right:
------------for i in self.__right.PreOrder(): yield i
--------count = self.__count
--------while count:
------------yield self.__value
------------count -= 1

----Value = property(lambda self: self.__value if self.__count else None)

User avatar
Posts: 13
Joined: Wed Mar 14, 2012 9:48 pm
Location: CUJAE
Gender: None specified

Re: Binary Search Tree

Postby padrinoIJ » Mon Jul 16, 2012 6:06 pm

This is my implementation of how to insert in an BST in C++(i solve the problem 1855 with these idea :lol: ), i wait his suggestions, padrino_IJ,

Code: Select all

struct TreeNode{
       TreeNode *rigthPtr;
       TreeNode *leftPtr;
       long num;

typedef TreeNode TREENODE;

void insert(TREENODEPTR *treePtr, long dat){
        *treePtr = new TREENODE;
             (*treePtr)->num = dat;
             (*treePtr)->leftPtr = NULL;
             (*treePtr)->rigthPtr = NULL;             
     else if(dat < (*treePtr)->num) insert(&((*treePtr)->leftPtr), dat);
     else if(dat > (*treePtr)->num) insert(&((*treePtr)->rigthPtr), dat);

Return to “Algorithms”

Who is online

Users browsing this forum: No registered users and 1 guest