아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. AVL 트리 AVL 트리는 스스로 균형을 잡는 이진 탐색 트리이다. 왼쪽과 오른쪽의 높이 (자식의 수) 차이 = 균형인수(Balance factor, BF)가 항상 1보다 작거나 같아야 한다. 즉, 왼쪽과 오른쪽의 높이 차이가 0, -1, 1 외의 다른 수가 나와서는 안된다. 예제 1) 예제 2) AVL 트리 : 노드 왼, 오른쪽 포인터 + 부모 노드 포인터를 선언한다. class Node{ T data;// 노드에 저장할 데이터 Node left; Node right; Node parent; // 생성자 public Node(T obj){ data = obj; parent = left = right = null; } add 메소드, 재귀 add 트..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 회전 균형(balance) 잡힌 트리를 만들기 위해 트리의 노드 위치를 바꾸는 과정이다. 위처럼 마치 연결리스트와 같이 한 방향으로 나열된 트리는 구조 자체는 문제없이 가능하나 탐색에 걸리는 시간 복잡도가 O(n)이 되어버린다. 본래 일반적으로 균형이 잡힌 이진트리에서 요소를 탐색하는 시간 복잡도가 O(log n)인 것과 대조하여 위와 같은 트리는 매우 비효율적이다. 따라서 회전을 통해 트리를 균형 있게 만들 수 있다. 트리에서 부모 노드보다 작은 데이터가 왼쪽 자식 노드에 와야 하고, 더 큰 데이터가 오른쪽 자식 노드에 와야하므로 트리가 한 쪽으로 치우친 경우 다음과 같이 조부모 노드, 부모 노드, 자식 노드의 크기 관계에 따라 우측 회전, 혹은 ..
공든 탑은 무너지지 않나보다 트리 파트를 공부하면서, 정보처리기사 공부를 했던 경험이 많은 도움을 주었다. 당시에는 표기법이나 순회방식을 외우면서도 단지 시험을 합격하기 위한 단기적인 지식을 공부할 뿐이라고 생각했었는데, 트리에 대해 좀 더 본격적으로 알아보며 다시 살펴보니 자료구조적으로 맥락을 이해할 수 있었다. 시험을 준비할 때 꽤나 보았던 이야기가 정처기는 별로 중요하지 않다, SI가 아니면 굳이 취득할 필요가 없다는 것이었다. 그러나 전공자가 아닌 이상 가뜩이나 보여질 공인된 자격이 없는 상황에서 뭐라도 있으면 낫지 않을까, 스스로도 조금 더 확신을 가질 수 있지 않을까 싶어 공부했다. 아직 실기 시험도 봐야하지만 잘한 결정이라고 생각한다. 본 스터디 말고도 학원에서 배우는 것들 역시 정처기 필기..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 노드 클래스 트리에서는 부모 노드보다 작은 데이터가 왼쪽 자식 노드에 위치하고 부모보다 큰 데이터가 오른쪽 자식노드에 위치해야 한다. 어떤 수를 찾으려고 하면 부모보다 작으면 왼쪽으로, 크면 오른쪽으로 이동하면 된다. 전체 데이터의 반은 무시하고 log n의 복잡도를 가진다. 연결리스트에서 next 포인터를 가졌듯, 트리에서는 left, right 포인터를 갖도록 만든다. class Node { E data; Node left, right; public Node(E obj){ this.data = obj; left=right=null; } } 재귀 함수: add 트리에 새로운 데이터를 add로 추가하기 (재귀: 함수에서 자기 자신을 다시 호출해 작업..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 완전 이진 트리(Complete binary tree) 마지막 줄을 제외한 모든 잎이 아닌 노드가 2개의 자식 노드를 가지고 있고, 마지막 줄은 왼쪽에서 오른쪽 순서로 채워져 있는 트리이다. 정 이진 트리(Full binary tree) 모든 잎이 아닌 노드가 2개의 자식 노드를 가지고 있고, 모든 잎이 같은 레벨에 있는 트리이다. (모든 노드가 0 개 또는 2개의 자식 노드만을 가짐) 트리 순회 전위 순회 (Pre order traversal) 1) 루트 노드에서 시작하여 2) 왼쪽 자식 노드에 갔다가 3) 오른쪽 자식 노드로 가는 순회 방법. 다른 모든 노드를 지나기 전에 루트 노드를 방문하기 때문에 전위(Pre order) 순회라고 한다. 중위..
한달 전을 돌아보자 정신 차려보니 벌써 스터디를 시작한지 한달이 지났다. 얼핏 한 달간 무얼했나 싶지만 잘 돌이켜보면 당시와 비교한 나는 확실히 많은 점이 달라졌다. 아무것도 모른 채 시작해 강의에서 다루는 많은 부분을 알아듣기 어려웠던 그 때에 비하면, 학원 수업과 공부를 통해 자바에 대해 전반적으로 약간은 알게된 지금은 강의를 알아듣거나 코드를 하나하나 살펴보는 일이 비교적으로 훨씬 수월해졌다. 물론 아직까지도 기초적인 부분에서 헤매기도 하지만... this가 무엇인지도 몰랐던 때에 비하면 감개무량이라고 볼 수 있지 않을까? 첫 주의 스터디 회고를 오랜만에 다시 읽어보았는데, 간단한 예제 코드를 구성요소 하나하나 뜯어 구글링하지 않고도 이해할 수 있을 만큼은 자라고 싶다고 적혀있었다. 얼추 이런 수준..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 트리 순회 중위 순회 - 왼쪽, 루트, 오른쪽 순서로 순회 전위 순회 - 루트, 왼쪽, 오른쪽 순서로 순회 후위 순회 - 왼쪽, 오른쪽, 루트 순서로 순회 레벨 순회 - 레벨 순서대로 순회 TrickelUp 완전이진트리에서 레벨 순회식 노드의 위치는 다음과 같은 성질을 가진다. children - 2 * parent + 1 // 또는 // 2 * parent + 2 parent - floor(내림)( (child-1) / 2 ) 이진 힙을 코드로 구현하기 위해서는 배열(0~..)을 만들어 인덱스를 노드 위치로 하여 이러한 규칙을 사용할 수 있다. int lastposition; // 배열에서 어디까지 요소를 넣었는지 기록: 힙이 시작점에서 얼마나 떨..
