Binary Search Tree

[Phantom]

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)

[padrinoIJ]

This is my implementation of how to insert in an BST in C++(i solve the problem 1855 with these idea ), 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);
}