[Binary Tree] 이진트리 (1) - 삽입, 삭제

Binary Tree

---

이진트리 무슨 코드든 차분히, 차근차근 한단계씩 밟고 지나가면 이해할 수 있다.

BinaryTree()를 하면,

head = Node(None) 다음과 같은 아이들이 생성된다.

 

1. add: val의 값을 비교해 left, right에 넣어주기

2. search: 있으면 True, 없으면 False

3. remove: 복잡복잡한듯

값이 head.val이면 자식 (left, right)를 조사하고 해당 조건에 따라 처리

아니면, head.val의 값과 비교하여 작으면 left, 크면 right로 가서 반복처리

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

class BinaryTree:
    def __init__(self):
        self.head = Node(None)

    def search(self, item):
        if self.head.val == None:
            return False
        else:
            return self._search(self.head, item)

    def __search(self, cur, item):
        if cur.val == item:
            return True
        else:
            if cur.val >= item:
                if cur.left != None:
                    return self._search(cur.left, item)
                else:
                    return False

            else:
                if cur.right != None:
                    return self._search(cur.right, item)
                else:
                    return False

    def add(self, item):
        if self.head.val == None:
            self.head.val = item
        else:
            self._add(self.head, item)

    def __add(self, cur, item):
        if cur.val >= item:
            if cur.left != None:
                self.__add(cur.left, item)
            else:
                cur.left = Node(item)
        else:
            if cur.right != None:
                self._add(cur.right, item)
            else:
                cur.right = Node(item)

    def remove(self, item):
        if self.head.val == None:
            print("No item in BST")
        if self.head.val == item:
            if self.head.left == None and self.head.right == None:
                self.head = None
            elif self.head.left == None and self.head.right != None:
                self.head = self.head.right
            elif self.head.left != None and self.head.right == None:
                self.head = self.head.left
            else:
                self.head.val = self.__most_left_from_right(self.head.right).val
                self.__removeItem(self.head, self.head.right, self.head.val)
        else:
            if self.head.val > item:
                self._remove(self.head, self.head.left, item)
            else:
                self._remove(self.head, self.head.right, item)

    def __remove(self, parent, cur, item):
        if cur == None:
            print("No item")
        if cur.val == item:
            if cur.left == None and cur.right == None:
                if parent.left == cur:
                    parent.left = None
                else:
                    parent.right = None
            elif cur.left == None and cur.right != None:
                if parent.left == cur:
                    parent.left = cur.right
                else:
                    parent.right = cur.right

            elif cur.left != None and cur.right == None:
                if parent.left == cur:
                    parent.left = cur.left
                else:
                    parent.right = cur.left
            else:
                cur.val = self.__most_left_from_right(cur.right).val
                self.__removeItem(cur, cur.right, cur.val)

    def __most_left_from_right(self, cur):
        if cur.left == None:
            return cur
        else:
            return self.__most_left_from_right(cur.left)

    def __removeItem(self, parent, cur, item):
        if cur.val == item:
            if parent.left == cur:
                parent.left =None
            else:
                parent.right = None
        else:
            if cur.val > item:
                self.__removeItem(cur, cur.left, item)
            else:
                self.__removeItem(cur, cur.right, item)