Python BST + AVL

Tree.py

?

1 2 3 4

class Tree:       def __init__(self):         self.Root = None

Node.py

?

1 2 3 4 5 6

class Node:       def __init__(self,key):         self.key = key         self.rightChild = self.leftChild = None

BST.py

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

# -*- coding : ms949 -*- import Tree,Node import sys   class BST:       def search(self,tree,s_key):         if (tree == None): return None,None         parent, curr = None,tree.Root         while(curr!=None):             if(curr.key == s_key): break             parent = curr             if(curr.key > s_key): curr = curr.leftChild             else: curr = curr.rightChild         return parent,curr       def inorder(self,node):         if(node==None):             return         self.inorder(node.leftChild)         sys.stdout.write(str(node.key))         sys.stdout.write("("+str(self.depth(node))+")"+" ")         self.inorder(node.rightChild)       def depth(self,node):         if(node==None): return 0;         elif(node.rightChild!=None and node.leftChild != None):             return 1+max(self.depth(node.rightChild),self.depth(node.leftChild))         elif(node.leftChild==None): return 1+self.depth(node.rightChild)         elif(node.rightChild==None): return 1+self.depth(node.leftChild)         else: return 1       def insert(self,tree,new_key):         q, p = self.search(tree, new_key)         if(p != None):             print("Duplicate key error")             return False         newNode = Node.Node(new_key)         if(tree.Root==None): tree.Root = newNode         elif (new_key < q.key): q.leftChild=newNode         else: q.rightChild = newNode         return True       def delete(self,tree, d_key):         q, p = self.search(tree, d_key)         if(p==None):             print("There are no key to delete.")             return False         if(p.leftChild==None and p.rightChild==None):             if(q == None):                 tree.Root = None                 return True             if(q.leftChild == p): q.leftChild = None             else: q.rightChild = None         elif(p.leftChild!=None and p.rightChild!=None):             if(self.depth(p.leftChild) > self.depth(p.rightChild)):                 # Depth of leftSubTree is larger than Right                 exchangeNode = p.leftChild                 while(exchangeNode.rightChild!=None):                     exchangeNode = exchangeNode.rightChild             else:                 # Depth of rightSubTree is larger than Left                 exchangeNode = p.rightChild                 while(exchangeNode.leftChild!=None):                     exchangeNode = exchangeNode.leftChild               self.delete(tree, exchangeNode.key)             p.key,exchangeNode.key = exchangeNode.key,p.key             elif(p.leftChild!=None):             if(q.leftChild == p): q.leftChild = p.leftChild             else: q.rightChild = p.leftChild         else:             if(q.leftChild == p): q.leftChild = p.rightChild             else: q.rightChild = p.rightChild         return True

AVL.py

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

# -*- coding: ms949 -*- import BST import sys   class AVL(BST.BST):     def __init__(self):         self.bf_stack=[]         self.node_stack=[]       def BFof(self,node):         return self.depth(node.leftChild)-self.depth(node.rightChild)       def insert(self,tree,key):         if super(AVL,self).insert(tree,key) == False: return False         if self.isAVL(tree,key) :             del self.bf_stack[:]             del self.node_stack[:]         else: self.makeAVL(tree,key)         return True       def delete(self,tree,key):         if super(AVL,self).delete(tree, key)==False: return False         if self.isAVL(tree,key) :             del self.bf_stack[:]             del self.node_stack[:]         else: self.makeAVL(tree,key)         return True       def isAVL(self,tree,key):         parent,gabage = self.search(tree, key)         if parent == None: return True         if len(self.bf_stack)==3:             self.bf_stack.remove(self.bf_stack[0])             self.node_stack.remove(self.node_stack[0])         bf=self.BFof(parent)         self.bf_stack.append(bf)         self.node_stack.append(parent)         if(abs(bf)>1):             return False         return self.isAVL(tree,parent.key)       def makeAVL(self,tree,key):         if(len(self.bf_stack)==2):             gabage,C = self.search(tree,key)             self.node_stack.insert(0,C)             self.bf_stack.insert(0,self.BFof(C))           if len(self.bf_stack) == 3:               if self.bf_stack[1] < 0 and self.bf_stack[2] > 0:                 print("insert",str(key),"=> LR")                 self.RL_LR(tree,self.node_stack[1],self.node_stack[2])               elif self.bf_stack[1] > 0 and self.bf_stack[2] < 0:                 print("insert",str(key),"=> RL")                 self.RL_LR(tree,self.node_stack[2],self.node_stack[1])               elif self.bf_stack[1] * self.bf_stack[2] > 0:                 sys.stdout.write("insert "+str(key))                 self.node_stack.remove(self.node_stack[0])                 self.LL_RR(tree)         del self.bf_stack[:]         del self.node_stack[:]         def LL_RR(self,tree):         A,B=self.node_stack[1],self.node_stack[0]         parent,gabage = self.search(tree,A.key)         if parent == None: tree.Root =B         elif parent.leftChild == A: parent.leftChild = B         else: parent.rightChild = B           if self.bf_stack[1] > 0 and self.bf_stack[2] > 0:             A.leftChild,B.rightChild = B.rightChild, A             print(" => LL")         elif self.bf_stack[1] < 0 and self.bf_stack[2] < 0:             A.rightChild,B.leftChild = B.leftChild, A             print(" => RR")       def RL_LR(self,tree,left,right):         parent,gabage = self.search(tree,self.node_stack[2].key)         C = self.node_stack[0]         if parent == None: tree.Root = C         elif parent.leftChild == self.node_stack[2]: parent.leftChild = C         else: parent.rightChild =C         C.leftChild,C.rightChild,left.rightChild,right.leftChild               = left,right ,C.leftChild,C.rightChild