[Algorithm] Binary Search Tree

바이너리 서치 트리

이진트리 구성하기 < 정렬된 트리가 있다 라고 가정하고, 탐색하는 방법

• BST 도 결국 트리의 한 종류
  • 왼쪽에 있는 노드는 반드시 부모 노드보다 값이 작아야한다
  • 오른쪽에 있는 노드는 반드시 부모 노드보다 값이 커야한다
• 중위순회 하면, 오름차순으로 된 것을 확인 할 수 있다
• 완전 이진 트리여야 한다

힙

• 완전 이진트리에 있는 노드 중에서 키 값이 가장 큰 노드, 또는 가장 작은 노드를 찾기 위해 만들어진 자료구조
• 힙은 트리의 한 종류일 뿐.
• 힙은 굳이 BST일 필요는 없다

max heap

• 부모가 자식보다 값이 커야한다
• 가장 큰 노드를 찾기 위해 사용
• 루트 노드 == 가장 값이 큰 노드

min heap

• 부모가 자식보다 값이 작아야한다
• 가장 작은 노드를 찾기 위해 사용
• 루트 노드 == 가장 값이 작은 노드

Heap 을 배열로

L = int(input()) # 트리의 레벨
레벨 별로 얼마만큼의 노드가 생성될 지 계싼이 가능하다.

L = int(input()) # 트리의 레벨

# number of nodes per level = 2**(L-1)
# => 1,2,4,8 ...

N = 6  
data = [3,6,2,1,7,9]

tree = [0 for _ in range(N+1)]
last = 1

for i in range(len(data)):
	if not tree[i]:
    	tree[last] = data[i]
    else:
    	last += 1
        child = last # 새로 추가된 정점을 자식으로
        parent = child // 2  # 완전 이진 트리에서 부모 정점 번호 
		
        tree[child] = data[i]
        # print(Tree, child, parent)
    # 부모가 있고, 부모가 자식보다 큰 동안(부모가 작아질 때 까지)
    while parant >= 1 and tree[parent] > tree[child]:
    	#부모와 자식의 위치를 변경 
    	tree[parent], tree[child] = tree[child], tree[parent]
        # 자식 위치를 부모로 변경
        child = parent
        # 부모는 부모 // 2 => 조상노드 
        parent = parent // 2
        
print(tree) # [0,1,2,3,6,7,9]