Python Binary Tree

johnque·2020년 2월 13일
0

Binary Tree

이진트리는 다음과 같은 조건을 지님

  • 왼쪽 자식 노드에는 부모 노드보다 작은 값을 가진 노드가 옴
  • 오른쪽 자식 노드에는 부모 노드보다 큰 값을 가진 노드가 옴
  • 루트 노드부터 리프 노드까지 모두에게 적용됨
  • 단 리프 노드는 왼쪽, 오른쪽 자식이 NULL

Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

먼저 Node에 대한 클래스를 만들어 줌

class BinaryTree:
    def __init__(self, root):
        self.root = root
    def insert(self, data):
        self.curr_node = self.root
        while True:
            if self.curr_node.data < data:
                if self.curr_node.right != None:
                    self.curr_node = self.curr_node.right
                else:
                    self.curr_node.right = Node(data)
                    break
            else:
                if self.curr_node.left != None:
                    self.curr_node = self.curr_node.left
                else:
                    self.curr_node.left = Node(data)
                    break

그 다음 비어있는 트리를 포함해서, 삽입하는 메소드까지 넣어줌
이어서, 탐색 -> 삭제 순으로 작성하는데, 이후에는 코드가 길어지므로 들여쓰기를 좀 하겠음
실제론 BinaryTree클래스 안에 들어있으므로 그 점 유의

def search(self, data):
    self.curr_node = self.root
    while self.curr_node:
        if self.curr_node.data == data:
            print(data)
            return True
        elif self.curr_node.data > data:
            print(self.curr_node.data)
            self.curr_node = self.curr_node.left
        else:     
            print(self.curr_node.data)
            self.curr_node = self.curr_node.right        
    return False

찾고자 하는 값이 현재 노드의 값보다 크냐 작으냐의 비교를 지속적으로 해서, 작으면 왼쪽, 크면 오른쪽으로 재귀호출대신에 반복문을 사용 이렇게 하기 때문에 시간복잡도가 순차탐색보다 더 낮은 로그가 나오게 됨

다음은 제일 고난이도이자 머리가 아픈 delete
삭제를 하기 위해선 크게 세가지를 생각해야함

  • 리프노드에서 삭제인가?
  • 트리 한가운데서 삭제인가?
  • 해당 삭제되는 노드에게 오른쪽 자식이 있는가?
    def delete(self, data):
        self.curr_node = self.root
        self.parent = self.curr_node
        searched = False
        while self.curr_node: # 값을 찾기위한 여정
            if self.curr_node.data == data:
                searched = True
                break
            elif self.curr_node.data > data:
                self.parent = self.curr_node
                self.curr_node = self.curr_node.left
            else:
                self.parent = self.curr_node
                self.curr_node = self.curr_node.right
        if searched == False: # 만약 True가 아니면 값을 찾지 못했단 증거
            return False

        # 일단 여기까지 왔다는 건 값을 찾긴 찾았다는 의미
        # 그럼 이제 리프노드에서 삭제, 즉 자식 노드가 1개도 없는지
        # 트리 한가운데에서 삭제인데, 자식노드가 1개인지
        # 트리 한가운데에서 삭제인데, 자식노드가 2개인지를 구별해 코드를 짜야 함
        if self.curr_node.left == None and self.curr_node.right == None:
            if self.parent.data > data: # 지우고자 하는 리프노드가 부모노드 왼쪽?
                self.parent.left = None
            else: #아니면 오른쪽?
                self.parent.right = None
        elif self.curr_node.left != None and self.curr_node.right == None:
        #왼쪽에만 자식이 한 개 있는 경우
            if data < self.parent.data: #현재 노드 자식과 부모 비교
                self.parent.left = self.curr_node.left
            else: # 크면 부모의 오른쪽, 작으면 부모의 왼쪽에 배치
                self.parent.right = self.curr_node.left
        elif self.curr_node.left == None and self.curr_node.right != None:
            if data < self.parent.data:
                self.parent.left = self.curr_node.right
            else:
                self.parent.right = self.curr_node.left
        else: # 두 개의 자식이 있는 경우
        # 방법은 두 가지가 있는데, 하나만 써도 상관없기 때문에 1개만 씀
        # 1.오른쪽 자식 노드로 가서, 가장 값이 작은 노드가 나올때까지 반복문 실시
        # 2.삭제할 값의 노드를 지우면 까다로우므로, 그냥 작은 노드의 value 삽입
        # 3.그 노드가 오른쪽 자식이 있으면, 그 노드의 자리에 자식이 대신함
            change = self.curr_node
            self.parent = self.curr_node
            self.curr_node = self.curr_node.right
            while self.curr_node.left: # 1번 파트
                self.parent = self.curr_node
                self.curr_node = self.curr_node.left
            # 이렇게 하면 오른쪽 자식 중에 가장 작은 값이 self.curr_node
            change.data = self.curr_node.data # 2번 파트
            if self.curr_node.right != None: # 3번 파트
                self.parent.left = self.curr_node.right
            else:
                self.parent.left = None
        del self.curr_node
        return True  
profile
코딩의 고수가 되고 싶은 종한이

0개의 댓글