[CS] 이진탐색트리(Binary Search Tree) 구현하기 python code

이진 탐색트리(Binary Search Tree) 구현하기

 

우리의 트리 클래스는 다음과 같은 기능을 제공해야 한다.

 

1. 새로운, 비어있는 이진 트리 맵을 생성한다. 이는 클래스의 인스턴스를 생성하는 것이다.
2. 키, 값 쌍의 데이터를 받아서 트리에 추가한다. put(key, value)의 형태로 메소드를 만들 것이다.
3. 키를 이용해서 해당 키에 연결된 값을 얻을 수 있다. get(key)를 구현할 것이다.
4. 특정 키를 주고, 해당 키를 트리 내에서 탐색한다. contains(key)의 메소드를 구현한다.
5. 특정 키를 주고, 해당 키를 트리 내에서 제거한다. delete(key) 의 메소드를 구현한다.

 

 

 

코드 

 

기본적인 노드 클래스 구현 

## 기본적인 노드 클래스 구현 
class TreeNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.parent = None
        self._leftChild = None
        self._rightChild = None
    
    @property
    def leftChild(self):
        return self._leftChild
    
    def rightChild(self):
        return self._rightChild

    @leftChild.setter
    def leftChild(self, value):
        # 현재 왼쪽 자식 노드가 있다면, 그 부모 속성을 제거한다.
        if self._leftChild:
            self._leftChild.parent = None
        #  새 노드가 None이 아니라면 새 노드의 부모를 자신으로 설정해준다. 
        if value : 
            value.parent = self
        self._leftChild = value 
    
    @rightChild.setter
    def rightChild(self, value):
        # 현재 오른쪽 자식 노드가 있다면, 그 부모 속성을 제거한다.
        if self._rightChild:
            self._rightChild.parent = None
        #  새 노드가 None이 아니라면 새 노드의 부모를 자신으로 설정해준다. 
        if value : 
            value.parent = self
        self._rightChild = value 
    
        
    ## 노드의 속성 확인용 메소드 구현 
    def isRoot(self):
        """
        자신이 루트인지 판단, 부모가 없으면 루트이다
        """
        return parent is None
    
    def isLeaf(self):
        """
        자신이 종단노드인지 확인 
        """
        return self._leftChiild is None and self.RightChild is None 
    
    def isLeftChild(self):
        """
        자신이 부모의 왼쪽 자식인지 확인, 부모가 있어야 하고 그 왼쪽 자식이 자신이어야 한다 
        """
        return self.parent and self.parent.leftChild is self 
    
    def isRightChild(self):
        """
        자신이 부모의 오른쪽 자식인지 확인, 부모가 있어야 하고 그 오른쪽 자식이 자신이어야 한다.
        """
        return self.parent and self.parent.rightChild is self 
    
    def hasLeftChild(self):
        """
        왼쪽자식을 가졌는지 확인
        """
        return self._leftChild is not None
    
    def hasRightChild(self):
        """
        오른쪽 자식을 가졌는지 확인 
        """
        return self._rightChild is not None
    
    def hasBothChildren(self):
        """
        두 자식을 가졌는지 확인 
        """
        return self._leftChild is not None and self._rightChild is not None
    
    def hasAnyChild(self):
        """
        어떤 자식이든 가졌는지 확인
        """
        return not self.isLeaf()

 

 

이진 트리 클래스 기초 구현 

,## 트리클래스 기초 구현 
class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.length = 0 
        
    # 노드 추가 
    def put(self, key, value):
        if self.root:
            self.__put(key, value, self.root)
        else : 
            self.root = TreeNode(key, value)
            
    def __put(self, key, value, currentNode):
        targetNode = currentNode
        while True:
            if key < targetNode.key:
                if not targetNode.hasLeftChild():
                    targetNode.leftChild = TreeNode(key, value)
                    break
                else:
                    targetNode = targetNode.leftChild 
            else : 
                if not targetNode.hasRightChild():
                    targetNode.rightChild = TreeNode(key, value)
                    break
                else:
                    targetNode = targetNode.rightChild 
        self.length +=1 
    
    # key를 통해 값을 받아오는 get 메소드 
    def get(self, key):
        if self.root is None:
            return None 
        res = self.__get(key,self.root)
        if res:
            return res.value
        return None 
    
    def __get(self, key, currentNode):
        targetNode = currentNode
        while True : 
            if key == targetNode.key:
                return targetNode
            elif key < targetNode.key:
                if targetNode.hasLeftChild():
                    targetNode = targetNode.leftChild
                else : 
                    return None
            else:
                if targetNode.hasRightChild():
                    targetNode = targetNode.rightChild
                else:
                    return None 

## key 삭제하기 

# 1. 먼저 삭제하고자 하는 노드의 키를 전달한다.
# 2. 주어진 키에 해당하는 노드를 찾는다. 
# 2-1. 만약 찾지 못했다면, 존재하지 않는 키를 삭제하려는 시도이다. 
# 예외를 던지거나 그냥 리턴할 수 있는데, 어떻게 처리할지는 구현자의 선택이다. 
# (여기서는 예외를 던지도록 한다.)
# 3. 찾은 노드를 제거한다.

# Case)) 
# 1. 길이가 1인 트리 내에서 루트 노드를 제거하는 경우
# 2. 종단 노드를 제거하는 경우
# 3. 좌/우 중 한쪽에만 자식 노드를 달고 있는 노드를 제거하는 경우
# 4. 양쪽에 자식 노드를 달고 있는 노드를 제거해야 하는 경우

    def delete(self, key):
        if self.length == 1 and self.root.key == key:
            self.root = None 
            self.length = 0 
        node_to_delete = self.get(key)
        if not node_to_delete:
            raise KeyError("tree에 node가 없습니다.")

#         종단 노드를 제거하는 경우
        if node_to_delete.isLeaf():
            ## 왼쪽 자식이었으면 부모의 왼쪽 자식 노드를 제거 
            if node_to_delete.isLeftChld():
                node_to_delete.parent.leftChild = None
            ## 오른쪽 자식이었으면 부모의 오른쪽 자식 노드를 제거 
            else :
                node_to_delete.parent.RightChild = None

#         자식을 가지는 노드를 제거하는 경우 
        elif node_to_delete.hasBothChildren():
        ## 양쪽 노드를 갖는 경우 처리 
            succ = self.findSuccessor()
            succ.sliceOut()
            self.key, self.value = succ.key, succ.value

        elif node_to_delete.leftChild:
        ## 한쪽 자식만 있는 경우이다.
        ## 자식과 제거될 노드의 연결을 끊는다.
        ## 그전에 자식 노드에 대한 참조를 별도로 유지한다.
            child = node_to_delete.leftChild \
                    if node_to_delete.leftChild is not None else \
                    node_to_delete.rightChild
            node_to_delete.leftChild = None
            node_to_delete.rightChild = None

            if node_to_delete.isRoot(): ## 만약 자기가 루트이면
                self.root = child
            elif node_to_delete.isLeftChild(): ## 이 이후부터는 부모가 존재하는 것이 보장된다.
                node_to_delete.parent.leftChild = child
            else:
                node_to_delete.parent.rightChild = child
        self.length -= 1
        
        def findSuccessor(self):
            succ = None
            if self.hasRightChild():
                succ = self.rightChild
                while succ.hasLeftChild():
                    succ = succ.leftChild       
            return succ
        
        def sliceOut(self):
  ## 현재 노드는 상속자이므로, 부모가 반드시 존재하고 왼쪽 자식은 없다.
            child = self.rightChild if self.hasRightChild() else None
            self.rightChild = None
            if self.isLeftChild():
                self.parent.leftChild = child
            else:
                self.parent.rightChild = child

 

 

 

 

출처 

soooprmx.com/archives/5165

이진탐색트리 (Binary Search Tree) 구현하기 - python · Wireframe