본문 바로가기

CS 공부/자료구조11

AVL 트리 & Red-Black 트리 비교 RB 트리는 노드에 색깔을 부여하며 일정한 규칙 안에서 재구조화를 한다. 반대로 AVL 트리는 각 노드의 좌우 자식의 높이 차이를 비교하여 1이 초과할 때 재구조화를 한다. ★이때 알아야 할 것은 AVL 트리가 더 엄격하게 트리의 균형을 유지한다는 것이다. 따라서 삽입, 삭제 연산에서 RB 트리보다 AVL 트리가 더 많은 회전 작업을 수행하게 될 가능성이 있다. 하지만 이는 AVL 트리가 더 낮은 높이를 가질 수 있다는 뜻이기에 서로 장단점이 있다. AVL 트리 - 성질/삽입방법/활용 탄생 계기 이진탐색트리는 위 그림과 같이 한쪽으로 노드가 쏠릴 수가 있는 문제점이 있다. 10,9,8,7,6을 순서대로 삽입한다고 생각해보면 저런 형태의 트리가 만들어진다는 것을 알 수 있을 것이 hyolls100.tist.. 2023. 8. 11.
RB(Red-Black) 트리 - 성질/삽입방법/활용 탄생 계기 이진탐색트리는 위 그림과 같이 한쪽으로 노드가 쏠릴 수가 있는 문제점이 있다. 10,9,8,7,6을 순서대로 삽입한다고 생각해보면 저런 형태의 트리가 만들어진다는 것을 알 수 있을 것이다. 이런 트리를 편향 트리라 하는데 이러한 형태에서 특정 값을 찾으려면 O(N)의 시간이 필요하다. 예를 들어 6을 찾으려면 모든 노드를 탐색해야지 찾을 수 있다. 따라서 성능이 매우 나빠지게 된다. 이진 탐색 트리 (BST-Binary Search Tree) 이진 탐색 트리란? 이진탐색트리(Binary Search Tree; BST)는 정렬된 tree이다. 어느 노드를 선택하든 해당 노드의 왼쪽 서브 트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로만 이루어져 있고, 오 hyolls100.tistory.c.. 2023. 8. 11.
AVL 트리 - 성질/삽입방법/활용 탄생 계기 이진탐색트리는 위 그림과 같이 한쪽으로 노드가 쏠릴 수가 있는 문제점이 있다. 10,9,8,7,6을 순서대로 삽입한다고 생각해보면 저런 형태의 트리가 만들어진다는 것을 알 수 있을 것이다. 이런 트리를 편향 트리라 하는데 이러한 형태에서 특정 값을 찾으려면 O(N)의 시간이 필요하다. 예를 들어 6을 찾으려면 모든 노드를 탐색해야지 찾을 수 있다. 따라서 성능이 매우 나빠지게 된다. 이진 탐색 트리 (BST-Binary Search Tree) 이진 탐색 트리란? 이진탐색트리(Binary Search Tree; BST)는 정렬된 tree이다. 어느 노드를 선택하든 해당 노드의 왼쪽 서브 트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로만 이루어져 있고, 오 hyolls100.tistory.c.. 2023. 8. 10.
이진 탐색 트리 (BST-Binary Search Tree) 이진 탐색 트리란? 이진탐색트리(Binary Search Tree; BST)는 정렬된 tree이다. 어느 노드를 선택하든 해당 노드의 왼쪽 서브 트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로만 이루어져 있고, 오른쪽 서브 트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로만 이루어져 있는 이진 트리이다. 서브 트리도 재귀적으로 이러한 조건을 만족한다. 1. 각 노드에 중복되지 않는 키(key)가 있다. 2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다. 3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다. 4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다. 특징 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리.. 2023. 8. 10.
트리(Tree)의 순회 (전위/중위/후위 순회) 트리의 순회 트리의 순회는 중위(inorder) 순회, 전위(preorder) 순회, 후위 순회(postorder) 순회가 있다. ※ 여기서 설명할 때 L은 Left, V는 Visit, R은 Right를 의미한다. 즉, 왼쪽 서브 트리, 노드 방문, 오른쪽 서브 트리를 의미한다. 중위 순회(inorder traversal) 중위 순회는 LVR 탐색이 이루어진다. 즉, 왼쪽 서브 트리-루트 노드-오른쪽 서브 트리 탐색이 재귀적으로 이루어진다. 가장 먼저 루트 노드를 기준으로 왼쪽 서브 트리로의 탐색이 시작된다. 즉, 왼쪽 서브 트리에서 또다시 중위 순회가 재귀적으로 이루어진다. B노드가 루트 노드인 것처럼 되고, 왼쪽 서브 트리인 A노드로의 중위 탐색이 진행된다. 이후 A노드는 왼쪽 서브 트리(Left)가.. 2023. 8. 10.
여러 종류의 트리(Tree) 정리 (이진 트리, 전 이진 트리, 완전 이진 트리, 포화 이진 트리, 이진 탐색 트리) 트리의 개념 - 노드로 이루어진 자료구조로 스택이나 큐 같은 선형 구조가 아닌 비선형 자료구조이다. - 계층적 관계를 표현하는 자료구조이다. 트리의 특성 - 하나의 루트 노드를 갖는다. - 루트 노드는 0개 이상의 자식 노드를 갖는다. - 자식 노드 또한 0개 이상의 자식 노드를 갖는다. - 노드들과 노드들을 연결하는 간선(Edge)들로 구성되어 있다. - 사이클(Cycle)이 존재할 수 없다. 트리는 사이클이 없는 하나의 연결 그래프라고 할 수 있다. ★사이클이란? 시작 노드에서 출발해 다른 노드를 거쳐 다시 시작 노드로 돌아올 수 있는 구조를 말함한다. - 트리의 노드는 self-loop가 존재해서는 안된다. - N개의 노드를 갖는 트리는 항상 N-1개의 간선을 갖는다. - 모든 자식 노드는 한 개의.. 2023. 8. 9.

티스토리툴바