IT-garden

이진트리(BinaryTree)는 각 노드의 자식수가 2 이하인 트리입니다.

이진트리에는 4가지 순회방식이 존재합니다. 방식은 각각 다르지만 항상 트리의 루트부터 시작한다는 공통점이 있습니다. 또한 모든 순회 방식은 트리의 모든 노드들을 반드시 1번씩 방문하고 순회를 종료합니다.

1. 전위순회(Preorder Traversal)

전위순회의 순회방법입니다.

• 현재 노드 n를 먼저 방문합니다.
• 현재 노드의 왼쪽 서브트리를 순회합니다.
• 현재 노드의 오른쪽 서브트리를 순회합니다.

전위순회의 순서는 NLR입니다. (N은 현재 노드, L은 왼쪽 서브트리, R은 오른쪽 서브트리)

def preorder(self, n):
        if n != None:
            print(n.item,' ',end='') # 노드 방문
            if n.left:
                self.preorder(n.left) # 왼쪽 서브트리 순회
            if n.right:
                self.preorder(n.right) # 오른쪽 서브트리 순회

2. 중위순회(Inorder Traversal)

중위순회의 순회방법입니다.

• 현재 노드의 왼쪽 서브트리를 순회합니다.
• 현재 노드 n을 방문합니다.
• 현재 노드의 오른쪽 서브트리를 순회합니다.

중위순회의 순서는 LNR입니다.

def inorder(self, n):
        if n != None:
            if n.left:
                self.preorder(n.left) # 왼쪽 서브트리 순회
            print(n.item,' ',end='') # 노드 방문
            if n.right:
                self.preorder(n.right) # 오른쪽 서브트리 순회

3. 후위순회(Postorder Traversal)

후위순회의 순회방법입니다.

• 현재 노드의 왼쪽 서브트리를 순회합니다.
• 현재 노드의 오른쪽 서브트리를 순회합니다.
• 현재 노드 n을 방문합니다.

후위순회의 순서는 LRN입니다.

def postorder(self, n):
        if n != None:
            if n.left:
                self.preorder(n.left) # 왼쪽 서브트리 순회
            if n.right:
                self.preorder(n.right) # 오른쪽 서브트리 순회
            print(n.item,' ',end='') # 노드 방문

4. 레벨순회(Level-order Traversal)

레벨순회의 순회방법입니다.

• 루트가 있는 곳부터 각 레벨마다 좌에서 우로 노드들을 방문합니다.

def levelorder(self, root):
        q=[] # 리스트 구현(큐로 사용하기 위해)
        q.append(root)
        while q:
            t=q.pop(0)
            print(t.item,' ',end='') # 큐에서 첫 항목 삭제하고 삭제한 노드 방문
            if t.left != None:
                q.append(t.left) # 왼쪽 자식 큐에 삽입
            if t.right != None: 
                q.append(t.right) # 오른쪽 자식 큐에 삽입

위 트리 형태를 4가지 방법으로 순회해보겠습니다.

이진트리 전체 파이썬 코드입니다.

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

class BinaryTree():
    def __init__(self): # 트리 생성
        self.root = None

    # 전위순회
    def preorder(self, n):
        if n != None:
            print(n.item,' ',end='') # 노드 방문
            if n.left:
                self.preorder(n.left) # 왼쪽 서브트리 순회
            if n.right:
                self.preorder(n.right) # 오른쪽 서브트리 순회

    # 중위순회
    def inorder(self, n):
        if n != None:
            if n.left:
                self.preorder(n.left) # 왼쪽 서브트리 순회
            print(n.item,' ',end='') # 노드 방문
            if n.right:
                self.preorder(n.right) # 오른쪽 서브트리 순회

    # 후위순회
    def postorder(self, n):
        if n != None:
            if n.left:
                self.preorder(n.left) # 왼쪽 서브트리 순회
            if n.right:
                self.preorder(n.right) # 오른쪽 서브트리 순회
            print(n.item,' ',end='') # 노드 방문

    # 레벨순회
    def levelorder(self, root):
        q=[] # 리스트 구현(큐로 사용하기 위해)
        q.append(root)
        while q:
            t=q.pop(0)
            print(t.item,' ',end='') # 큐에서 첫 항목 삭제하고 삭제한 노드 방문
            if t.left != None:
                q.append(t.left) # 왼쪽 자식 큐에 삽입
            if t.right != None: 
                q.append(t.right) # 오른쪽 자식 큐에 삽입

    def height(self, root):
        if root == None:
            return 0
        # 루트 노드를 기준으로 두 자식노드의 높이 중 큰 높이 
        return max(self.height(root.left), self.height(root.right)) + 1


tree=BinaryTree()
n1=Node(10)
n2=Node(20)
n3=Node(30)
n4=Node(40)
n5=Node(50)
n6=Node(60)
n7=Node(70)
n8=Node(80)

# 트리 만들기
tree.root=n1
n1.left=n2
n1.right=n3
n2.left=n4
n2.right=n5
n3.left=n6
n3.right=n7
n4.left=n8

# 출력>>트리 높이 : 4
print('트리 높이 :', tree.height(tree.root))

# 출력>>전위순회 : 10  20  40  80  50  30  60  70  
print('전위순회 : ',end='')    
tree.preorder(tree.root)

# 출력>>중위순회 : 20  40  80  50  10  30  60  70  
print('\n중위순회 : ',end='')
tree.inorder(tree.root)

# 출력>>후위순회 : 20  40  80  50  30  60  70  10  
print('\n후위순회 : ',end='')
tree.postorder(tree.root)

# 출력>>레벨순회 : 10  20  30  40  50  60  70  80  
print('\n레벨순회 : ',end='')
tree.levelorder(tree.root)

트리는 그래프의 종류로 실제 트리를 거꾸로 세워 놓은 모양의 자료구조입니다.

트리의 예시로는 조직의 계층구조가 있습니다.

트리에서는 알아야 할 용어들이 있습니다.

루트 : 트리의 최상위에 있는 노드

부모 노드 : 노드의 상위에 연결된 노드

자식 노드 : 노드의 하위에 연결된 노드

형제 노드 : 동일한 부모를 가지는 노드

조상 노드 : 루트까지의 경로상에 있는 모든 노드들의 모임

후손 노드 : 노드 아래로 있는 모든 노드들의 모임

차수 : 자식 노드의 수

이파리 : 자식이 없는 노드

레벨 : 깊이(루트가 레벨 1이고 아래로 갈수록 1씩 증가

높이 : 트리의 최대 레벨

위의 트리에서 보면 루트는 A입니다.

B와 C의 부모노드는 A이고 A의 자식 노드는 B, C입니다.

그리고 B와 C는 부모노드가 A로 같기 때문에 형제 노드입니다.

L의 조상 노드는 G, C, A입니다.
C의 후손 노드는 G, H, L, M입니다.
A의 차수는 2입니다.
이파리는 I, J, E, K, L, M, H입니다.
트리의 높이는 4입니다.

원형연결리스트(Circular Linked List)는 단순연결리스트에서 첫 노드와 마지막 노드를 연결한 연결리스트를 구현한 자료구조입니다.

마지막 노드를 참조하는 last가 단순연결리스트의 head 역할을 하기 때문에 마지막 노드와 첫 노드를 O(1) 시간에 방문할 수 있습니다.

리스트가 비어있지 않으면 어떤 노드도 None를 가지고 있지 않기 때문에 프로그램에서 None 조건을 검사하지 않아도 된다는 장점을 가집니다.

하지만 원형연결리스트에서는 반대 방향으로 노드들을 방문하기 쉽지 않으며 무한 루프가 발생할 수 있다는 단점이 있습니다.

원형연결리스트의 기본 구조입니다.

last는 원형연결리스트의 첫 번째 노드가 무엇인가 의미하는 정보입니다.

node는 아이템과 레퍼런스를 가집니다.

item은 항목으로 node값이 저장됩니다.

reference는 메모리 주소를 의미하며 다음 노드의 위치를 알려줍니다.

insert() : 리스트가 empty인 경우, 일반적인 경우

delete() : 한 개의 노드만 있는 경우, 노드가 2개 이상 있는 일반적인 경우

원형연결리스트의 파이썬 코드입니다.

class CList:
    class Node:
        def __init__(self, item, link): # 노드 생성자
            self.item = item  # 항목
            self.next = link  # 다음 노드 레퍼런스

    def __init__(self):  # 원형 연결 리스트 생성자
        self.last = None  # 마지막 노드를 가리킴
        self.size = 0

    def no_items(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def insert(self, item):  # 새 항목을 리스트의 첫 노드로 삽입
        n = self.Node(item, None)  # 새 노드를 생성하여 n이 참조
        if self.is_empty():  # 연결 리스트가 empty인 경우
            n.next = n  # 새 노드는 자신을 참조
            self.last = n  # last는 새 노드 참조
        else:
            n.next = self.last.next  # 새 노드는 첫 노드 참조
            self.last.next = n  # last가 참조하는 노드와 새 노드 연결
        self.size += 1

    def first(self):  # 원형 연결 리스트의 첫 항목
        if self.is_empty():
            raise EmptyError('Underflow')
        f = self.last.next
        return f.item

    def delete(self):  # 연결 리스트의 첫 노드를 삭제
        if self.is_empty():
            raise EmptyError('Underflow')
        x = self.last.next
        if self.size == 1:  # 연결 리스트에 노드가 1개인 경우
            self.last = None  # empty 리스트 됨
        else:  # 연결 리스트에 노드가 2개 이상인 경우
            self.last.next = x.next  # last가 참조하는 노드가 두번째 노드를 연결
        self.size -= 1
        return x.item

    def print_list(self):
        if self.is_empty():
            print('리스트 비어있음')
        else:
            f = self.last.next
            p = f
            while p.next != f:  # 첫 노드가 다시 방문되면 루프 중단
                print(p.item, ' -> ', end='')
                p = p.next  # 노드들을 차례로 방문
            print(p.item)

class EmptyError(Exception):  # Underflow시 에러 처리
    pass


s = CList()  # 원형 연결 리스트 객체 생성
s.insert('pear')
s.insert('cherry')
s.insert('orange')
s.insert('apple')
s.print_list()

print('s의 길이 =', s.no_items())

print('s의 첫 항목 :', s.first())

s.delete()
print('첫 노드 삭제 후: ', end='')
s.print_list()

print('s의 첫 길이 =', s.no_items())

print('s의 첫 항목 :', s.first())

s.delete()
print('첫 노드 삭제 후: ', end='')
s.print_list()

s.delete()
print('첫 노드 삭제 후: ', end='')
s.print_list()

s.delete()
print('첫 노드 삭제 후: ', end='')
s.print_list()

위의 개념과 소스코드는 생능출판의 '파이썬과 함께하는 자료구조의 이해'를 보고 이해하여 정리한 것입니다.

이중연결리스트(Doubly Linked List)는 각 노드가 두 개의 레퍼런스를 가지고 각각 이전 노드와 다음 노드를 가리키는 연결리스트를 구현한 자료구조입니다.

이중연결리스트는 단순연결리스트의 단점(역방향으로 노드 탐색 불가능, 삽입이나 삭제시 반드시 이전 노드를 가리키는 레퍼런스를 추가로 알아야 함)을 보완하기 위해 나왔습니다.

하지만 노드마다 2개의 레퍼런스를 저장해야 한다는 단점이 있습니다.

이중연결리스트의 기본 구조입니다.

head는 이중연결리스트의 첫 번째 노드가 무엇인가 의미하는 정보입니다.

tail은 이중연결리스트의 마지막 노드가 무엇인가 의미하는 정보입니다.

node는 아이템과 레퍼런스 2개를 가집니다.

item은 항목으로 node값이 저장됩니다.

reference1는 메모리 주소를 의미하며 이전 노드의 위치를 알려줍니다.

reference2는 메모리 주소를 의미하며 다음 노드의 위치를 알려줍니다.

__init__(self) : DList 객체 생성

insert_before() : p가 가리키는 노드 앞에 새 노드를 삽입

insert_after() : p가 가리키는 노드 뒤에 새 노드를 삽입

delete() : 노드 x 삭제

이중연결리스트의 파이썬 코드입니다.

class DList:
    
    class Node:
        def __init__(self, item, prev, link):  # 노드 생성자
            self.item = item  # 항목
            self.prev = prev  # 앞노드 레퍼런스
            self.next = link  # 뒤노드 레퍼런스

    def __init__(self):  # 이중 연결 리스트 생성자
        # head, tail, 항목수로 구성
        # 두 더미노드(head, tail)에는 실제 항목 저장하지 않음
        self.head = self.Node(None, None, None)
        self.tail = self.Node(None, self.head, None)
        self.head.next = self.tail
        self.size = 0

    def size(self):
        return self.size

    def isempty(self):
        return self.size == 0

    def insert_before(self, p, item):  # p가 가리키는 노드 앞에 새 노드를 삽입
        t = p.prev # p 앞의 기존 노드
        n = self.Node(item, t, p)  # 삽입할 노드
        p.prev = n  # 새 노드와 뒤 노드 연결
        t.next = n  # 새 노드와 앞 노드 연결
        self.size += 1 

    def insert_after(self, p, item):  # p가 가리키는 노드 뒤에 새 노드를 삽입
        t = p.next # p 뒤의 기존 노드
        n = self.Node(item, p, t)  # 삽입할 노드
        t.prev = n  # 새 노드와 뒤 노드 연결
        p.next = n  # 새 노드와 앞 노드 연결
        self.size += 1

    def delete(self, x):  # 노드 x 삭제
        f = x.prev # x 앞의 기존 노드
        r = x.next # x 뒤의 기존 노드
        f.next = r  # x를 건너뛰고 x의 앞뒤 노드를 연결
        r.prev = f  # x를 건너뛰고 x의 앞뒤 노드를 연결
        self.size -= 1
        return x.item

    def print_list(self):
        if self.isempty():
            print('List is empty.')
        else:
            p = self.head.next
            while p != self.tail:
                if p.next != self.tail:
                    print(p.item, ' <=> ', end='')
                else:
                    print(p.item)
                p = p.next  # 노드를 차례로 방문

class EmptyError(Exception):  # Underflow시 에러 처리
    pass


s = DList() # 이중 연결 리스트 생성
s.insert_after(s.head, 'apple') 
s.insert_before(s.tail, 'orange')
s.insert_before(s.tail, 'cherry')
s.insert_after(s.head.next, 'pear')
s.print_list()

print('마지막 노드 삭제 후:\t', end='')
s.delete(s.tail.prev)
s.print_list()

print('맨 끝에 포도 삽입 후:\t', end='')
s.insert_before(s.tail, 'grape')
s.print_list()

print('첫 노드 삭제 후:\t', end='')
s.delete(s.head.next)
s.print_list()

print('두 번째 노드 삭제 후:\t', end='')
s.delete(s.head.next.next)
s.print_list()

print('첫 노드 삭제 후:\t', end='')
s.delete(s.head.next)
s.print_list()

print('첫 노드 삭제 후:\t', end='')
s.delete(s.head.next)
s.print_list()

위의 개념과 소스코드는 생능출판의 '파이썬과 함께하는 자료구조의 이해'를 보고 이해하여 정리한 것입니다.

단순연결리스트(Singly Linked List)는 동적 메모리 할당을 이용해 노드들을 한 방향으로 연결하여 리스트를 구현한 자료구조입니다.

단순연결리스트는 삽입이나 삭제 시 항목들의 이동이 필요없습니다.

하지만 항목을 탐색하려면 항상 첫 노드부터 원하는 노드를 찾을 때까지 차례로 방문하는 순차탐색을 이용해야 합니다.

단순연결리스트의 기본 구조입니다.

head는 단순연결리스트의 첫 번째 노드가 무엇인가 의미하는 정보입니다.

node는 아이템과 레퍼런스를 가집니다. 

item은 항목으로 node값이 저장됩니다.

reference는 메모리 주소를 의미하며 다음 노드의 위치를 알려줍니다.

Insert_front() : 새 노드를 단순연결리스트의 맨 앞에 삽입, 시간복잡도 : O(1)

Insert_after() : p가 가리키는 노드의 다음에 삽입, 시간복잡도 : O(1)

delete_front() : 단순연결리스트의 첫 노드 삭제, 시간복잡도 : O(1)

delete_after() : p가 가리키는 노드의 다음 노드 삭제, 시간복잡도 : O(1)

단순연결리스트의 파이썬 코드입니다.

class SList:
    
    class Node:
        def __init__(self, item, link):  # 노드 생성자
            self.item = item  # 항목
            self.next = link  # 다음 노드 레퍼런스
            
    def __init__(self):  # 단순 연결 리스트 생성자
        self.head = None
        self.size = 0  

    def size(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def insert_front(self, item):  # 연결 리스트의 맨 앞에 새 노드 삽입
        if self.is_empty():  # 연결 리스트가 empty인 경우
            self.head = self.Node(item, None)  # head가 새 노드 참조
        else: 
            self.head = self.Node(item, self.head)  # head가 새 노드 참조
        self.size += 1

    def insert_after(self, item, p):  # p가 가리키는 노드 다음에 새 노드 삽입
        p.next = SList.Node(item, p.next)  # 새 노드가 p 다음 노드
        self.size += 1

    def delete_front(self):  # 연결 리스트의 맨 앞 노드 삭제 
        if self.is_empty():  # empty인 경우 에러 처리
            raise EmptyError('Underflow')
        else:
            self.head = self.head.next  # head가 둘째 노드를 참조
            self.size -= 1

    def delete_after(self, p):  # p가 가리키는 노드의 다음 노드 삭제
        if self.is_empty():  # empty인 경우 에러 처리
            raise EmptyError('Underflow')
        t = p.next
        p.next = t.next  # p 다음 노드를 건너뛰어 연결
        self.size -= 1

    def search(self, target):  # 노드 탐색(순차탐색)
        p = self.head
        for k in range(self.size): 
            if target == p.item:
                return k  # 탐색 성공
            p = p.next
        return None  # 탐색 실패

    def print_list(self):
        p = self.head
        while p:
            if p.next != None:
                print(p.item, ' -> ', end='')
            else:
                print(p.item)
            p = p.next  # 노드들을 순차탐색

class EmptyError(Exception):  # 에러 처리
    pass



s = SList() #객체생성
s.insert_front('orange')
s.insert_front('apple')
s.insert_after('cherry',s.head.next)
s.insert_front('pear')
s.print_list()

print('cherry는 %d번째' % s.search('cherry'))
print('kiwi는', s.search('kiwi'))   

print('배 다음 노드 삭제 후:\t\t', end='')
s.delete_after(s.head)
s.print_list()

print('첫 노드 삭제 후:\t\t', end='')
s.delete_front()
s.print_list()
print('첫 노드로 망고, 딸기 삽입 후:\t', end='')
s.insert_front('mango')
s.insert_front('strawberry')
s.print_list()
s.delete_after(s.head.next.next)

print('오렌지 다음 노드 삭제 후:\t', end='')
s.print_list()

위의 개념과 소스코드는 생능출판의 '파이썬과 함께하는 자료구조의 이해'를 보고 이해하여 정리한 것입니다.

덱은 Double ended Queue로 양방향 큐를 의미합니다.

앞, 뒤 모두 삽입과 삭제가 가능한 자료구조입니다.

덱을 이용하면 스택과 큐를 모두 구현할 수 있습니다.

덱은 파이썬 라이브러리 deque()를 사용해 구현할 수 있습니다.

덱에서는 여러가지 연산이 있습니다.

append(x) : 덱의 가장 뒤에 x 삽입
appendleft(x) : 덱의 가장 앞에 x 삽입
pop : 덱의 가장 뒤 원소를 제거
popleft : 덱의 가장 앞 원소 제거

덱의 파이썬 코드입니다.

from collections import deque

deq = deque()

deq.append(1)
deq.appendleft(2)
deq.append(3)
deq.appendleft(4)
deq.append(5)

# 출력>>deque([4, 2, 1, 3, 5])
print(deq)

deq.pop()
# 출력>>deque([4, 2, 1, 3])
print(deq)

deq.popleft()
# 출력>>deque([2, 1, 3])
print(deq)

deq.pop()
# 출력>>deque([2, 1])
print(deq)