학부과정/알고리즘
hertaehoon
2022. 12. 21. 11:45
2022. 12. 21. 11:45
인접행렬 장&단점
장점
- 구현하기 간단하다
- ((i,j)에 간선이 있는지 알기 쉽다)
단점
- 아무리 간선수가 적어도 O(n^2)개의 방이 필요하다
연결리스트
장점
단점
- (i,j) 사이에 간선이 있음을 알기위해 연결리스트 탐색 시간 필요
hertaehoon
2022. 12. 21. 11:42
2022. 12. 21. 11:42
이진탐색트리의 높이(깊이)
- 최악의 경우 높이 n
- 랜덤하게 만들면
- (균형 탐색 트리)-높이가 O(log2n)을 보장
경사이진트리 = 최악의 이진탐색트리
이진탐색트리의 중위순회
- 이진탐색트리를 중위순회하여 데이터를 출력하면 정렬된 데이터를 얻게 된다
인접행렬 (0) |
2022.12.21 |
이진트리 (0) |
2022.12.21 |
트리 (0) |
2022.12.16 |
hertaehoon
2022. 12. 21. 11:41
2022. 12. 21. 11:41
- 이진트리 = 루트 + 왼쪽 서브트리 + 오른쪽 서브트리
- 어떤 일반트리도 이진트리로 변환 가능하다
- 왼쪽에서 오른쪽 순서로 이동
최소노드의 개수
- 레벨에 하나씩만 노드가 있다는 가정하에
최소노드의 수는 h + 1
최대노드의 수
hertaehoon
2022. 12. 16. 02:57
2022. 12. 16. 02:57
Tree = root + subtrees
- 루트 노드(root node) : 부모 노드가 없는 중심이 되는 노르[트리에서 단 1개만 존재]
- ex) 1
- 서브 트리(sub tree) : 루트 노드를 제외한 나머지 노드
- ex ) 2, 3, ..., 9 , 10
- 리프 노드(leaf node) : 자식 노드를 가지고 있지 않은 트리의 말단에 있는 노드
- ex) 7, 8, 9, 10
- 부모 노드(parent node) : 어떤 노드와 간선으로 연결되어 있고 위에 있는 노드
- ex) 2번 노드는 4,5 번 노드의 부모 노드
- 자식 노드(children node) : 어떤 노드와 간선으로 연결되어 있고 그 아래에 있는 노드
- ex) 4,5번 노드의 부모는 2번 노드
- 형제 노드(sibling) : 같은 부모 노드를 가지는 노드
- ex) 8,9번 노드는 5번 노드를 부모로 하는 형제 노드
- 노드의 크기(size) : 자신을 포함한 모든 자식 노드들의 개수
- 노드의 차수(degree) : 어떤 노드가 가지고 있는 자식 노드의 개수
- ex) 4번 노드의 차수는 1
- 노드의 깊이(depth) : 루트 노드에서 어떤 노드까지 도달하기 위해 거치는 정점의 개수
ex) 6번 노드의 깊이는 2이다
- 트리의 레벨(level) : 트리의 각 층에 번호를 매긴 것이다. 루트의 레벨은 0이다.
- ex) 6번 노드의 레벨은 2다
- 트리의 높이(height) : 가장 깊이가 깊은 노드의 깊이
- ex) 트리의 높이는 3이다
- 교재에 따라서 root node의 Level이 1부터 시작하는 경우도 있다