[TIL: 0223] 이진트리2

ryun·2023년 2월 23일

TIL

목록 보기

24/34

노드 - 1 = 간선의 수

def preorder(i):
	if i:  # 존재하는 정점이면
    	print(i, end = ' ')
        preorder(left[i])
        preorder(right[i])
    return
    
def inorder(i):
	if i:
		inorder(left[i])
        print(i, end = ' ')
    	inorder(right[i])
    return
    
def postorder(i):
	if i:
    	postorder(left[i])
        postorder(right[i])
        print(i, end = ' ')
    return 

V = int(input())
arr = list(map(int, input().split()))
E = V - 1  # 간선 수
left = [0] * (V + 1)  # 부모를 인덱스로 왼쪽 자식 저장
right = [0] * (V + 1)  # 부모를 인덱스로 오른쪽 자식 저장
par = [0] * (V + 1)  # 자식을 인덱스로 부모 저장
# child = [[] for _ in range(V + 1)]
for i in range(E):
	p, c = arr[i * 2], arr[i * 2 + 1]
    if left[p] == 0:
    	left[p] = c
    else:
    	right[p] = c
    #child[p].append(c)
 root = 1
 while par[root] != 0:  # root 찾기
 	root += 1
 preorder(root)

수식 트리

수식을 표현하는 이진 트리
수식 트리의 순회

이진 탐색 트리

탐색 작업을 효율적으로 하기 위한 자료구조

모든 원소는 서로 다른 유일한 키를 갖는다

key(왼쪽 서브트리) < key(루트노드) < key(오른쪽 서브트리)

왼쪽 서브트리와 오른쪽 서브트리 내도 이진 탐색 트리다

탐색 트리

탐색할 키 값 x를 루트 노드의 키 갑과 비교
탐색할 x가 루트보다 작으면 왼쪽 서브트리를 기준으로 이동

삽입 연산

탐색 연산 수행

같은 원소가 트리에 있는지 확인
탐색 실패가 결정되는 위치가 삽입 위치

실패한 위치에 원소 삽입

이진탐색트리 - 성능

탐색, 삽입, 삭제 시간은 트리 높이만틈 시간이 걸린다: O h, BTS의 길이
평균의 경우
균형적으로 생성되어있는 경우 O(log n)
최악의 경우
한족으로 치우친 경사 이진트리의 경우 순차탐색과 시간복잡도가 같다

이진탐색트리 - 연산 연습

삭제 연산
13, 12, 9 차례로 삭제

참고) 힙

완전 이진 트리 노드 중 키 값이 가장 큰 노드나 가장 작은 노드 찾기 위해 만든 자료구조
최대 힙 (max heap)
키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
부모노드 키값 > 자식노드 키값
루트노드: 키값이 가장 큰 노드
최소 힙 (min heap)
키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
부모노드 키값 < 자식노드 키값
루트노드: 키값이 가장 작은 노드
트리 1 중간이 빠졌다 (왼쪽자식부터 들어와야함), 트리 2 일관성이 없다 (최대힙이든지 최소힙 둘 중에 하나여야함)
이진트리의 최대힙에 원소 삽입하기

23넣을 때 먼저 완전 이진트리 완성 후 자리 바꾸기까지 진행 (한번 바꿨다고 끝이 아니라 부모가 자식보다 큰 조건을 만족하거나 자리바꾸는 원소가 루트에 도착할 때까지)