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.
Post Reply
User avatar
Phantom
Posts: 58
Joined: 6 years ago
Location: Cuba
Gender: None specified

Binary Search Tree

Post by Phantom » 6 years ago

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
------------return
--------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
--------else:
------------majMin = self.__left.__Major()
------------majMin.__RemoveNode()
------------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
padrinoIJ
Posts: 13
Joined: 6 years ago
Location: CUJAE
Gender: None specified

Re: Binary Search Tree

Post by padrinoIJ » 6 years ago

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;
typedef TREENODE* TREENODEPTR;

void insert(TREENODEPTR *treePtr, long dat){
     if(*treePtr==NULL){
        *treePtr = new TREENODE;
         if(*treePtr!=NULL){
             (*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);
} 

Post Reply

Return to “Algorithms”