트리
-
코딩 테스트 - 트리(Tree)의 개념과 문제Coding Test/Coding Test 문제 추천 2021. 9. 26. 14:21
트리(Tree) 트리란? ㆍ 사이클이 존재하지 않는 특수한 형태의 그래프이다. 트리 문제 난이도(하) ㆍ 백준 11725번 : 트리의 부모 찾기 (🥈 실버 2 티어) ㆍ 백준 5639번 : 이진 검색 트리 (🥈 실버 1 티어) ㆍ 백준 15900번 : 나무 탈출 (🥈 실버 1 티어) ㆍ 백준 20364번 : 부동산 다툼 (🥈 실버 2 티어) 난이도(중) ㆍ 백준 3584번 : 가장 가까운 공통 조상 (🥇 골드 4 티어) ㆍ 백준 1240번 : 노드사이의 거리 (🥇 골드 4 티어) ㆍ 백준 11437번 : LCA (🥇 골드 3 티어) ㆍ 백준 9489번 : 사촌 (🥇 골드 4 티어) ㆍ 백준 1068번 : 트리 (🥇 골드 5 티어) ㆍ 백준 15681번 : 트리와 쿼리 (🥇 골드 5 티어) ㆍ 백준 142..
-
AVL 트리Computer Science/Data Structure 2021. 9. 24. 16:23
AVL 트리의 정의 ㆍ 균형 잡힌 높이의 이진 검색 트리이다. ㆍ 두 개의 자식 노드들 간에 깊이 차이가 1 이하인 트리이다. AVL 트리의 장점 ㆍ 트리의 검색 연산이 항상 O(log n)으로 균형 잡혀 있다. ㆍ 트리의 삭제 연산 또한 O(log n)으로 균형 잡혀 있다. AVL 트리의 단점 ㆍ 삽입 연산이 이루어질 때 트리의 재구성 시간이 소요된다. ㆍ 이진 검색 트리보다 구현의 난이도가 높다. 구현 방법 relink() 메서드 protected void relink(Node parent, Node child, boolean makeLeft) { if (child != null) child.parent = parent; if (makeLeft) parent.left = child; else pare..
-
이진 검색 트리Computer Science/Data Structure 2021. 9. 24. 16:04
이진 검색 트리의 정의 ㆍ 각 노드는 (키, 값)의 쌍을 저장하며, 서로 다른 노드의 키는 다르다. ㆍ 왼쪽 서브 트리에 저장된 노드의 키보다는 크다. ㆍ 오른쪽 서브 트리에 저장된 노드의 키보다는 작다. 이진 검색 트리의 장점 ㆍ 심볼 테이블을 정렬된 순서로 유지할 필요 없다. ㆍ 새로 삽입되는 노드는 항상 리프 노드에 위치한다. 이진 검색 트리의 단점 ㆍ 균형 트리를 보장하지 않는다. ㆍ 감색 시 많은 시간이 소요된다. 구현 방법 노드의 구성 class Node { K key; V value; Node left, right; int N; int aux; Node parent; public Node(K key, V value) { this.key = key; this.value = value; this..