이진 트리 구현

이진 트리는 부모 노드가 left, right 자식 노드를 가지는 나무를 거꾸로 한 모양의 자료구조

* search, add, delete가 O(logn)의 성능으로 좋은 성능을 가진 자료구조이기 때문에 여러가지 프로그램을 만드는데 자주 쓰입니다.

* preorder_traverse 는 말 그대로 root 노드를 먼저 순회하기 때문에 preorder traverse이고, root노드 -> left 노드 -> right 노드 순으로 순회하고, 전송시에 이진 트리의 모형을 그대로 유지하기 때문에 전송시에 사용됩니다.

* inorder_traverse 도 마찬가지로 root 노드를 중간에 순회해서 inorder traverse입니다. left 노드 -> root 노드 -> right 노드 순으로 순회하고, 오름차순으로 정렬된 값이 나오게 됩니다.

* postorder_traverse 는 root 노드를 가장 나중에 순회하는 방법으로 left 노드 -> right 노드 -> root 노드 순으로 순회합니다.





구현 코드 및 테스트 코드

import unittest


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


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

# test purpose lists
self.preorder_list = []
self.inorder_list = []
self.postorder_list = []

def add(self, value):
if self.head.value is None:
self.head.value = value
else:
self._add(self.head, value)

def _add(self, cur, value):
if cur.value < value:
if cur.right is None:
cur.right = Node(value)
else:
self._add(cur.right, value)
else:
if cur.left is None:
cur.left = Node(value)
else:
self._add(cur.left, value)

def search(self, value):
if self.head.value is None:
return False
else:
return self._search(self.head, value)

def _search(self, cur, value):
if cur.value == value:
return True
else:
if cur.value < value:
if cur.right is None:
return False
else:
return self._search(cur.right, value)
else:
if cur.left is None:
return False
else:
return self._search(cur.left, value)

def remove(self, value):
if self.head.value is None:
return print("there is no value in this binary tree")
else:
if self.head.value == value:
if self.head.left is None and self.head.right is None:
self.head = Node(None)
elif self.head.left is None and self.head.right is not None:
self.head = self.head.right
elif self.head.left is not None and self.head.right is None:
self.head = self.head.left
else:
self.head.value = self._most_left_val_from_right_node(self.head.right).value
self._remove_item(self.head, self.head.right)
return True
else:
if self.head.value < value:
self._remove(self.head, self.head.right, value)
else:
self._remove(self.head, self.head.left, value)

def _remove(self, prev, cur, value):
if cur is None:
return print("not found value")

if cur.value < value:
self._remove(cur, cur.right, value)
elif cur.value > value:
self._remove(cur, cur.left, value)
else:
if cur.left is None and cur.right is None:
if prev.left.value == value:
prev.left = None
else:
prev.right = None
elif cur.left is None and cur.right is not None:
if prev.left.value == value:
prev.left = cur.right
else:
prev.right = cur.right
elif cur.left is not None and cur.right is None:
if prev.left.value == value:
prev.left = cur.left
else:
prev.right = cur.left
else:
cur.value = self._most_left_val_from_right_node(cur.right).value
self._remove_item(cur, cur.right)
return True

def _most_left_val_from_right_node(self, cur):
if cur.left is not None:
return self._most_left_val_from_right_node(cur.left)
else:
return cur

def _remove_item(self, prev, cur):
if cur.left is None:
prev.right = cur.right
else:
while cur.left is not None:
prev = cur
cur = cur.left
if cur.right is not None:
prev.left = cur.right
else:
prev.left = None

def preorder_traverse(self):
if self.head is not None:
self._preorder_traverse(self.head)

def _preorder_traverse(self, cur):
self.preorder_list.append(cur.value)
if cur.left is not None:
self._preorder_traverse(cur.left)
if cur.right is not None:
self._preorder_traverse(cur.right)

def inorder_traverse(self):
if self.head is not None:
self._inorder_traverse(self.head)

def _inorder_traverse(self, cur):
if cur.left is not None:
self._inorder_traverse(cur.left)

self.inorder_list.append(cur.value)

if cur.right is not None:
self._inorder_traverse(cur.right)

def postorder_traverse(self):
if self.head is not None:
self._postorder_traverse(self.head)

def _postorder_traverse(self, cur):
if cur.left is not None:
self._postorder_traverse(cur.left)
if cur.right is not None:
self._postorder_traverse(cur.right)
self.postorder_list.append(cur.value)


class BinaryTreeTest(unittest.TestCase):
def test(self):
bt = BinaryTree()
bt.add(6)
bt.add(3)
bt.add(4)
bt.add(1)
bt.add(7)
print("pre order")
bt.preorder_traverse()
self.assertEqual(bt.preorder_list, [6, 3, 1, 4, 7])

print("in order")
bt.inorder_traverse()
self.assertEqual(bt.inorder_list, [1, 3, 4, 6, 7])

print("post order")
bt.postorder_traverse()
self.assertEqual(bt.postorder_list, [1, 4, 3, 7, 6])

print("bt root remove")
bt_root_remove_test = BinaryTree()
bt_root_remove_test.add(60)
bt_root_remove_test.add(50)
bt_root_remove_test.add(70)
bt_root_remove_test.remove(60)
bt_root_remove_test.preorder_traverse()
self.assertEqual(bt_root_remove_test.preorder_list, [70, 50])

print("bt root remove2")
bt_root_remove_test = BinaryTree()
bt_root_remove_test.add(60)
bt_root_remove_test.add(50)
bt_root_remove_test.remove(60)
bt_root_remove_test.preorder_traverse()
self.assertEqual(bt_root_remove_test.preorder_list, [50])

print("bt root remove3")
bt_root_remove_test = BinaryTree()
bt_root_remove_test.add(60)
bt_root_remove_test.add(70)
bt_root_remove_test.remove(60)
bt_root_remove_test.preorder_traverse()
self.assertEqual(bt_root_remove_test.preorder_list, [70])

print("bt left remove 1")
bt_left_remove_test_1 = BinaryTree()
bt_left_remove_test_1.add(60)
bt_left_remove_test_1.add(50)
bt_left_remove_test_1.add(70)
bt_left_remove_test_1.remove(50)
bt_left_remove_test_1.preorder_traverse()
self.assertEqual(bt_left_remove_test_1.preorder_list, [60, 70])

print("bt left remove 2")
bt_left_remove_test_2_left = BinaryTree()
bt_left_remove_test_2_left.add(60)
bt_left_remove_test_2_left.add(50)
bt_left_remove_test_2_left.add(70)
bt_left_remove_test_2_left.add(40)
bt_left_remove_test_2_left.remove(50)
bt_left_remove_test_2_left.preorder_traverse()
self.assertEqual(bt_left_remove_test_2_left.preorder_list, [60, 40, 70])

print("bt right remove 2")
bt_left_remove_test_2_right = BinaryTree()
bt_left_remove_test_2_right.add(60)
bt_left_remove_test_2_right.add(50)
bt_left_remove_test_2_right.add(70)
bt_left_remove_test_2_right.add(55)
bt_left_remove_test_2_right.remove(50)
bt_left_remove_test_2_right.preorder_traverse()
self.assertEqual(bt_left_remove_test_2_right.preorder_list, [60, 55, 70])

print("bt right remove 1")
bt_right_remove_test_1 = BinaryTree()
bt_right_remove_test_1.add(60)
bt_right_remove_test_1.add(50)
bt_right_remove_test_1.add(70)
bt_right_remove_test_1.remove(70)
bt_right_remove_test_1.preorder_traverse()
self.assertEqual(bt_right_remove_test_1.preorder_list, [60, 50])

print("bt right remove 2")
bt_right_remove_test_2_left = BinaryTree()
bt_right_remove_test_2_left.add(60)
bt_right_remove_test_2_left.add(50)
bt_right_remove_test_2_left.add(70)
bt_right_remove_test_2_left.add(65)
bt_right_remove_test_2_left.remove(70)
bt_right_remove_test_2_left.preorder_traverse()
self.assertEqual(bt_right_remove_test_2_left.preorder_list, [60, 50, 65])

print("bt right remove 3")
bt_right_remove_test_1 = BinaryTree()
bt_right_remove_test_1.add(60)
bt_right_remove_test_1.add(78)
bt_right_remove_test_1.add(70)
bt_right_remove_test_1.add(50)
bt_right_remove_test_1.add(55)
bt_right_remove_test_1.add(65)
bt_right_remove_test_1.add(67)
bt_right_remove_test_1.add(69)
bt_right_remove_test_1.add(79)
bt_right_remove_test_1.remove(70)
bt_right_remove_test_1.preorder_traverse()
self.assertEqual(bt_right_remove_test_1.preorder_list, [60, 50, 55, 78, 65, 67, 69, 79])

print("bt right remove 2")
bt_right_remove_test_2_right = BinaryTree()
bt_right_remove_test_2_right.add(60)
bt_right_remove_test_2_right.add(50)
bt_right_remove_test_2_right.add(70)
bt_right_remove_test_2_right.add(75)
bt_right_remove_test_2_right.remove(70)
bt_right_remove_test_2_right.preorder_traverse()
self.assertEqual(bt_right_remove_test_2_right.preorder_list, [60, 50, 75])

print("bt left remove 3")
bt_left_remove_test_3 = BinaryTree()
bt_left_remove_test_3.add(60)
bt_left_remove_test_3.add(50)
bt_left_remove_test_3.add(70)
bt_left_remove_test_3.add(40)
bt_left_remove_test_3.add(55)
bt_left_remove_test_3.add(52)
bt_left_remove_test_3.remove(50)
bt_left_remove_test_3.preorder_traverse()
self.assertEqual(bt_left_remove_test_3.preorder_list, [60, 52, 40, 55, 70])

print("BST search test")
bt_search_test = BinaryTree()
bt_search_test.add(60)
bt_search_test.add(50)
bt_search_test.add(70)
bt_search_test.add(40)
bt_search_test.add(55)
bt_search_test.add(52)
self.assertTrue(bt_search_test.search(60))
self.assertTrue(bt_search_test.search(50))
self.assertTrue(bt_search_test.search(70))
self.assertTrue(bt_search_test.search(40))
self.assertTrue(bt_search_test.search(55))
self.assertTrue(bt_search_test.search(52))
self.assertFalse(bt_search_test.search(61))
self.assertFalse(bt_search_test.search(81))


코드가 조금 많이 긴 편입니다. 도움이 되셨으면 좋겠습니다.

github에서도 쉽게 코드를 확인하실 수 있습니다.


https://github.com/baidoosik/ProblemSolving/blob/master/DataStructure/BinaryTree.py


감사합니다.









안녕하세요.


요즘 Cracking the coding interview 라는 책을 통해서 공부하고 있습니다.


연결 리스트 문제 중에  비정렬 연결 리스트에서 중복 문자열을 제거하는 코드 문제를 파이썬으로 해결해보려고 합니다.


+ 임시 버퍼를 사용하는 방법과 임시 버퍼를 사용하지 않는 방법 두가지 모두 코드를 작성하여 봤습니다.



일단 값과 다음 노드를 가르키는 객체인 Node 객체를 만듭니다.




복사 가능한 코드


class Node:

    def __init__(self, value, next_node):

        self.value = value

        self.next = next_node



그리고 LinkedList 를 구현합니다.


여기서 설명은 원소를 추가, 삭제 ,조회 등을 구현하는 것은 설명하지 않고 중복 문자열을 제거하는 코드에 대해서만 설명을 할 것 입니다.



첫번째 함수는 임시 버퍼인 dictonary를 사용해서 O(n)의 시간 복잡도로 문제를 해결했습니다.


순회하면서  dictonary에 value를 넣고 중복되는 값이 있는지 체크하면서 중복된 경우 중복된 노드를 삭제하고 전 노드와 중복 노드가 가리키는 노드를 연결해서 문제를 해결했습니다.


두 번째 문제인 임시버퍼를 사용하지 않는 경우는 하나의 node 변수를 추가해서 시간 복잡도 O(n**2)의 시간복잡도로 하나의 값을 가지고 있으면서 


순회하면서 중복된 값을 찾아서 제거하는 방법을 사용했습니다.



전체 LinkedList 코드입니다.


class LinkedList:

    def __init__(self):

        self.head = Node(None, None)

        self.cur = None

        

    def add(self, value):

        self.cur = self.head

        while self.cur.next is not None:

            self.cur = self.cur.next

        self.cur.next = Node(value, None)

    

    def _remove(self, cur):

        cur.next = cur.next.next

    

    def remove(self, value):

        self.cur = self.head

        while self.cur.next is not None:

            if self.cur.next.value == value:

                self._remove(self.cur)

                return value

            self.cur = self.cur.next

        raise Exception("value not found")

        

    def show_all(self):

        self.cur = self.head.next

        

        while self.cur is not None:

            print(self.cur.value)

            self.cur = self.cur.next

    

    def remove_duplicate_word(self):

        self.cur = self.head

        temporary_buffer = {}

        while self.cur.next is not None:

            if temporary_buffer.get(self.cur.next.value) is not None:

                self._remove(self.cur)

            else:

                temporary_buffer[self.cur.next.value] = 0

                self.cur = self.cur.next

    

    # 임시 버퍼 사용 x

    def remove_duplicate_word_without_buffer(self):

        runner = self.head.next

        self.cur = self.head

        

        while runner is not None:

            self.cur = runner

            while self.cur.next is not None:

                if runner.value == self.cur.next.value:

                    self._remove(self.cur)

                else:

                    self.cur = self.cur.next

            runner = runner.next


해당 책의 문제들을 파이썬으로 해결한 코드를 Github에 올릴 예정입니다.


repository가 만들어지면 공유 드리도록 하겠습니다.








먼저 QUEUE 란?


- 선입 선출의 First In , First Out (FIFO) 의 특성을 갖는 자료구조.


- 조금 더 풀어서 말하면 먼저 들어온 데이터가 먼저 나간다.



가장 대표 적인 예시는 패스트 푸드 점의 주문 관리 시스템 먼저 받은 주문부터 먼저 음식을 줘야한다. (안주면 큰 일 나지요..)




Queue 를 구현하는 방법으로는 직선구조의 Queue나 원형 구조의 Queue, Linked Queue 가 있다.



단순한 직선 구조의 Queue 는 데이터가 10000 개 있다고 했을 때 enqueue, dequeue 과정에서 모든 데이터가 한 칸씩 움직여야 함으로 비효율


적이다.


이를 해결하기 위해서 Linked Queue 나 Circular Queue 를 이용하는데 Linked Queue를 이용하면 First Node 와 Last Node로 맨 앞의 데이터


와 뒤를 가리키게 하고, enqueue , dequeue시 이를 변경해주기만 하면 됨으로 효율적이다.


그래서 파이썬으로 



기본 적으로 파이썬의 자료구조인 리스트를 이용해서 구현해보고, 아쉬워서 Linked Queue도 구현해봤다.


코드는 기본적으로 리뷰가 안되었기 때문에 많이 가다듬은 코드는 아니기 때문에 참고하는데 주의를 ...



파이썬 built-in list로 구현한 QUEUE




두 번째로 파이썬으로 구현한 Linked QUEUE






다시 한 번 말하자면 혼자 생각하면서 바로 쓴 것이어서 문제가 발생할 수도 있으니 ㅎㅎ 


그냥 느낌만 보시길 추천..!






+ Recent posts