grape/tree/heap/bst

Graph

• 노드,정점 (Node)와 간선 (Egde)로 구성
• 들어오는 간선 수를 indegree
• 나가는 간선 수를 outdegree
• 최단거리 구하기..

---

저장하는 방법 - 인접행렬

---

방향성을 추가하면?

---

가중치를 추가하면?

---

sparse 한 그래프라면? - 인접리스트

• 0이 차지하는 비율이 절반 이상(sparse) 이므로 메모리 낭비 - 인접리스트로 표현
• (도착지, 가중치)
• 1의 indegree - 0 / outdegree - 3

---

Tree

• 노드,정점 (Node)와 간선 (Egde)로 구성
• 상위 하위 관계를 나눌 수 있음
• 싸이클이 없다.
• 모든 노드가 연결이 되어야 한다.
• 간선의 수는 N-1, 노드의 수는 N개이다.

---

Tree에서 사용하는 명칭

• 부모(Parent)와 자식(Child)
• 선조(Ancestor)와 자손(Descendant)
• 뿌리(Root)와 잎(Leaf)

---

Tree 저장방식

• 부모만 저장 : 1개만 저장
  • 1 2 3 4 5 6 7 8
  •  

    

  • O(N) 1차원 배열에 저장
  • 장점 : 선조에 대한 노드를 재귀적으로 따라갈 수 있다.
• 자식들까지 저장 : root에서 뻗어나가기 쉬움

  • 

  • 장점 : 순환하기 좋다.

---

Tree 예제 1

• 총 9명이 존재
• 7번 노드와 3번 노드 사이의 촌수를 구하고 싶다.
• 부모자식 관계는 총 7개가 있다.
• 공통된 조상이 있어야 촌수가 존재한다.
• 공통 조상(LCA) 으로 부터의 각각의 거리의 합 = 촌수

N = int(input())

A, B = map(int, input().split()) // 7명 입력 받기
p = [0 for_ in range(N+1)] // 관계 저장, 7개의 관계 부모 초기값 0으로 지정

for _ in range(int(input())):
    x, y = map(int, input())
    p[y] = x // y의 부모는 x로 지정
    
Aa, Ba = [], [] // 자신을 포함한 자신들의 조상을 올려보냄
Ad, Bd = 0, 0 // 나와의 촌수

while p[A] > 0: // 최상단 부모를 찾을 때 까지
    Aa.append((A, Ad))
    Ad += 1
    A = p[A] 
    // A가 3일 때 
    // 3의 부모인 1이 p[A]가 되고 
    // 3과 1의 가중치를 Ad로 넣고 
    // 해당 부모인 p[A]는 나 자신 A가 된다.
    
while p[B] > 0: // 최상단 부모를 찾을 때 까지
    Ba.append((B, Bd))
    Bd += 1
    B = p[B] 
    
for i in Aa:
    for j in Ba;
    	if i[0] == j[0]: // 첫번째 조상이 같을 경우
        	print(i[1] + j[1]) // 촌수 출력
            exit()
            
print(-1)

---

이진트리

• 부모 노드가 X 이면, 왼쪽 노드가 2X 오른쪽 노드가 2X+1
• 이진트리를 바탕으로 Heap과 Bst가 나타남

---

Tree 예제 2

• 이진트리
• 나를 2로 나눈 몫은 무조건 부모이다.
• 33, 79의 공통 부모 찾기

while not a==b:
    if a>b: a//=2
    else: b//=2
print(a)

---

Heap

• 우선순위가 가장 높은 값을 Root 노드로 만듦
• 첫째 루트는 랜덤하게 지정하고 값을 붙이면서 크기가 큰 값이 root 가 되도록 설정함

• 가장 큰 값이 최상단 ROOT가 되어야 한다
• 큰 이진트리가 있다고 가정할 때, 총 갯수는?
  • 높이가 N일 때, 2^(N+1) -1개
• 제일 하단 노드부터 제일 상단 노드로 올라갈 때 까지의 시간복잡도는?
  
  • O(N)
  • 총 개수는 대략 2^N 이고, 이를 K로 표현하면,
    N = log2K
    O(logN)

---

Binary Search Tree (BST)

• 나보다 작은건 왼쪽으로, 큰건 오른쪽으로
• 검색의 시간 복잡도 O(logN)
• 단점 : 한쪽 ( 왼쪽 or 오른쪽 )으로 치우쳐질 수 있다 ( 메모리 낭비 )