Python에서 이진 검색 트리 작성 - 예제 포함

44013 단어 languagescomputersciencepythonmailinglist


게시물Writing a Binary Search Tree in Python – With Examples은 Qvault에 처음 등장했습니다.

이진 검색 트리 또는 줄여서 BST는 각 노드가 모든 왼쪽 자식 노드보다 크고 모든 오른쪽 자식 노드보다 작은 키를 저장하는 트리입니다. 이진 트리는 조직적인 방식으로 데이터를 저장하는 데 유용하므로 데이터를 빠르게 가져오고, 삽입하고, 업데이트하고, 삭제할 수 있습니다. 노드의 보다 큼 및 보다 작음 순서는 각 비교가 나머지 트리의 약 절반을 건너뛰므로 전체 조회에 트리의 노드 수에 비례하는 시간이 걸린다는 것을 의미합니다.

정확하게 말하면 이진 검색 트리는 검색, 삽입, 업데이트 및 삭제 작업에 대해 평균 Big-O 복잡성O(log(n))을 제공합니다. Log(n)은 정렬되지 않은 배열에서 항목을 찾는 데 필요한 선형O(n) 시간보다 훨씬 빠릅니다. PostgreSQL 및 MySQL과 같은 널리 사용되는 많은 프로덕션 데이터베이스는 내부에서 이진 트리를 사용하여 CRUD 작업 속도를 높입니다.

BST

1단계 – BSTNode 클래스



우리의 구현은 Tree 클래스를 사용하지 않고 대신 Node 클래스만 사용합니다. 이진 트리는 실제로 각 하위 노드에 연결되는 루트 노드에 대한 포인터일 뿐이므로 해당 아이디어로 실행할 것입니다.

먼저 생성자를 만듭니다.

class BSTNode:
    def  __init__ (self, val=None):
        self.left = None
        self.right = None
        self.val = val


값(키)을 제공하도록 허용하지만 제공되지 않으면 그냥 None 로 설정합니다. 또한 새 노드의 두 자식을 None 로 초기화합니다.

2단계 – 삽입



새 데이터를 삽입할 방법이 필요합니다. 삽입 방법은 다음과 같습니다.

def insert(self, val):
        if not self.val:
            self.val = val
            return

        if self.val == val:
            return

        if val < self.val:
            if self.left:
                self.left.insert(val)
                return
            self.left = BSTNode(val)
            return

        if self.right:
            self.right.insert(val)
            return
        self.right = BSTNode(val)


노드에 아직 값이 없으면 주어진 값을 설정하고 반환할 수 있습니다. 또한 존재하는 값을 삽입하려고 하면 noop 로 간주될 수 있으므로 간단히 반환할 수도 있습니다. 주어진 값이 노드의 값보다 작고 이미 왼쪽 자식이 있는 경우 왼쪽 자식에서 재귀적으로 insert를 호출합니다. 아직 왼쪽 자식이 없으면 주어진 값을 새로운 왼쪽 자식으로 만듭니다. 우리는 오른쪽에 대해서도 똑같이 할 수 있습니다.

3단계 – 최소값 가져오기 및 최대값 가져오기




def get_min(self):
        current = self
        while current.left is not None:
            current = current.left
        return current.val

def get_max(self):
        current = self
        while current.right is not None:
            current = current.right
        return current.val

getMin 및 getMax는 유용한 도우미 함수이며 작성하기 쉽습니다! 트리의 가장자리를 순회하여 트리에 저장된 가장 작은 값 또는 가장 큰 값을 찾는 간단한 재귀 함수입니다.

4단계 – 삭제




def delete(self, val):
        if self == None:
            return self
        if val < self.val:
            self.left = self.left.delete(val)
            return self
        if val > self.val:
            self.right = self.right.delete(val)
            return self
        if self.right == None:
            return self.left
        if self.left == None:
            return self.right
        min_larger_node = self.right
        while min_larger_node.left:
            min_larger_node = min_larger_node.left
        self.val = min_larger_node.val
        self.right = self.right.delete(min_larger_node.val)
        return selfdef delete(self, val):
        if self == None:
            return self
        if val < self.val:
            if self.left:
                self.left = self.left.delete(val)
            return self
        if val > self.val:
            if self.right:
                self.right = self.right.delete(val)
            return self
        if self.right == None:
            return self.left
        if self.left == None:
            return self.right
        min_larger_node = self.right
        while min_larger_node.left:
            min_larger_node = min_larger_node.left
        self.val = min_larger_node.val
        self.right = self.right.delete(min_larger_node.val)
        return selfdef delete(self, val):
        if self == None:
            return self
        if val < self.val:
            self.left = self.left.delete(val)
            return self
        if val > self.val:
            self.right = self.right.delete(val)
            return self
        if self.right == None:
            return self.left
        if self.left == None:
            return self.right
        min_larger_node = self.right
        while min_larger_node.left:
            min_larger_node = min_larger_node.left
        self.val = min_larger_node.val
        self.right = self.right.delete(min_larger_node.val)
        return self


삭제 작업은 더 복잡한 작업 중 하나입니다. 재귀 함수이기도 하지만 삭제 작업을 수행한 후 주어진 노드의 새로운 상태를 반환하기도 합니다. 이렇게 하면 자식이 삭제된 부모가 left 또는 right 데이터 멤버를 None 로 적절하게 설정할 수 있습니다.

5단계 – 존재



exists 함수는 주어진 값이 트리에 이미 존재하는지 여부에 따라 True 또는 False를 반환하는 또 다른 간단한 재귀 함수입니다.

def exists(self, val):
        if val == self.val:
            return True

        if val < self.val:
            if self.left == None:
                return False
            return self.left.exists(val)

        if self.right == None:
            return False
        return self.right.exists(val)


6단계 - 순서대로



트리를 읽을 수 있는 형식으로 인쇄할 수 있으면 유용합니다. inorder 메서드는 키 순서대로 트리의 값을 인쇄합니다.

def inorder(self, vals):
        if self.left is not None:
            self.left.inorder(vals)
        if self.val is not None:
            vals.append(self.val)
        if self.right is not None:
            self.right.inorder(vals)
        return vals


7단계 – 선주문




def preorder(self, vals):
        if self.val is not None:
            vals.append(self.val)
        if self.left is not None:
            self.left.preorder(vals)
        if self.right is not None:
            self.right.preorder(vals)
        return vals


8단계 - 후주문




def postorder(self, vals):
        if self.left is not None:
            self.left.postorder(vals)
        if self.right is not None:
            self.right.postorder(vals)
        if self.val is not None:
            vals.append(self.val)
        return vals


용법




def main():
    nums = [12, 6, 18, 19, 21, 11, 3, 5, 4, 24, 18]
    bst = BSTNode()
    for num in nums:
        bst.insert(num)
    print("preorder:")
    print(bst.preorder([]))
    print("#")

    print("postorder:")
    print(bst.postorder([]))
    print("#")

    print("inorder:")
    print(bst.inorder([]))
    print("#")

    nums = [2, 6, 20]
    print("deleting " + str(nums))
    for num in nums:
        bst.delete(num)
    print("#")

    print("4 exists:")
    print(bst.exists(4))
    print("2 exists:")
    print(bst.exists(2))
    print("12 exists:")
    print(bst.exists(12))
    print("18 exists:")
    print(bst.exists(18))


Python의 전체 이진 검색 트리




class BSTNode:
    def  __init__ (self, val=None):
        self.left = None
        self.right = None
        self.val = val

    def insert(self, val):
        if not self.val:
            self.val = val
            return

        if self.val == val:
            return

        if val < self.val:
            if self.left:
                self.left.insert(val)
                return
            self.left = BSTNode(val)
            return

        if self.right:
            self.right.insert(val)
            return
        self.right = BSTNode(val)

    def get_min(self):
        current = self
        while current.left is not None:
            current = current.left
        return current.val

    def get_max(self):
        current = self
        while current.right is not None:
            current = current.right
        return current.val

    def delete(self, val):
        if self == None:
            return self
        if val < self.val:
            if self.left:
                self.left = self.left.delete(val)
            return self
        if val > self.val:
            if self.right:
                self.right = self.right.delete(val)
            return self
        if self.right == None:
            return self.left
        if self.left == None:
            return self.right
        min_larger_node = self.right
        while min_larger_node.left:
            min_larger_node = min_larger_node.left
        self.val = min_larger_node.val
        self.right = self.right.delete(min_larger_node.val)
        return self

    def exists(self, val):
        if val == self.val:
            return True

        if val < self.val:
            if self.left == None:
                return False
            return self.left.exists(val)

        if self.right == None:
            return False
        return self.right.exists(val)

    def preorder(self, vals):
        if self.val is not None:
            vals.append(self.val)
        if self.left is not None:
            self.left.preorder(vals)
        if self.right is not None:
            self.right.preorder(vals)
        return vals

    def inorder(self, vals):
        if self.left is not None:
            self.left.inorder(vals)
        if self.val is not None:
            vals.append(self.val)
        if self.right is not None:
            self.right.inorder(vals)
        return vals

    def postorder(self, vals):
        if self.left is not None:
            self.left.postorder(vals)
        if self.right is not None:
            self.right.postorder(vals)
        if self.val is not None:
            vals.append(self.val)
        return vals


읽어 주셔서 감사합니다!



테이크computer science courses on our new platform

질문이나 의견이 있으면 Twitter를 팔로우하고 연락하십시오.

Subscribe 더 많은 프로그래밍 기사를 보려면 뉴스레터로

관련 읽기


  • Building a Linked List in Python
    • 붙이는 클래스가 특정의 부모 클래스를 가지는 것을 알고 있는 trait내에서, 그 클래스의 입력 보완을 사용하고 싶다
    예제를 사용하여 Python에서 연결 목록 만들기

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage