자료구조/알고리즘 - 이진트리(2)

이진 탐색 트리란?

이진탐색과 연결리스트(linked list) 를 결합한 자료구조의 일종이다.
이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다.

이진탐색트리

부모 기준 왼쪽에는 작은 값, 오른쪽에는 큰 값을 가진다.
평균적으로 탐색의 시간복잡도는 O(logN), 치우친(skewed) 경우 O(n) 따라서 균형이 중요하다.

아래 그림에서 균형잡힌 경우와 치우친 경우를 확인할 수 있다.

균형/비균형 트리

이진 트리의 검색, 삽입, 삭제

검색

이진탐색트리에서 키 x를 가진 노드를 검색하고자 할때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NULL을 리턴한다.
검색하고자 하는 값을 루트노드와 먼저 비교하고, 일치할 경우 루트노드를 리턴한다.
불일치하고 검색하고자 하는 값이 루트노드의 값보다 작을 경우 왼쪽 서브트리에서 재귀적으로 검색한다.
불일치하고 검색하고자 하는 값이 루트노드의 값보다 큰 경우 오른쪽 서브트리에서 재귀적으로 검색한다.

위 와 같은 식으로 검색을 진행한다.

삽입

삽입을 하기 전, 검색을 수행한다.
트리를 검색한 후 키와 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교하여서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다.

삭제

삭제하려는 노드의 자식 수에 따라

자식노드가 없는 노드(리프 노드) 삭제 : 해당 노드를 단순히 삭제한다.
자식노드가 1개인 노드 삭제 : 해당 노드를 삭제하고 그 위치에 해당 노드의 자식노드를 대입한다.
자식노드가 2개인 노드 삭제 : 삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰값으로 변경하거나, 오른쪽 서브트리에서 가장 작은 값으로 변경한 뒤, 해당 노드(왼쪽서브트리에서 가장 큰 값을 가지는 노드 또는 오른쪽 서브트리에서 가장 작은 값을 가지는 노드)를 삭제한다.

오늘 푼 문제

https://geonoo.tistory.com/107

[파이썬] 938. Range Sum of BST - 리트코드

https://geonoo.tistory.com/108

[파이썬] 700. Search in a Binary Search Tree - 리트코드

https://geonoo.tistory.com/109

[파이썬] 297. Serialize and Deserialize Binary Tree - 리트코드

파이썬 global, nonlocal

[global]

num = 0

def chnage_num():
    global num
    num = 100
    print(num) # 100

chnage_num()

print(num) # 100

global은 전역변수를 함수내에서 변경하거나 재할당 하고 싶을때 사용하는 키워드이다.

[nonlocal]

def print_nums():
    num = 0

    def change_num():
        nonlocal num
        num = 100
        print(num) # 100

    change_num()

    print(num) # 100

print_nums()

change_num() 함수 바깥에서 선언된 num이라는 비지역 변수의 값을 변경할 때 사용하는 변수이다.

 

회고

오늘은 어느 한 문제를 제대로 못 풀었다. 무엇이 문제였을까... 다시 풀어보면 봤던 문제라서 그나마 풀리긴하는데 역시 처음에 접근조차 못하니까 답답한 마음이 가득하다...

거기다 오늘은 과제톡 발표를하는데 깔끔하게 마루리를 못지었다. 잘 되던 코드가 안되서 머리가 말하고 싶었던 부분을 잊어버렸다.
개인적으로 혼자 설명하면서 연습을 하긴 했는데, 내 머릿속에 확실히 정리 되지 않아서 그런지 아쉬운점이 많았다.

다음엔 더 잘해보자!