코딩(Coding)/자료구조
-
[자료구조] 균형트리 - AVL Tree(Adelson-Velskii-Landis Tree)코딩(Coding)/자료구조 2021. 1. 14. 11:39
AVL Tree(Adelson-Velskii-Landis Tree) 개념 AVL Tree는 기존의 BST에서 편향된 모양을 최대한 억제한 Tree이다. 음... 그림으로 말하자면,,, 위 그림처럼 입력이 10,20,30,40,50 순으로 입력되었다고 하자 내가 50Node를 탐색하려면 총 4번의 탐색이 필요하다 결국, 저렇게 편향된 BST는 그냥 선형 자료구조와 다름이 없다... 한 마디로 효율이 떨어진다는 것이다. 따라서 저러한 편향된 모양을 최대한 억제한 것이 바로 AVL이다. 균형인수(Balancing-Factor) AVL은 그렇다면 규형을 어떤식으로 맞춰야 하는가... 바로 균형인수(Balancing-Factor)라는 새로운 자원을 통해 균형을 맞춘다. 균형인수는 특정 노드의 왼쪽 서브트리와 오른..
-
[자료구조] BST - 이진탐색 트리(Binary Search Tree)코딩(Coding)/자료구조 2021. 1. 7. 11:04
이진 탐색 트리 BST(Binary Search Tree) BST는 각각의 Node가 2개의 하위 노드를 가진 모양의 Tree이다. 단 BST는 정렬된 상태로 Node가 저장된다. 즉 순서가 있다는 것이다. 쉽게 이야기 하자면 특정 노드가 있을때 그 노드의 왼쪽 하위 노드는 해당 노드보다 data값이 작아야하며 반대로 오른쪽 하위 노드는 data값이 해당 노드보다 커야한다. 그림을 통해 확인해 보면 위 그림을 확인해 보자 root노드인 50의 왼쪽 node의 data 값은 30이고 오른쪽 노드의 data값은 90이다. 해당 규칙을 지키며 tree를 구성한 것이 BST이다. 설계 그렇다면 바로 구현을 시작해보자 Node 설계 우선은 Tree의 각각의 노드를 설계할 것이다. 그림에서 처럼 좌우의 하위 Nod..
-
[자료구조] Tree 개념/정의코딩(Coding)/자료구조 2021. 1. 5. 13:26
Tree 트리(Tree)는 하나 이상의 노드들로 구성된 유한집합이다. 트리는 가장 최상위에 존재하는 Root 노드와 그 노드서부터 내려가는 하위노드들의 구성으로 표현된다. 아래 그림을 보자 그림처럼 Tree를 표현하면 위 그림같이 될 것이다. Root노드인 A는 하위 노드인 B,C,D노드가 있고 각각의 하위노드들은 또 자신들만의 하위노드들이 있다. 여기서 A에 대해 subTree는 B노드와 그의 하위 노드들과 C,D노드와 각각의 하위노드들이 될 것이다. Tree 설계 그렇다면 Tree는 어떻게 설계하면 좋을까? 생각해보자 일단 노드 A는 data와 sub-Node를 저장할 Node변수 3개가 필요할 것이다. 그렇다면 아래 그림 처럼 Tree의 노드구조를 설명할 수 있겠다. 자 그럼 문제는 다음이다. 가령..
-
[자료구조] Doubly Linked List코딩(Coding)/자료구조 2020. 12. 31. 13:40
Doubly Linked List 지난 포스팅에서 언급했던 Singly Linked List을 보완하여 정의된 Doubly Linked List이다. 단일 링크드 리스트와 다르게 한쪽 방향으로만 pointer가 있는 것이 아닌 좌우로 pointer가 존재한다. 좌우로 pointer를 표현했기 때문에 좀던 자유롭게 Node에 접근할 수 있다. 아래는 지난 글인 Single Linked List이다. jsy-coding-blog.tistory.com/9 [자료구조] Single Linked List Single Linked List Linked List는 많은 양의 자료이동이 필요할때 사용하는 자료구조이다. Linked List는 Node라는 단일된 객체들의 연결로 표현한다. 오늘 포스팅에서 소개할 Sing..
-
[자료구조] Single Linked List코딩(Coding)/자료구조 2020. 12. 28. 12:05
Single Linked List Linked List는 많은 양의 자료이동이 필요할때 사용하는 자료구조이다. Linked List는 Node라는 단일된 객체들의 연결로 표현한다. 오늘 포스팅에서 소개할 Single Linked List는 이러한 연결이 한개로 순차적인 표현을 한다. Single Linked List 설계 단일 연결 리스트의 설계를 해보자 Node 설계 Node는 데이터가 담기는 핵심적인 요소이다. 일반적인 배열로 생각하면 [1,2,4]같이 있다면 "1", "2"같은 단일된 요소 해당 인덱스의 요소를 가리키는 것이다. 그렇다면 Node는 데이터를 저장해야하는 Data변수가 있어야 된다. 그리고 연결을 표현해야함으로 다음 Node로 가는 Pointer가 있어야겠다. 그림으로 표현하면 다음 ..
-
[자료구조] Stack과 Queue코딩(Coding)/자료구조 2020. 12. 23. 15:51
Stack과 Queue Stack 스택(Stack)은 기본적인 자료구조로 쌓아올린다는 개념으로 시작하며 접근방법은 언제나 목록의 끝에서만 일어난다. 위 그림처럼 스택은 데이터를 아래서부터 쌓아올리고 데이터들을 다시 불러올때는 가장 최근의 데이터가 호출된다. 이를 선입후출(LIFO - Last in First Out)이라고 한다. 해당 자료구조를 구현하기위해 정의해야할 메소드를 아래에 적어보겠다. push(data): 데이터를 저장할 때, 호출되는 메소드 pop(): 가장 위에있는 데이터를 반환하고 그 값을 삭제하는 메소드 getTop(): 가장 위에있는 데이터를 반환하는 메소드 isEmpty(): stack이 비어있는지를 확인하는 메소드 isFull(): stack이 꽉차있는지를 확인하는 메소드 prin..