본문 바로가기
728x90

Data Structure5

[자료구조] Binary Search Tree(BST, 이진탐색트리) 정의와 python 구현 [자료구조] Binary Search Tree(BST, 이진 탐색 트리) 정의와 python 구현 살펴볼 주요 개념: 더보기 - Binary Search Tree의 정의 - Binary Search Tree 구현 방법 1. Binary Search Tree의 정의 이진탐색 트리는 탐색에 효율적인 트리이다. 이진트리의 규칙은 다음과 같다. 각 노드의 왼쪽 subtree의 값은 노드의 key값 보다 작거나 같아야 하고, 오른쪽 subtree의 값은 노드의 key값 보다 커야 한다. 12의 자리에 1이 올 수는 없다. 왜냐하면, 1이 부모 노드인 13보다 작은 수 이더라도, 10의 오른쪽 subtree이기 때문에 10보다 큰 수가 와야 하기 때문이다. 즉, 12 노드 자리에는 10~13까지만 key값으로 사용.. 2022. 5. 15.
[자료구조] Heap 기초 개념 알아보기(python) [자료구조] Heap 기초 개념 알아보기(python) 살펴볼 주요 개념: 더보기 - 힙이란? - 힙을 충족하는 트리 형태 - 힙 직접 구현 1. 힙이란? 힙 성질(heap property)을 만족하는 이진트리(Binary Tree)이다. * 힙 성질 - 모양성질 : 레벨 별로 모든 노드가 꽉 차있고, 마지막 레벨의 노드만 왼쪽에서부터 차있는 형태 - heap 성질 : 모든 부모노드의 key값이 자식노드의 key값보다 작지 않다. 힙 성질을 만족하는 트리를 리스트화 해서 표현하면 다음과 같다. A = [15, 12, 6, 11, 10, 2, 3, 1, 5] 루트 노드에는 리스트에서 가장 큰 값이다. 힙은 insert와 remove(최대값 삭제), maxHeapify 연산을 지원한다.(max heap) 각.. 2022. 5. 15.
[자료구조] Tree 기본 개념 알아보기 [자료구조] Tree 기본 개념 알아보기 살펴볼 주요 개념: 더보기 - 트리의 개념 - 트리의 표현법(python) 1. 트리의 개념 트리(tree)는 부모 - 자식 간의 관계의 노드로 구성되어 있다. 한 방향 연결리스트와 비슷하다. 한 방향 연결리스트의 경우, 한 부모에 한 자식 밖에 없는 트리구조인 것이다. 트리는 두 개 이상의 자식 노드를 가질 수 있다. 세 개 이상의 자식을 가지는 2, 3, 4 트리와 같은 것도 존재한다. 각각의 노드에는 key값이 들어가 있다. 각각의 용어 설명을 해보자면 다음과 같다. 루트 노드 : 맨 꼭대기에 위치한 조상과 같은 노드 링크 or 에지 : 부모 노드와 자식 노드 사이를 이어주는 선 리프 노드 : 더 이상의 자식 노드가 없는 노드 형제 노드 : level이 같고.. 2022. 5. 15.
[자료구조] Double Linked List(양 방향 연결리스트) python class 구현하기 [자료구조] Double Linked List(양 방향 연결리스트) python class 구현하기 살펴볼 주요 개념: 더보기 - 양 방향 연결리스트의 특징 - 양 방향 연결리스트 클래스 구현(Node, Double Linked List) 1. 양 방향 연결리스트의 특징 양 방향 연결리스트는 이중 연결 리스트, 원형 연결 리스트로 나누어 진다. 여기서는 원형 연결 리스트만을 살펴볼 것이다. 양 방향 연결리스트는 tail 노드를 알지 못해도 순차적인 탐색 연산이 필요 없다. 삽입될 앞 뒤의 노드만 알고 있다면, 상수 시간 내에 삽입 또는 삭제 연산이 가능하다. 원형 연결리스트의 맨 앞 노드는 '더미 노드'이다. 원형 연결리스트의 순서를 정확하게 매길 수 없는 특징 때문에, head 노드를 정확하게 설정할 .. 2022. 5. 14.
[자료구조] Linked List(연결리스트)의 특징 [자료구조] 살펴볼 주요 개념: 더보기 - Linked List의 정의 - 한 방향 연결리스트 vs 양 방향 연결리스트 1. Linked List(연결리스트)의 정의 연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. 여기서 하나의 박스가 노드라고 보면된다. 박스의 옆부분이 링크 부분이며 각 노드 안에는 key값 또는 key값 value값 쌍이 들어간다. 다음 노드를 계속 가리키면서 하나의 줄줄이 소세지 같은 모습을 한다. 연결 리스트의 종류로는 한 방향 연결 리스트, 양 방향.. 2022. 5. 14.
728x90

티스토리툴바