AVL 트리는 값을 추가하거나 삭제할 때 스스로 균형을 잡는 이진 탐색 트리이다. 이 트리는 두 자식 트리의 높이가 항상 최대 1만큼 차이나야 하며 차이가 1보다 커지면 스스로 트리를 회전하여 균형을 잡으며 삽입과 삭제는 한 번 이상의 트리 회전을 통해 균형을 잡을 수 있다. 검색, 삽입, 삭제는 모두 평균과 최악의 경우 O(log n)의 시간 복잡도가 걸린다. 회전 트리의 자식 노드 간 차수의 차가 1보다 커지게 되면 균형이 맞지 않다고 보고 트리를 재구성하는데 이 작업을 회전이라 한다. 회전하는 모양에 따라서 LL 회전, LR 회전, RR 회전, RL 회전이라고 할 수 있다. 각 회전을 구분하는 방법은 회전하는 노드가 왼쪽 자식 노드, 왼쪽 자식 노드이면 LL, 오른쪽 자식 노드, 오른쪽 자식 노드이..
이진 탐색 트리(Binary Search Tree)는 다음과 같은 속성을 가진다. 1. 노드의 왼쪽 서브 트리는 노드의 값보다 작은 값으로 이루어진다. 2. 노드의 오른쪽 서브 트리는 노드의 값보다 큰 값으로 이루어진다. 3. 노드의 좌우 서브 트리는 모두 이진 탐색 트리여야 한다. 4. 중복되는 노드가 없어야 한다. 이진 탐색 트리의 시간 복잡도는 최악일 경우 O(n)이며 최선일 경우 O(log n)이다. 최악의 경우 5 / 4 / 3 / 2 / 1 최선의 경우 10 / ＼ 5 15 / ＼ / ＼ 2 7 12 17 삽입 1. 검색을 수행한다. 2. 검색 중 중복되는 노드가 있는지 확인 3. 검색 중 하위 노드에 노드가 없는 경우 노드를 삽입 삭제 삭제하려는 노드의 자식 수에 따라 방식이 달라진다. 1...
여러 개의 값 중 가장 크거나 작은 값을 빠르게 찾기 위한 완전 이진 트리 형식의 트리로 부모 노드의 값이 항상 자식 노드의 값보다 크거나 작도록 만들어 대소관계를 가지도록 만든다. 따라서 루트 노드는 항상 가장 크거나 가장 작은 값을 가지게되며 최댓값(또는 최솟값)을 바로 찾을 수 있게 된다.( O(1) ) * 루트 노드가 가장 클 때는 최대힙, 가장 작을 때는 최소힙이라고 한다. 노드 간 값의 대소관계는 오로지 부모 노드와 자식 노드 사이에만 성립하며 형제 노드 사이에서는 관계없다. 즉 아래와 같은 트리가 있으면 A와 B(혹은 C) 간에는 대소관계가 성립되어야 하며 B와 C 간에는 성립되지 않아도 된다. A / ＼ B C 노드 추가 방법 트리의 가장 마지막에 노드 추가 추가한 노드와 추가한 노드의 부..
Stack : 먼저 들어온게 나중에 나간다. (후입선출, Last In First Out, LIFO) - 예로 물건을 쌓아올린 것으로 생각하면 된다. 쌓아올린 물건들 중 원하는 물건을 꺼내기위해서는 가장 마지막에 올린 물건부터 차례대로 꺼내야 하기 때문이다. Queue : 먼저 들어온게 먼저 나간다. (선입선출, First In First Out, FIFO) - 예로 사람들이 줄을 서있는것을 생각하면 된다. 물론 새치기가 없어야 된다는 조건이 있지만 줄을 서있다는 것은 먼저온 사람이 먼저 일을 처리한 후 먼저 가기 때문이다.