본문 바로가기

CS 공부44

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.
힙(Heap)이란? 특징 - 완전이진트리의 일종이다. - 여러 값들 중 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 자료구조이다. - 중복된 값을 허용한다. - Max Heap은 가장 큰 값을 빠르게 찾기 위한 것이고, Min Heap은 가장 작은 값을 빠르게 찾기 위한 것이다. ※ 완전 이진 트리란? 여러 종류의 트리(Tree) 정리 (이진 트리, 전 이진 트리, 완전 이진 트리, 포화 이진 트리, 이진 탐 트리의 개념 - 노드로 이루어진 자료구조로 스택이나 큐 같은 선형 구조가 아닌 비선형 자료구조임. - 계층적 관계를 표현하는 자료구조임. 트리의 특성 - 하나의 루트 노드를 갖음. - 루트 노드 hyolls100.tistory.com Map Heap - Max Heap은 부모 노드의 키 값이 자식 노드의 키 값보다 크거.. 2023. 8. 9.
큐(Queue) 두 개로 스택(Stack) 구현하기 Push - queue1의 enqueue()를 통하여 데이터를 저장 Pop a. queue1의 데이터 갯수가 1개 이하로 남을 때까지 dequeue를 한 후, 해당 데이터를 queue2에 enqueue()하여 옮김. 이 결과로 가장 나중에 들어온 데이터를 제외한 모든 데이터가 queue2로 옮겨짐. b. queue1에 남아있는 하나의 데이터를 dequeue()하여 가장 최근에 저장된 데이터를 반환(LIFO) c. ★ 다음에 진행될 pop()을 마찬가지로 진행하기 위해 queue1과 queue2를 swap 코드 작성 import queue class Stack(object): def __init__(self): self.q1 = queue.Queue() self.q2 = queue.Queue() def p.. 2023. 8. 8.

티스토리툴바