트리(Tree) 자료구조를 공부하다 보면 반드시 마주치게 되는 개념이 바로 노드(Node)입니다. 트리를 구성하는 모든 요소가 노드이기 때문에, 이진 트리(Binary Tree)를 정의하기 전에 먼저 노드가 무엇인지 명확히 이해해야 합니다.노드의 기본 구조노드는 크게 세 가지 속성(property)으로 정의할 수 있습니다.left — 현재 노드의 왼쪽 자식 노드에 대한 참조(reference)를 저장합니다.right — 현재 노드의 오른쪽 자식 노드에 대한 참조를 저장합니다.data — 해당 노드에 저장하고자 하는 데이터를 담습니다

이번 글에서는 자바스크립트를 사용해 이진 탐색 트리(Binary Search Tree)를 어떻게 생성하고 표현하는지 알아보겠습니다. 가장 먼저 해야 할 일은 BinarySearchTree 클래스를 만들고, 그 안에 노드(Node) 속성을 정의하는 것입니다.예제 코드class BinarySearchTree { constructor() { // 루트(root) 요소를 null로 초기화합니다. this.root = null; } } BinarySearchTree.prototype.Node =

새로 생성된 이진 탐색 트리(Binary Search Tree)에 처음으로 값을 삽입하면 해당 노드가 루트(root)에 위치하게 됩니다. 이후의 삽입 연산은 이진 탐색 트리의 기본 성질에 따라 수행됩니다. 즉, 왼쪽 자식 노드는 부모보다 작은 값, 오른쪽 자식 노드는 부모보다 큰 값을 가지도록 배치됩니다.이번 글에서는 이 알고리즘을 코드로 어떻게 구현할 수 있는지 살펴보겠습니다.반복문을 사용한 삽입 구현insertIter(data) { let node = new this.Node(data); // 트리가 비어 있는지

이진 탐색 트리(Binary Search Tree, BST)는 각 노드를 기준으로 왼쪽 자식에는 더 작은 값, 오른쪽 자식에는 더 큰 값이 위치한다는 핵심 속성을 가지고 있습니다. 이 속성을 활용하면 트리 안에서 원하는 값을 매우 효율적으로 찾을 수 있습니다. 먼저 반복문(iteration)을 사용하는 검색 구현부터 살펴보겠습니다.반복문을 사용한 검색 구현searchIter(data) { let currNode = this.root; while (currNode !== null) { if (currNod

이진 탐색 트리(Binary Search Tree, BST)는 왼쪽 자식 노드가 항상 부모 노드보다 작다는 핵심 성질을 가지고 있습니다. 이 성질을 활용하면 루트에서 출발해 왼쪽 자식을 따라 계속 이동하고, 더 이상 왼쪽 자식이 없는 노드에 도달했을 때 그 노드의 값이 곧 트리 전체에서 가장 작은 값임을 알 수 있습니다.이제 이 로직을 실제 코드로 구현해 보겠습니다. 앞으로 진행되는 예제에서는 함수를 반복(iterative) 방식 또는 재귀(recursive) 방식 중 한 가지로만 구현합니다. 여기서는 반복문을 사용하는 방식으로 작

딕셔너리(Map) 객체를 다루다 보면 전체 데이터가 아니라 키(key)만 필요한 경우가 종종 있습니다. 예를 들어, 저장된 모든 키 목록을 배열 형태로 가져와 반복 처리하거나 화면에 출력해야 할 때가 그렇습니다. 자바스크립트에서는 Object.keys() 메소드를 사용하면 객체의 속성(키)들을 아주 간단하게 추출할 수 있습니다.이번 글에서는 커스텀 맵(MyMap) 클래스와 ES6의 Map 객체에서 키와 값을 조회하는 방법을 예제 코드와 함께 살펴보겠습니다.1. keys() 메소드로 키 목록 가져오기커스텀 맵 클래스 내부에 keys(

자바스크립트에서 사전(Dictionary) 혹은 맵(Map)에 저장된 모든 데이터를 한 번에 삭제하고 싶을 때는 clear() 함수를 활용하면 됩니다. 이번 글에서는 직접 만든 맵 클래스에 clear() 함수를 구현하는 방법과, ES6에서 기본 제공되는 Map 객체의 clear 메서드 사용법을 예제와 함께 살펴보겠습니다.직접 구현한 맵에서 clear() 함수 만들기clear() 함수는 매우 간단합니다. 내부 컨테이너(container)를 빈 객체로 다시 할당하기만 하면, 기존에 저장된 모든 키-값 쌍이 한꺼번에 사라집니다.clear

이번 글에서는 클래스 내부에 forEach 함수를 직접 구현하고, 모든 키-값 쌍에 대해 호출할 수 있는 콜백(callback)을 인자로 받는 방법을 살펴보겠습니다. 이러한 함수는 다음과 같이 구현할 수 있습니다.예제forEach(callback) {     for (let prop in this.container) {         // callback(key, value) 형태로 콜백 호출    

사전(Dictionary) 클래스란?사전(Dictionary), 또는 맵(Map)은 데이터를 키(Key)-값(Value) 쌍의 형태로 저장하는 대표적인 자료구조입니다. 배열과 달리 인덱스가 아닌 고유한 키를 통해 값에 바로 접근할 수 있어, 검색·삽입·삭제 작업을 효율적으로 처리할 수 있습니다.자바스크립트는 ES6부터 내장 Map 객체를 제공하지만, 이를 직접 구현해 보면 해시 기반 자료구조의 동작 원리를 깊이 있게 이해할 수 있습니다. 아래는 일반 객체({})를 내부 저장소로 활용해 사전 자료구조를 구현한 MyMap 클래스입니다.

해시 테이블(Hash Table)은 데이터를 연관(associative) 방식으로 저장하는 자료구조입니다. 해시 테이블에서 데이터는 배열 형태로 저장되며, 각 데이터 값은 고유한 인덱스 값을 가집니다. 따라서 원하는 데이터의 인덱스만 알고 있다면 데이터에 매우 빠르게 접근할 수 있습니다.이러한 특성 덕분에 해시 테이블은 데이터 크기와 무관하게 삽입과 검색 연산이 매우 빠른 자료구조가 됩니다. 해시 테이블은 배열을 저장 매체로 사용하고, 해시 기법을 활용해 요소를 삽입하거나 찾아야 할 위치의 인덱스를 생성합니다.해싱(Hashing)이

이제 해시 테이블의 각 메서드를 정의하는 데 사용할 간단한 클래스를 만들어 보겠습니다. 해시 테이블 데이터를 담을 컨테이너 객체를 생성하고, 테이블의 내용을 출력하는 display 함수도 함께 작성합니다. 충돌(collision) 해결 방식으로는 체이닝(chaining) 기법을 사용합니다.display 함수는 테이블의 각 엔트리(해시된 값)를 순회하며, 해당 위치에 연결된 모든 키-값 쌍을 출력하는 역할을 합니다.예제키-값 쌍을 저장하기 위해 프로토타입에 새로운 클래스(KVPair)도 추가합니다.class HashTable {

충돌(Collision) 해결이 핵심이다해시 테이블에 요소를 추가할 때 가장 중요하게 고려해야 할 부분은 바로 충돌(collision) 해결입니다. 서로 다른 키가 동일한 해시 값을 가질 수 있기 때문인데요, 이번 글에서는 대표적인 충돌 해결 기법인 체이닝(chaining) 방식을 사용하겠습니다.체이닝 외에도 개방 주소법(open addressing) 등 다양한 충돌 해결 알고리즘이 존재합니다. 관심 있는 분들은 아래 위키백과 문서에서 자세히 살펴볼 수 있습니다.참고: Hash Table - Collision Resolution (

해시 테이블에서 특정 요소를 검색하는 기능은 사실 앞서 구현한 put 메서드 안에 이미 상당 부분 포함되어 있습니다. 이번에는 해당 로직을 분리하여 get 메서드로 독립적으로 살펴보겠습니다.get 메서드 구현 예제get(key) { let hashCode = hash(key); for(let i = 0; i < this.container[hashCode].length; i ++) { // 체인(연결 리스트)에서 해당 키를 가진 요소 탐색 if(this.container[hashCode

해시 테이블(hash table)에서 요소를 제거하는 작업은 의외로 간단합니다. 먼저 주어진 키(key)에 해당하는 요소를 찾은 뒤, 배열에서 요소를 제자리(in-place)로 삭제해 주는 splice() 함수를 호출하기만 하면 됩니다. remove 메서드 구현 해시 테이블은 서로 다른 키가 같은 해시 코드를 가질 수 있기 때문에, 하나의 버킷(bucket)에 여러 요소가 체인(chain) 형태로 저장될 수 있습니다. 따라서 삭제 시에는 해당 체인 안에서 키가 일치하는 요소를 직접 찾아 제거해야 합니다. remove(key) {

이제 해시 테이블에 저장된 모든 키-값(key-value) 쌍을 순회하면서 각 값에 대해 콜백(callback) 함수를 실행할 수 있는 forEach 함수를 만들어 보겠습니다.구현 방법은 매우 간단합니다. 내부 컨테이너(container)에 있는 각 체인(chain, 버킷)을 차례대로 반복한 뒤, 체인 안의 각 요소에 대해 키와 값을 인수로 전달하며 콜백을 호출해 주면 됩니다.forEach 메서드 구현 예제forEach(callback) { // 컨테이너의 각 체인(버킷)을 순회 this.container.forEach(el

세트(Set) 비우기: clear() 메서드커스텀 세트(Set) 자료구조를 구현할 때, 저장된 모든 요소를 한 번에 제거하는 clear() 메서드는 매우 간단하게 만들 수 있습니다. 핵심 아이디어는 기존의 container 객체를 하나씩 순회하며 삭제하는 대신, 새로운 빈 객체를 통째로 재할당하는 것입니다. 이렇게 하면 이전에 저장된 모든 데이터가 사라지고 세트가 깨끗한 상태가 됩니다.clear() 메서드 구현clear() { this.container = {}; }this.container = {} 코드는 컨테이너 변수를 새로

직접 구현한 집합(Set) 클래스에서는 각 요소에 대해 특정 작업을 수행할 수 있도록 forEach 함수를 만들 수 있습니다. 이 함수는 콜백(callback)을 매개변수로 받아, 집합에 포함된 모든 요소마다 해당 콜백을 호출하는 방식으로 동작합니다.아래 예제를 통해 이러한 함수를 어떻게 구현하는지 살펴보겠습니다.구현 예제forEach(callback) {     for (let prop in this.container) {       &nbs

두 개의 집합을 더하는 연산을 합집합(Union)이라고 합니다. 합집합을 구하려면 한 집합의 모든 요소를 다른 집합에 추가하면서 중복 여부를 확인해야 합니다. 다행히 앞서 이미 구현한 메서드들을 활용하면 이 기능을 손쉽게 만들 수 있습니다.이 함수는 정적(static) 함수로 구현하는 것이 좋습니다. 기존 집합을 변경(mutation)하는 대신 새로운 집합을 생성하여 반환하기 때문입니다. 먼저 전달된 객체가 실제로 MySet 클래스의 인스턴스인지 검사하는 과정이 필요합니다.구현 예제 newSet.add(elem)); retu

두 집합의 차집합(difference)이란, 빼려는 집합(s2)에 포함된 모든 원소를 원본 집합(s1)에서 제거한 결과를 의미합니다. 따라서 두 번째 집합을 순회하면서 해당 원소들을 첫 번째 집합에서 하나씩 삭제하는 방식으로 차집합을 간단히 구현할 수 있습니다.커스텀 Set 클래스에서 차집합 구현하기아래는 자체 제작한 MySet 클래스에 정적(static) 메서드 형태로 차집합 기능을 추가한 예제입니다.static difference(s1, s2) { if (!(s1 instanceof MySet) || !(s2 instance

셋(Set)은 수학의 집합 개념을 프로그래밍으로 옮긴 자료구조로, 중복을 허용하지 않고 고유한 값만 저장한다는 점이 가장 큰 특징입니다. 자바스크립트는 ES6부터 내장 Set 객체를 제공하지만, 셋이 내부적으로 어떻게 동작하는지 깊이 이해하려면 직접 구현해 보는 것이 가장 좋은 학습 방법입니다.아래는 일반 객체를 내부 저장소로 활용해 셋의 핵심 기능을 모두 담은 MySet 클래스의 전체 구현 코드입니다.MySet 클래스 전체 구현class MySet { constructor() { this.container = {};