[자료구조] 완전 이진 트리, 이진 트리의 최대 깊이, 이진 탐색 트리

 

 

---

트리

트리는 그래프의 한 종류!
트리의 조건으로는, 사이클이 없어야 한다(순환 구조를 가지면 안됨).
또한, 한개의 부모만 가져야 한다. (부모가 한개 초과인 이상 그 것은 그냥 그래프, 트리아님)

[1, [2, [3]]]  ➡️  트리 ➡️  레이어가 존재해야 트리임!
[1, 2, 3] ➡️ 리스트

 

트리의 종류

이진트리: 자식 노드를 최대 2개 가질 수 있는 트리
포화 이진 트리: 모든 깊이가 포화 상태인 이진트리 (자식이 없거나 2개 있어야함)
완전 이진 트리: 노드 수가 n 개일 때, 1번부터 n개까지 노드가 있는 이진트리 (왼쪽부터 자식이 있어야함)
편향 이진 트리: 한쪽 방향으로만 자식이 있는 트리

---

완전 이진 트리

트리 구조를 표현하는 방법은 직접 클래스를 구현해서 사용하는 방법이 있고, 배열로 표현하는 방법이 있습니다.

 

엇, 트리 구조를 어떻게 배열에 저장할 수 있을까요?

바로 완전 이진 트리를 쓰는 경우에 사용할 수 있습니다!

 

완전 이진 트리는 왼쪽부터 데이터가 쌓이게 되는데,

이를 순서대로 배열에 쌓으면서 표현할 수 있습니다.

 

예를 들어 아래와 같은 완전 이진 트리를 배열에 표현한다면, 다음과 같습니다!

# bfs 순으로 배열 나열

      8      Level 0 -> [8] 첫번째 레벨의 8을 넣고,
    6   3    Level 1 -> [8, 6, 3] 다음 레벨인 6, 3을 넣고
   4 2 5     Level 2 -> [8, 6, 3, 4, 2, 5] 다음 레벨인 4, 2, 5를 넣으면 됩니다!

 

 

완전 이진트리의 높이

트리의 높이(Height)는, 루트 노드부터 가장 아래 리프 노드까지의 길이 입니다!

예를 들어 다음과 같은 트리의 높이는 2라고 할 수 있습니다.

      o      Level 0  # 루트 노드
    o   o    Level 1
   o o o     Level 2  # 가장 아래 리프 노드

이 트리의 높이는?  2 - 0 = 2!

 

 

그러면 한 번, 각 레벨에 노드가 꽉~~ 차 있으면 몇 개가 있는지 잠깐 생각해보겠습니다.

아래 예시를 보면, 레벨을 k라고 한다면 각 레벨에 최대로 들어갈 수 있는 노드의 개수는 2^k 개수 임을 알 수 있습니다.

      1            Level 0 -> 1개
    2   3          Level 1 -> 2개 
   4 5 6 7         Level 2 -> 4개
 8 9....... 14 15  Level 3 -> 8개 
                   Level k -> 2^k 개

 

 

❓ 만약 높이가 h 인데 모든 노드가 꽉 차 있는 완전 이진 트리라면 모든 노드의 개수는 몇개일까요?

1 + 2^1 + 2^2 + 2^3 + 2^4 ..... 2^h

즉, 이를 수식으로 표현하면 2^(h+1) - 1 이 됩니다!

즉, 높이가 h 일 때 최대 노드의 개수는 2^(h+1) - 1개 입니다. # 등비수열의합

 

그러면 이 때 최대 노드의 개수가 N이라면, h 는 뭘까요?

N = 2^(h+1) - 1 → h = log_2(N+1)-1 라고 할 수 있습니다!

 

즉! 완전 이진 트리 노드의 개수가 N일 때 최대 높이가 log_2(N+1) - 1 이므로

이진 트리의 높이는 최대로 해봤자 O(log(N)) 이구나! 라고 이해하시면 됩니다.

선형 구조는 보통 O(N) -> 이진트리로 구성하면 시간복잡도가 확 준다!

 

---

 

이진 트리의 최대 깊이

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/

이 문제에서는 트리의 깊이: 간선의 개수 ❌ 지나는 노드의 개수‼️

Input: root = [3,9,20,null,null,15,7]
Output: 3

 

test_max_depth.py

from collections import deque

from binarytree.prac import make_tree_by


def test_max_depth(lst):
	# 주어진 배열을 트리로 만든다.
    root = make_tree_by(lst, 0)
    # 루트가 없다면 깊이는 0
    if not root:
        return 0

	# q에 넣어 순차방문
    q = deque([root])
    depth = 0

    while q:
        depth += 1
        for _ in range(len(q)):
        	# current
            cur = q.popleft()
            if cur.left:
                q.append(cur.left)
            if cur.right:
                q.append(cur.right)

    return depth


assert test_max_depth(lst=[]) == 0
assert test_max_depth(lst=[3, 9, 20, None, None, 15, 7]) == 3

 

 

structures.py

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

 

 

prac.py

from binarytree.structures import TreeNode


def make_tree_by(lst, idx):
    parent = None
    # 주어진 트리의 크기보다 더 큰 index가지는 노드는 생성할 수 없다.
    if idx < len(lst):
    	# 부모
        value = lst[idx]
        if value is None:
            return
		
        # 부모 기준으로 노드 만들고
        parent = TreeNode(value)
        # 부모 기존 왼쪽, 오른쪽을 트리로 다시 구성
        parent.left = make_tree_by(lst, 2 * idx + 1)
        parent.right = make_tree_by(lst, 2 * idx + 2)

    return parent

 

 

---

 

이진 트리 반전

https://leetcode.com/problems/invert-binary-tree/description/

거울 반전 시키기

 

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

 

 

test_invert_btree.py

from binarytree.prac import make_tree_by, make_lst_by


def test_invert_btree(lst):
	# 리스트가 비었을 경우 빈 배열 반환
    if not lst:
        return []

	# 재귀적으로 반복
    def invert(parent):
        if parent:
        	# 오른쪽 child를 반전시킨 후 왼쪽으로 이동, 왼쪽 child를 반전시킨 후 오른쪽으로 이동
            # 2, 1, 3 -> 2, 3, 1 후 왼쪽, 오른쪽 switch
            parent.left, parent.right = invert(parent.right), invert(parent.left)
            return parent
	
    # 리스트를 이용하여 트리를 만듦
    root = make_tree_by(lst, 0)
    # 거울 반전 시킨 후 다시 리스트로 바꿔서 반환
    return make_lst_by(invert(root))


assert test_invert_btree(lst=[]) == []
assert test_invert_btree(lst=[2]) == [2]
assert test_invert_btree(lst=[2, 1, 3, 5, 6, 2, 3]) == [2, 3, 1, 3, 2, 6, 5]
assert test_invert_btree(lst=[4, 2, 7, 1, 3, 6, 9]) == [4, 7, 2, 9, 6, 3, 1]

 

prac.py

def make_lst_by(root):
	# 루트가 비었다면 빈 배열 반환
    if not root:
        return []

    lst = []
    q = deque([root])

	# bfs 순서
    while q:
        node = q.popleft()
        lst.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

    return lst

 

---

이진트리 : 자식의 개수가 0 또는 1 또는 2인 트리

이진 탐색 트리: 탐색에 용이(부모 기준 왼쪽: 부모보다 작은값, 오른쪽: 부모보다 큰 값)하게 된 이진트리!

 

이진 탐색 트리 (binary search tree)

• 부모 기준 왼쪽에는 작은 값, 오른쪽에는 큰 값을 가지는 이진 트리.
• 평균적으로 탐색의 시간복잡도는 O(logN). 치우친(skewed) 경우 O(n). 따라서 균형이 중요.
• (치우친 구조: ex. 루트가 1일 경우 -> 그냥 선형 구조 마냥 죽 늘어진 형태 => 최악의 경우 O(n) )
• 자가균형 이진탐색 트리는 AVL, 레드블랙 트리 등이 있다.

• 자바의 해시맵이 체이닝 시 연결리스트와 함께 레드블랙 트리를 병행해 저장한다.

---

 

정렬된 배열의 이진 탐색 트리 변환

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/

sorted array -> binary search tree 로 변환

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

 

test_sorted_array_to_bst.py

from binarytree.prac import sorted_array_to_bst, make_lst_by_bst


def test_sorted_array_to_bst(lst):
    if not lst:
        return []
    root = sorted_array_to_bst(lst)
    return make_lst_by_bst(root, len(lst))


assert test_sorted_array_to_bst(lst=[-10, -3, 0, 5, 9]) == [0, -3, 9, -10, None, 5]
assert test_sorted_array_to_bst(lst=[-10, -7, -3, -1, 0, 1, 4, 5, 7, 9]) == [1, -3, 7, -7, 0, 5, 9, -10, None, -1, None]

 

prac.py

def sorted_array_to_bst(lst):
    if not lst:
        return None

	# 중간값을 root로 잡음
    mid = len(lst) // 2

    node = TreeNode(lst[mid])
    node.left = sorted_array_to_bst(lst[:mid])
    node.right = sorted_array_to_bst(lst[mid + 1:])

    return node

# bfs 로직 + 빈 노드 None으로 표시하는 기능 추가
# limit: 내가 만들어야하는 리스트의 길이
def make_lst_by_bst(root, limit):
    if not root:
        return []

    lst = []
    q = deque([root])

    while q:
        if len(lst) > limit:
            break

        node = q.popleft()
        if node:
            lst.append(node.val)
            q.append(node.left)
            q.append(node.right)
        else:
        	# 추가할 Node가 없는 경우엔 None을 추가해준다!
            lst.append(None)

    return lst

 

---

 

이진탐색이란?

• 배열이 정렬되어있을 경우, 절반씩 줄여나가면서 탐색하는 기법 -> 비용↓

이진탐색의 효율성

• 1억 개 목록을 선형탐색할 때, 1억 번을 연산해야 한다. 이진탐색으로 찾는다면, 27번 안에 찾을 수 있다.

import math

math.log2(100000000) # 26.575424759098897

계속 절반으로 쪼개기 때문에 log2

 

• 이진탐색을 위해서는 정렬되어 있어야 한다.

 

이진 검색

https://leetcode.com/problems/binary-search/description/

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

 

 

구현

def binary_search(nums, target):
	# 내장함수
    # 어디서부터(시작요소) 어디까지(마지막요소) 돌 지 미리 지정
    def bs(start, end):
        # 시작점이 끝보다 index가 큰 경우 -> 값이 없는 것 -> -1리턴
        if start > end:
            return -1

        mid = (start + end) // 2
		
        # 이진 탐색
        # 찾는 값보다 작다면
        if nums[mid] < target:
            # 재귀 구조
            # 오른쪽으로 탐색
            return bs(mid + 1, end)
        elif nums[mid] > target:
            # 재귀 구조
            return bs(start, mid - 1)
        else:
            return mid

    return bs(0, len(nums) - 1)


assert binary_search(nums=[-1, 0, 3, 5, 9, 12], target=9) == 4
assert binary_search(nums=[-1, 0, 3, 5, 9, 12], target=2) == -1

 

파이썬 내장 함수 이용

def binary_search_builtin(nums, target):

	# bisect : 라이브러리
    # bisect_left : 바이너리 서치(이진탐색)를 왼쪽으로 한다.
    idx = bisect.bisect_left(nums, target)
    
    # idx == len(nums) 가능하기 떄문.
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """
    
    # 전체 배열의 길이를 넘지 않고 and 타겟과 일치하면
    if idx < len(nums) and nums[idx] == target:
        return idx
    # 없을 경우 -1 리턴
    else:
        return -1

 

import bisect

 

bisect.bisect_left([-1, 1, 2, 2, 2, 3] , 2) ➡️ 원하는 값이 있는 경우 가장 왼쪽 인덱스 ➡️ 2 리턴
bisect.bisect_left([-1, 1, 3, 3, 5] ,2)  ➡️ 내가 찾는 값이 없는 경우, 내가 찾는 값보다 작은 모든 값들 +1  ➡️ 2 리턴 
bisect.bisect_left([-5, -4, -3, -2, -1] , 2)  ➡️  5 반환
bisect.bisect_left([3, 4, 5, 6, 7] , 2)  ➡️  0 반환

 

bisect.bisect_right([1, 2, 2, 2, 3, 4], 2) ➡️ 주어진 인덱스에 있는 작은 모든 요소들보다 1 큰 값  ➡️  4 반환

 

bisect_right 는 있다는 것만 알고있으면 되고,

bisect_left는 이진탐색 시 굉장히 자주 사용하므로 잘 알아둘 것!

---

 

회전 정렬된 배열 검색 (Seach in Rotated Sorted Array)

https://leetcode.com/problems/search-in-rotated-sorted-array/description/

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Input: nums = [1], target = 0
Output: -1

 

 

def bs_rotated(nums, target):
    # 이진탐색
    def bs(lst, start, end):
        if start > end:
            return -1

        mid = (start + end) // 2
        if lst[mid] < target:
            return bs(lst, mid + 1, end)
        elif lst[mid] > target:
            return bs(lst, start, mid - 1)
        else:
            return mid

    if not nums:
        return -1

	# 최소점(left) 찾기
    left = 0
    # 가장 끝 점
    right = len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
	
    # [4, 5, 6, 7, 0, 1, 2] -> [4, 5, 6, 7, 0, 1, 2, 4, 5, 6, 7]
    added = nums + nums[:left]

	# added 기준으로 최소점부터 끝까지 이진탐색
    result = bs(added, left, len(added) - 1)
    # 최소점에서 원래 배열의 길이만큼 더해졌음. -> 값이 존재할 경우 len(nums)로 모듈러 연산
    return result if result == -1 else result % len(nums)

 

최소점 찾기

rotated sorted array

 

중간값(mid)가 가장 끝 값(right) 보다 큰 경우

 

➡️ 내가 지금 속한건 큰 부분! -> 내가 찾고 싶은 건 오른 쪽에 있다. ➡️ left = mid + 1

(큰 부분의 최소점은 작은 부분의 최고점보다 크므로)

- else : 만약 내가 작은 부분일 경우 ➡️ right = mid  왼쪽에서 찾는다!

 

 

 

 

---

 

예제1. 상위 K 빈도 요소

Q. 상위 k번 이상 등장하는 요소를 추출해보세요.

 

입력

nums = [1, 1, 1, 2, 2, 3], k=2

 

출력

[1, 2]

 

 

---

 

예제2. 부분집합

Q. 모든 부분 집합을 리턴하라.

 

입력

nums = [1, 2, 3]

 

출력 

[
	[3],
	[1],
	[2],
	[1,2,3],
	[1,3],
	[2,3],
	[1,2],
	[]
]