Python BST + AVL

Tree.py

class Tree:

    def __init__(self):
        self.Root = None
 

Node.py

class Node:

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

BST.py

# -*- 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

# -*- 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