<Udemy 스택 & 큐/이진 검색 트리> TIL-64

  오늘은 스택과 큐 형태의 자료 구조 그리고 이진 검색 트리 자료 구조를 공부했다. 스택은 후입선출 형태를 갖는 자료 구조를 말하고 큐는 선입선출 형태를 갖는 자료 구조를 말하는 추상적인 개념이다. 즉, 어떤 자료 구조이든 후입선출, 선입선출의 규칙을 지켜 활용하면 스택과 큐가 되는 것이다. 모던 자바스크립트 책을 공부할때 종종 등장했었던 개념이었으나 그 당시에는 정확한 개념을 이해하지 못했었다. 하지만 이번에 공부를 하고 나서는 스택과 큐 개념에 대해서 확실하게 이해하게 되었다. 배열에 데이터를 저장할때는 push & pop 메서들를 활용해서 스택 형태로 데이터를 활용하는게 좋겠다는 생각이 들었다. shift & unshift는 인덱스를 다시 설정해야 하므로 적합하지 않음

 

  앞서 공부했듯이 배열은 인덱스를 지니기 때문에 배열의 앞이나 중간에 데이터를 추가하거나 제거하는 경우에는 모든 인덱스가 새롭게 바뀌어야 하기 때문에 효율성이 떨어진다. 하지만 배열의 맨 뒤에 데이터를 추가하거나 삭제하는 경우에는 인덱스가 다시 설정되는 일은 없으니까 말이다. 반대로 단일 연결 리스트로 데이터를 저장하는 경우에는 push & shift 메서드를 활용한 큐를 활용하는 것이 더 효율적일 것 같다. 단일 연결 리스트의 경우 헤드의 다음 노드를 찾는 것은 용이하지만 테일의 직전 노드를 찾기 위해서는 헤드부터 시작해서 리스트의 모든 노드들을 거쳐가며 테일의 직전 노드를 찾고, 테일을 삭제하고 테일의 직전 노드를 다시 테일로 설정해주고 연결을 끊어주어야 하기 때문이다. 이처럼 스택과 큐는 자료 구조의 형태에 따라 더 효율적으로 데이터를 저장하고 꺼내는데 적합한 방식을 표현한 개념화한 것 같다.

 

  그리고 오늘은 새로운 자료 구조인 이진 검색 트리를 공부했다. 이진 검색 트리는 트리의 한 유형인 이진 트리의 한 유형이다. 트리와 이진 트리의 특성들을 그대로 가지고 추가적으로 새로운 규칙을 갖는 자료 구조이다. 이진 검색 트리의 경우에는 숫자로 이루어진 데이터를 활용할때 적합하다. 왼쪽에는 부모 노드보다 작은 값을 가지는 자식 노드는 부모 노드의 왼쪽으로 연결하고 반대로 부모 노드보다 큰 값을 가지는 자식 노드는 부모 노드의 오른쪽으로 연결을해서 데이터를 저장하는 방식이다. 조금 놀랐던 것은 '이렇게도 생각할 수 있구나? 난 왜 이런건 전혀 생각하지 못했지?' 라는 생각이 들었다. 단순히 자료를 어떻게 연결해서 저장해 놓는지에 따라 활용도와 효율성이 달라질 수 있다는것이 신기하기도 하고 한편으로는 그런 생각까지 하지 못한 내가 조금은 바보 같다는 생각이 들었다. 

 

2022.08.14 - [언어 공부 및 정리/자바스크립트 알고리즘 & 자료구조[Udemy강의]] - 15 스택 & 큐

15 스택 & 큐

2022.08.14 - [언어 공부 및 정리/자바스크립트 알고리즘 & 자료구조[Udemy강의]] - 16 이진 검색 트리

16 이진 검색 트리