• TL;DR
• 이진 탐색 트리(BST)는 왼쪽 < 루트 < 오른쪽 규칙을 따르는 이진 트리 기반의 탐색 자료구조
• 주요 연산은 탐색 / 삽입 / 삭제 / 개수 4가지이며, 삭제 연산이 가장 복잡함
• 순회 방법은 전위(루트→왼→오) / 중위(왼→루트→오) / 후위(왼→오→루트) 3가지
• 중위 순회를 하면 정렬된 순서(오름차순)로 데이터를 방문할 수 있음
• 탐색·삽입·삭제 평균 O(log n), 편향 트리(최악)에서는 O(n)으로 저하
• 실제 응용: 단어장 프로그램, 폴더 용량 계산 등

01  이진 탐색 트리(BST)란?

탐색(Search)은 일상에서도 매우 중요한 작업입니다. 사전에서 단어를 찾거나, 쇼핑몰에서 상품을 검색하는 것도 모두 탐색이죠. 컴퓨터에서 이 탐색 작업을 효율적으로 처리하기 위해 고안된 자료구조가 바로 이진 탐색 트리(BST, Binary Search Tree)입니다.

📖 이진 탐색 트리(BST) 정의
레코드의 집합에서 특정 레코드를 찾아내는 탐색에 특화된 이진 트리 기반의 자료구조.
배열과 선형 리스트의 단점을 보완하기 위해 연결리스트로 구성된 이진 트리를 사용하며, 원소의 삽입·삭제가 용이하다.

📌 탐색 관련 핵심 용어

📌 BST의 4가지 핵심 성질

✓ 예시로 이해하기
루트가 18인 트리가 있다면:
· 왼쪽 서브 트리 = 18보다 작은 값들 (예: 7, 12, 15)
· 오른쪽 서브 트리 = 18보다 큰 값들 (예: 26, 22, 30)
이 규칙이 트리 전체에 재귀적으로 적용됩니다.

⚠️ BST의 한계
데이터 원소가 정렬되어 있어야 하며, 빈번한 삽입·삭제가 필요한 경우에는 부적합합니다.
삽입·삭제가 잦으면 트리가 한쪽으로 치우쳐 성능이 O(n)까지 저하될 수 있습니다.

02  BST의 4가지 연산

🔍 탐색 연산 (Search)

탐색은 항상 루트 노드에서 시작하며, 찾는 키(key)값과 현재 노드의 키를 비교해가며 내려갑니다.

C 코드 — 노드 구조체 정의

#include <stdio.h>
#include <stdlib.h>

// BST 노드 구조체
typedef struct TreeNode {
    int key;                    // 키(데이터)
    struct TreeNode *left;    // 왼쪽 자식 포인터
    struct TreeNode *right;   // 오른쪽 자식 포인터
} TreeNode;

C 코드 — 재귀적 탐색 함수

TreeNode* search(TreeNode *root, int key) {
    if (root == NULL) return NULL;  // 탐색 실패

    if (key == root->key)        // 탐색 성공
        return root;
    else if (key < root->key)   // 왼쪽 서브 트리로 재귀 탐색
        return search(root->left, key);
    else                         // 오른쪽 서브 트리로 재귀 탐색
        return search(root->right, key);
}

📖 코드 포인트
· root == NULL : 찾는 키가 없는 경우(탐색 실패). 삽입 시에는 이 위치가 새 노드 자리가 됨
· 재귀 호출 : BST의 구조적 특성(서브 트리도 BST)을 활용해 같은 함수를 반복 적용
· 반환값 : 찾은 노드의 포인터를 반환. 없으면 NULL 반환

⏱️ BST 시간 복잡도 성능 비교

❌ 편향 트리(Skewed Tree)란?
예를 들어 1, 2, 3, 4, 5를 순서대로 삽입하면 모든 노드가 오른쪽으로만 연결됩니다.
이렇게 되면 트리가 사실상 연결 리스트와 동일해져서 BST의 장점인 O(log n) 성능을 전혀 살릴 수 없습니다.

이를 해결하기 위해 AVL 트리, 레드-블랙 트리 같은 자가 균형 BST가 고안되었습니다.

➕ 삽입 연산 (Insert)

✓ 삽입 연산의 핵심 원칙
BST에서는 같은 키 값을 갖는 노드가 없어야 합니다.
탐색에 실패한 위치 = 새로운 노드를 삽입할 위치
따라서 삽입 전에 반드시 탐색을 먼저 수행해야 합니다.

슈도코드 (Pseudocode) — 삽입 연산 전체 흐름

insert (root, n)

if KEY(n) = KEY(root)                  // 중복 키 — 삽입 불가
    then return;

else if KEY(n) < KEY(root)          // 삽입 키가 더 작으면 왼쪽
    if LEFT(root) = NULL
        then LEFT(root) ← n;           // 왼쪽이 비었으면 바로 삽입
        else insert(LEFT(root), n);   // 아니면 왼쪽 서브트리로 재귀

else                                    // 삽입 키가 더 크면 오른쪽
    if RIGHT(root) = NULL
        then RIGHT(root) ← n;        // 오른쪽이 비었으면 바로 삽입
        else insert(RIGHT(root), n); // 아니면 오른쪽 서브트리로 재귀

C 코드 — 재귀적 삽입 함수

TreeNode* insert(TreeNode *root, int key) {
    if (root == NULL) {                       // 빈 자리 발견 → 새 노드 생성
        TreeNode *n = (TreeNode*)malloc(sizeof(TreeNode));
        n->key = key;
        n->left = n->right = NULL;
        return n;
    }
    if (key == root->key)                    // 중복 키 → 그냥 반환
        return root;
    else if (key < root->key)               // 왼쪽 서브트리로 재귀
        root->left = insert(root->left, key);
    else                                      // 오른쪽 서브트리로 재귀
        root->right = insert(root->right, key);
    return root;
}

📖 코드 포인트
· root == NULL 도달 : 탐색 실패 위치 = 새 노드를 삽입할 자리
· 중복 키 처리 : KEY(n) = KEY(root)이면 아무 작업 없이 바로 return (BST는 중복 불허)
· 재귀 호출 : 삽입할 키와 현재 노드를 비교해 왼쪽/오른쪽으로 내려가며 빈 자리를 탐색

🗑️ 삭제 연산 (Delete) — 가장 복잡한 연산

노드 삭제는 BST에서 가장 복잡한 연산입니다. 삭제 후에도 BST의 성질(왼쪽 < 루트 < 오른쪽)을 반드시 유지해야 하기 때문입니다. 삭제할 노드의 자식 수에 따라 처리 방법이 달라집니다.

📖 중위 후속자(Inorder Successor)란?
중위 순회(왼→루트→오) 기준으로 삭제 노드 바로 다음에 방문될 노드를 의미합니다.
이 값은 삭제 노드보다 크면서 가장 작은 값이므로, 그 자리에 들어와도 BST 성질이 유지됩니다.

· 중위 후속자 위치 : 오른쪽 서브 트리에서 가장 왼쪽(= 가장 작은) 노드
· 중위 전임자(Inorder Predecessor) : 왼쪽 서브 트리에서 가장 오른쪽(= 가장 큰) 노드

예) 노드 18 삭제 시
· 중위 후속자 = 오른쪽 서브 트리의 최솟값 → 22
· 중위 전임자 = 왼쪽 서브 트리의 최댓값 → 12
→ 22 또는 12 중 하나를 18 위치에 복사한 뒤, 원래 22(또는 12)를 삭제

🔢 개수 연산 (Count)

🔢 개수 연산 방법
전체 노드 수 = 왼쪽 서브 트리 노드 수 + 오른쪽 서브 트리 노드 수 + 1(루트)

모든 노드를 순회하면서 count 변수를 증가시키는 방식으로도 구현 가능.
이진 트리의 전체 노드 개수를 세기 위해서는 모든 노드의 순회가 필요합니다.

슈도코드 (Pseudocode) — 개수 연산

count_node(x)

if x = NULL                               // 빈 노드 → 0 반환
    then return 0;
    else return 1 + count_node(x.left)  // 루트 1 + 왼쪽 + 오른쪽
                    + count_node(x.right);

C 코드 — 재귀적 노드 개수 계산 함수

int count_node(TreeNode *x) {
    if (x == NULL)                                // 빈 노드 → 0 반환
        return 0;
    else
        return 1 + count_node(x->left)  // 현재 노드(1) + 왼쪽 서브트리
                 + count_node(x->right); // + 오른쪽 서브트리
}

📖 코드 포인트
· x == NULL : 트리가 없거나 리프 노드의 자식에 도달한 경우 — 0을 반환해 합산을 종료
· return 1 + ... : 현재 노드 자신(1) + 왼쪽 서브트리 개수 + 오른쪽 서브트리 개수
· 재귀 구조 : 모든 노드를 빠짐없이 방문하는 후위 순회와 동일한 흐름으로 동작

03  BST의 3가지 순회 방법

순회(Traversal)란 트리에 속하는 모든 노드를 중복 없이 한 번씩 방문하여 데이터를 처리하는 작업입니다. 선형 자료구조(배열, 리스트 등)는 순회 방법이 하나뿐이지만, 트리는 비선형 자료구조이므로 루트와 좌·우 서브 트리를 어떤 순서로 방문하느냐에 따라 3가지 방법으로 나뉩니다.

✓ 중위 순회가 정렬 순서인 이유
BST의 성질상 왼쪽 < 루트 < 오른쪽이므로,
왼쪽 서브 트리를 모두 방문 → 루트 → 오른쪽 서브 트리 순으로 가면
자연스럽게 작은 값부터 큰 값 순서(사전식/오름차순)로 방문하게 됩니다.

📖 이진 트리 순회의 재귀적 특성
이진 트리는 전체 트리와 서브 트리의 구조가 동일합니다.
따라서 전체 트리 순회에 사용한 알고리즘을 서브 트리에도 그대로 적용할 수 있습니다. (재귀 구조)

04  실제 응용 사례

✓ 폴더 용량 계산에 후위 순회를 쓰는 이유
부모 폴더의 용량을 알려면 자식 폴더의 용량을 먼저 알아야 합니다.
후위 순회(왼→오→루트)는 자식을 먼저 처리하고 부모를 마지막에 처리하는 구조이므로,
하위 폴더 용량을 합산하여 상위 폴더로 반환하는 계산에 딱 맞습니다.

📌 핵심 정리

· BST 정의 : 왼쪽 서브 트리 키 < 루트 키 < 오른쪽 서브 트리 키를 만족하는 이진 트리
· 시간 복잡도 : 평균 O(log n) / 편향 트리(최악) O(n) — 균형 유지가 핵심
· 탐색 연산 : 루트에서 시작, 키 비교로 좌/우 이동, 재귀 구조로 구현
· 삽입 연산 : 탐색 실패 위치가 삽입 위치, 반드시 탐색 먼저 수행
· 삭제 연산 : 단말 노드 / 자식 1개 / 자식 2개 세 경우 구분 처리
· 중위 후속자 : 오른쪽 서브 트리의 최솟값 — Case 3 삭제 시 후계자로 사용
· 전위 순회 : 루트 → 왼쪽 → 오른쪽
· 중위 순회 : 왼쪽 → 루트 → 오른쪽 (결과: 오름차순 정렬)
· 후위 순회 : 왼쪽 → 오른쪽 → 루트 (폴더 용량 계산에 활용)

태그 : 이진탐색트리란BST 자료구조이진트리 순회 종류전위순회 중위순회 후위순회 차이BST 삭제 연산이진탐색트리 탐색방법C언어 자료구조중위순회 정렬순서후계자 노드란BST 응용 사례

• JK 플립플롭 : SR FF의 S=R=1 불안정 문제를 해결. J=K=1이면 출력이 toggle(반전)
• 특성방정식 (JK) : Q(t+1) = J·Q(t) + K·Q(t)
• T 플립플롭 : JK의 J·K를 하나로 묶은 것. T=0이면 불변, T=1이면 toggle
• 특성방정식 (T) : Q(t+1) = T·Q(t) + T·Q(t) → 출력 주파수 = 입력의 1/2 (분주회로)
• 비동기 입력 : PR(Preset, Q→1) · CLR(Clear, Q→0) — active low, 클록 무관
• 동작 특성 : 전파지연시간 / 설정 시간(Set-up) / 보류 시간(Hold) / 펄스 폭 / 최대 클록 주파수
• 멀티바이브레이터 3종 : 무안정(발진기) / 단안정(one-shot) / 쌍안정(플립플롭)

01 JK 플립플롭 — SR의 한계를 넘어서

📖 왜 JK 플립플롭이 필요한가?
SR 플립플롭은 S=1, R=1 입력이 동시에 들어올 때 출력이 불안정(undefined)해지는 치명적 단점이 있다. JK 플립플롭은 이 금지 입력 조합을 toggle(반전) 동작으로 정의해 문제를 완전히 해결했다. 플립플롭 중 가장 널리 사용되는 이유가 여기에 있다.

🔁 JK 플립플롭 입출력 대응 관계

JK 플립플롭의 J는 SR의 S(set)에, K는 R(reset)에 각각 대응한다. 클록펄스(CP=1)가 인가되었을 때의 동작은 다음과 같다.

✓ 특성 방정식 (Characteristic Equation)

Q(t+1) = J · Q(t) + K · Q(t)

· J=1, K=0 → Q(t+1) = 1·Q(t) + 1·Q(t) = Q(t) + Q(t) = 1
· J=0, K=1 → Q(t+1) = 0 + 0 = 0
· J=K=1 → Q(t+1) = Q(t) + 0 = Q(t) (toggle)

⚡ 클록형 vs 에지 트리거 JK 플립플롭

✓ 74112 IC — 비동기 입력 동작
PR과 CLR은 active low 신호 (0일 때 동작).
· PR = 0 → J, K, CP 상태에 관계없이 Q = 1 (강제 Set)
· CLR = 0 → J, K, CP 상태에 관계없이 Q = 0 (강제 Reset)
· PR = CLR = 1 → 정상 클록 동작

02 T 플립플롭 — Toggle 전용 설계

📖 T 플립플롭 개념
JK 플립플롭의 J 입력과 K 입력을 하나로 묶어 단일 입력 T로 구동하는 플립플롭. JK FF에서 J=K=0 (불변) 또는 J=K=1 (toggle) 두 경우만 사용하도록 특화한 회로다.

· T = 0 → JK FF의 J=0, K=0과 동일 → 출력 불변(Hold)
· T = 1 → JK FF의 J=1, K=1과 동일 → 출력 toggle(반전)

📊 T 플립플롭 진리표 · 특성표 · 방정식

<진리표> — CP=1일 때

<특성표> — 현재 상태 Q(t)와 입력 T에 따른 다음 상태

✓ 특성 방정식 (Characteristic Equation)

Q(t+1) = T · Q(t) + T · Q(t)

· T=0 → Q(t+1) = 0 + Q(t) = Q(t) (불변)
· T=1 → Q(t+1) = Q(t) + 0 = Q(t) (반전)

📉 T 플립플롭의 분주(分周) 특성

⚠️ 시험 함정 — 출력 주파수
T 플립플롭(T=1 고정)에서 출력 주파수 = 입력 클록 주파수 × 1/2.
"출력 주파수 = 입력 주파수와 동일하다"는 표현은 틀린 설명이다.
클록이 들어올 때마다 출력이 반전되므로, 클록 2주기에 출력 1주기가 완성된다.

· T FF 2개를 직렬 연결 → 클록을 1/4로 분주 (4분주 회로)
· 이 원리로 계수(Counter) 회로의 핵심 소자로 사용

🔧 T 플립플롭 구성 방법

03 비동기 입력 — PR · CLR

📖 비동기 입력(Asynchronous Input)이란?
대부분의 플립플롭은 클록펄스(CP)에 의해 상태가 바뀌는 동기 입력이 있고, 클록과 무관하게 즉시 출력을 바꿀 수 있는 비동기 입력도 함께 갖추고 있다.

· PR (Preset, active low) : 0을 인가하면 즉시 Q = 1
· CLR (Clear, active low) : 0을 인가하면 즉시 Q = 0
· 주요 용도 : 회로 동작 전 초기값 설정, 시스템 리셋

04 플립플롭 동작 특성 파라미터

플립플롭이 실제 회로에서 올바르게 동작하려면 입력 신호의 타이밍이 정확해야 한다. 아래 파라미터들은 데이터시트에서 반드시 확인해야 하는 필수 수치들이다.

⚠️ 설정 시간 · 보류 시간 위반 시 발생하는 일
두 조건 중 하나라도 위반되면 플립플롭 출력이 0도 1도 아닌 메타스테이블(metastable) 상태에 빠질 수 있다. 이 상태는 예측 불가능한 출력을 만들어 디지털 시스템 전체를 오동작시키기 때문에 실제 설계에서 반드시 준수해야 한다.

05 멀티바이브레이터 3종

📖 멀티바이브레이터(Multivibrator)란?
기본적으로 두 개의 인버터가 서로의 출력을 입력으로 받아 피드백(feedback)을 구성하는 회로. 한쪽 출력이 0이면 반드시 다른 쪽은 1이 되어 동시에 같은 상태에 있을 수 없다. 디지털 시스템에서 2진수 저장, 펄스 계수, 연산 동기화 등 핵심 기능을 수행한다.

📋 멀티바이브레이터 3종 비교

❌ 용어 주의 — '준안정'과 '불안정'을 혼동하지 말 것
· 무안정(Astable) : 안정 상태가 0개. 두 불안정(unstable) 상태를 자동으로 오가는 발진 동작
· 단안정(Monostable) : 안정 상태 1개 + 준안정(quasi-stable) 상태 1개. 트리거가 오면 준안정 상태로 갔다가 일정 시간 후 자동으로 안정 상태로 복귀

따라서 "외부 트리거 없이 준안정 상태에서 다른 준안정 상태로 변화를 되풀이하는 것"은 정확한 표현이 아니며, 올바른 답은 '무안정(비안정) 멀티바이브레이터'이고 두 불안정 상태를 오간다고 이해하는 것이 정확하다.

🔔 무안정 멀티바이브레이터 구현 방법

📌 핵심 정리

· JK 플립플롭 : J=K=1 → toggle, 특성방정식 Q(t+1) = J·Q(t) + K·Q(t), 가장 범용적
· 에지 트리거 : 상승(↑) 또는 하강(↓) 에지 순간에만 동작, 레이스 문제 없음
· T 플립플롭 : JK의 J·K를 묶은 것, T=1이면 toggle. 출력 주파수 = 입력의 1/2 (분주)
· 비동기 입력 : PR=0이면 Q=1, CLR=0이면 Q=0, 클록과 무관하게 즉시 동작
· 설정·보류 시간 : 위반 시 메타스테이블 상태 → 실제 설계에서 반드시 준수
· 무안정 : 안정 0개, 자력 발진 (발진기·타이머) / 단안정 : 안정 1개, 트리거 시 일정 폭 펄스
· 쌍안정 : 안정 2개 = 플립플롭. 플립플롭은 쌍안정 멀티바이브레이터와 동일하다

태그 : JK플립플롭이란JK플립플롭 SR플립플롭 차이T플립플롭이란T플립플롭 분주회로플립플롭 특성방정식에지트리거 플립플롭멀티바이브레이터 종류무안정 단안정 쌍안정 차이플립플롭 설정시간 보류시간디지털공학 플립플롭