[Data Structure] Tree

Y_Y·2023년 4월 22일

BinarySearchTree BinaryTree datastructure tree 자료구조

Data-Structure

목록 보기

4/6

트리 (Tree)

특징

부모 자식간의 관계를 갖고 자료를 구성하는 자료구조를 트리라고 한다
자식 노드의 개수가 2이하인 트리 = 이진트리 (binary tree)

이진트리 (BinaryTree)

특징

루트 노드는 parent를 갖지 않는다.
preorder, inorder 값을 가지고 이진트리의 원래 구조를 reconstruct 할 수 있다.

class Node:
    def __init__(self, key, left, right):
    self.key = key
    self.parent = None
    self.left = None
    self.right = None
    
    def __str__(self):
        return str(self.key)
        
    def preorder(self): # 현재 방문중인 노드
        if self != None:
            print(self.key)
            self.left.preorder()
            self.right.preorder()
            
    def inorder(self):
        if self != None:            
            self.left.inorder()
            print(self.key)
            self.right.postorder()
        
    def postorder(self):
        if self != None:
            self.left.postorder()
            self.right.postorder()
            print(self.key)

이진탐색트리 (BinarySearchTree)

특징

각 노드의 왼쪽 subtree의 key 값은 노드의 key값보다 작거나 같아야 하고, 오른쪽 subtree의 key 값이 노드의 key값보다 같거나 커야 한다.

-> 만족할 경우 이진탐색트리라고 부른다

시간복잡도: O(h) = O(logn)

class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.size = 0
    
    def __len__(self):
        return self.size
# self.root로 class Node에 접근하여 __iter__()라는 특수 메소드를 부른다. 
# 만약 각각의 노드를 preorder순서로 방문하게 정의되어 있다면, preorder 순서로 방문한다
    def __iter__(self):
        return self.root.__iter__()
        # __iter__()는 generator라고 부르는데
        # iterator와 generator에 대해서 추가적으로 정리해서 업로드 하겠다.

search

def find_loc(self, key): # self -> class BST를 가리킨다.
# key 값 노드가 있다면 해당노드 return
# 없다면 노드가 삽입될 부모노드 리턴
    if self.size == 0:
        return None
    p = None # parent
    v = self.root # 현재노드
    while v != None: # 현재노드가 비어있지 않을 때 까지
        if v.key == key: return v # 현재노드의 key값과 key값 비교
        elif v.key < key: # 삽입할 노드가 더 크다면 right
            p = v
            v = v.right 
        else: # 작다면 left
            p = v
            v = v.left
    return P # key값이 Tree에 존재하지 않는다 return None
    
def search(self, key): # return 해당 노드의 위치
    v = self.find_loc(key)
    if v == None:
        return None
    else:
        return v

시간복잡도: O(h) = O(logn)

insert

def insert(self, key):
    p = self.find_loc(key)
    if p == None or p.key != key:
        v = Node(key)
        if p == None: # 첫 노드일 경우 (루트노드)
            self.root = v
        else: # 기존 노드가 존재할 경우
            v.parent = p # 현재 노드의 부모를 연결시켜주고
            if p.key > key: # key 값 비교 left or right
                p.left = v
            else:
                p.right = v
    self.size += 1
    return v
    else:
        print("key is already exist")
        return p #None

삽입할 위치를 찾는다.
Node를 생성한다
해당 위치의 부모노드의 left또는 right에 연결한다.
시간복잡도: O(h) = O(logn)

delete

def delete_by_merging(self, x):
    a = x.left, b = x.right
    pt = x.parent
    c = x자리를 대체할 노드
    m = L에서 가장 큰 노드
    if a != None: # a가 None일 때와 아닐 때
        c = a
        m = a
        while m.right != None:
            m = m.right
		if b != None:
            b.parent = m
        m.right = b
    else:
        c = b
        
    if pt != None: #
        if c: c.parent = pt # c가 None이 아닐 때
        if pt.key < c.key:
            pt.right = c
        else:
            pt.left = c        
    else: # x가 root이다 pt == None root를 지워야한다.
        self.root = c
        if c: c.parent = None # c가 None이 아닐 때
        
    self.size -= 1
    
def delete_by_copying(self, x):