코딩테스트 AVL 트리: 기준 이상 최솟값 찾기

읽기 전에 알아두면 좋아요

아래 개념이 익숙하면 본문을 바로 읽으세요. 낯선 개념만 링크에서 복습하면 됩니다.

JavaScript AVL 트리: 높이 불변식과 LL·RR·LR·RL 삽입 회전AVL 트리는 양쪽 높이 차이를 살피고 연결을 회전시켜 균형을 맞춥니다. 균형 회전과 BST 비교 규칙을 이용해 기준 이상 후보를 좁힙니다.
JavaScript 이진 탐색 트리 구현: 중복 키와 세 가지 삭제 처리이진 탐색 트리는 작은 키와 큰 키를 양쪽으로 나누어 저장합니다. 이진 탐색 트리의 탐색 방향과 중복·삭제 규칙을 확인합니다.

개념과 예제는 실행하지 않아도 읽을 수 있습니다. 내 컴퓨터·터미널에서 직접 실행하는 과정은 선택 실습입니다.

과정 위치와 선택 복습 안내

과정 위치: 심화 선택 실습 · 문제

과정 위치는 이 글이 속한 묶음입니다. 이 단계의 모든 개념을 먼저 읽을 필요는 없습니다. 위에 연결한 개념 중 낯선 내용만 복습하세요. 문제의 조건·상태·갱신 순서는 익숙한 언어로 설명하면 됩니다.

JavaScript로 문법·실행 복습하기 (선택)

개념 글의 코드는 JavaScript 예시입니다. 문제 화면에서는 JavaScript·Python·Java·C++·C# 중 익숙한 언어의 함수를 작성하세요. 본문의 Node.js 입출력 예시는 로컬 실행을 위한 별도 안내입니다.

AVL 기준 이상 최솟값 문제는 어떤 추가·조회 명령을 처리하나요?

키 추가와 기준 이상 최솟값 조회 명령을 처리하는 문제입니다. 이진 탐색 트리·높이·AVL의 기본을 준비하고, 아래 입력·반환 계약을 확인해 직접 풀어보세요.

적용 조건·범위: 작업 수 0~100,000. 번호와 기준은 정수이고 절댓값 1,000,000,000 이하입니다. 같은 번호를 여러 번 등록할 수 있지만 집합 원소 수는 한 번만 증가합니다.

본문 근거: Princeton Algorithms 공식 AVLTreeST 문서

[창작 문제] 기준 이상 등록번호 안내

등록번호를 순서 없이 추가하면서 방문자가 제시한 기준 이상인 가장 작은 번호를 안내합니다. 중복 등록은 한 번으로 취급하며 없는 답은 null입니다.

일곱 노드로 이루어진 균형 이진 트리 개념 표지 — 주제를 표현한 개념 표지입니다. 정확한 동작과 값의 변화는 아래 코드와 표에서 확인하세요.

이 문제는 BlogFlow 자료구조 학습용으로 독립 창작했습니다. 외부 문제의 지문이나 테스트를 옮기지 않았습니다.

문제
입력·출력과 제약
예시
힌트
정답과 해설

문제

전시 안내 데스크는 등록된 작품 번호를 관리합니다. add 작업은 번호를 등록하고 next 작업은 기준 이상인 등록번호 중 가장 작은 번호를 묻습니다. 기준과 같은 번호가 있으면 그 번호가 답입니다. 어떤 등록번호도 기준 이상이 아니면 null을 반환하세요. 등록 취소 작업은 없습니다.

입력·출력과 제약

JSON 객체 {ops}. 작업은 [“add”,key] 또는 [“next”,threshold]입니다.

next 작업의 답을 순서대로 담은 JSON 배열입니다. 각 답은 정수 또는 null입니다.

작업 수 0~100,000. 번호와 기준은 정수이고 절댓값 1,000,000,000 이하입니다. 같은 번호를 여러 번 등록할 수 있지만 집합 원소 수는 한 번만 증가합니다.

입력은 위 계약을 만족한다고 가정합니다. 온라인 채점기는 제공하지 않으며 로컬 Node.js에서 JSON 입력으로 실행합니다.

예시

예시 1 입력:

{"ops":[["next",15],["add",30],["add",10],["add",20],["add",20],["next",15],["next",30],["next",31]]}

예시 1 출력:

[null,20,30,null]

예시 2 입력:

{"ops":[]}

예시 2 출력:

[]

힌트

현재 노드가 기준 이상이면 후보로 기록하고 왼쪽에서 더 작은 답을 찾으세요. 현재 노드가 기준 미만이면 왼쪽은 볼 필요가 없습니다.

정답과 해설

직접 풀어보기

먼저 선택한 언어의 입력·반환 계약에 맞춰 작성해 보세요. 힌트 받기와 정답과 비교하기는 코드를 실행하지 않는 AI 분석입니다. 해답·해설은 아래에서 필요할 때 펼칠 수 있습니다.

내 풀이 JavaScript0 / 6,000바이트

function solve(input) {
    // 아래 함수 계약에 맞게 결과를 반환하세요.
    return [];
}

원문 JSON 객체를 파싱한 객체 input을 solve(input)에 전달하고 배열을 반환합니다. 표준 입출력은 포함하지 않습니다. Tab은 다음 항목으로 이동합니다. 입력 영역 오른쪽 아래를 끌어 높이를 조절할 수 있습니다.

비밀키·개인정보는 입력하지 마세요. 코드는 이 페이지에만 유지됩니다.

해답·해설 보기

class AVLSet {
    constructor() {
        this.root = null;
        this.size = 0;
    }
    check(key) {
        if (! Number.isSafeInteger(key)) throw new TypeError('키는 안전한 정수여야 합니다.');
    }
    height(node) {
        return node?.height ?? 0;
    }
    update(node) {
        node.height = 1 + Math.max(this.height(node.left), this.height(node.right));
    }
    rotateRight(y) {
        const x = y.left, middle = x.right;
        x.right = y;
        y.left = middle;
        this.update(y);
        this.update(x);
        return x;
    }
    rotateLeft(x) {
        const y = x.right, middle = y.left;
        y.left = x;
        x.right = middle;
        this.update(x);
        this.update(y);
        return y;
    }
    add(key) {
        this.check(key);
        const before = this.size;
        this.root = this.insert(this.root, key);
        return this.size !== before;
    }
    insert(node, key) {
        if (! node) {
            this.size++;
            return {
                key, left : null, right : null, height : 1
            };
        }
        if (key < node.key) node.left = this.insert(node.left, key);
        else if (key > node.key) node.right = this.insert(node.right, key);
        else return node;
        this.update(node);
        const balance = this.height(node.left) - this.height(node.right);
        if (balance > 1) {
            if (key > node.left.key) node.left = this.rotateLeft(node.left);
            return this.rotateRight(node);
        }
        if (balance < - 1) {
            if (key < node.right.key) node.right = this.rotateRight(node.right);
            return this.rotateLeft(node);
        }
        return node;
    }
    has(key) {
        this.check(key);
        let node = this.root;
        while (node) {
            if (key === node.key) return true;
            node = key < node.key ? node.left : node.right;
        }
        return false;
    }
    ceiling(key) {
        this.check(key);
        let node = this.root, candidate = null;
        while (node) {
            if (node.key >= key) {
                candidate = node.key;
                node = node.left;
            } else node = node.right;
        }
        return candidate;
    }
    toArray() {
        const result = [];
        const visit =(node) => {
            if (! node) return;
            visit(node.left);
            result.push(node.key);
            visit(node.right);
        };
        visit(this.root);
        return result;
    }
}
function solve( {
    ops
}) {
    const tree = new AVLSet(), out = [];
    for (const[type, key] of ops) {
        if (type === 'add') tree.add(key);
        else if (type === 'next') out.push(tree.ceiling(key));
        else throw new Error('알 수 없는 작업입니다.');
    }
    return out;
}

원문 JSON 객체를 파싱한 객체 input을 solve(input)에 전달하고 배열을 반환합니다. 표준 입출력은 포함하지 않습니다.

class Node:
    def __init__(self,key): self.key,self.left,self.right,self.height=key,None,None,1
def height(n): return n.height if n else 0
def update(n): n.height=1+max(height(n.left),height(n.right))
def right(y):
    x=y.left
    y.left=x.right
    x.right=y
    update(y); update(x)
    return x
def left(x):
    y=x.right
    x.right=y.left
    y.left=x
    update(x); update(y)
    return y
def insert(n,key):
    if n is None: return Node(key)
    if key<n.key: n.left=insert(n.left,key)
    elif key>n.key: n.right=insert(n.right,key)
    else: return n
    update(n)
    balance=height(n.left)-height(n.right)
    if balance>1:
        if key>n.left.key: n.left=left(n.left)
        return right(n)
    if balance<-1:
        if key<n.right.key: n.right=right(n.right)
        return left(n)
    return n
def solve(input):
    root=None
    out=[]
    for kind,key in input['ops']:
        if kind=='add': root=insert(root,key)
        else:
            node,candidate=root,None
            while node:
                if node.key>=key: candidate,node=node.key,node.left
                else: node=node.right
            out.append(candidate)
    return out

원문 JSON 객체를 파싱한 dict input을 solve(input)에 전달하고 list를 반환합니다. 표준 입출력은 포함하지 않습니다.

import java.util.*;
class Solution {
    static class Node {
        int key, h = 1;
        Node left, right;
        Node(int k) {
            key = k;
        }
    }
    int h(Node n) {
        return n == null ? 0 : n.h;
    }
    void update(Node n) {
        n.h = 1 + Math.max(h(n.left), h(n.right));
    }
    Node right(Node y) {
        Node x = y.left;
        y.left = x.right;
        x.right = y;
        update(y);
        update(x);
        return x;
    }
    Node left(Node x) {
        Node y = x.right;
        x.right = y.left;
        y.left = x;
        update(x);
        update(y);
        return y;
    }
    Node insert(Node n, int key) {
        if (n == null) return new Node(key);
        if (key < n.key) n.left = insert(n.left, key);
        else if (key > n.key) n.right = insert(n.right, key);
        else return n;
        update(n);
        int b = h(n.left) - h(n.right);
        if (b > 1) {
            if (key > n.left.key) n.left = left(n.left);
            return right(n);
        }
        if (b < - 1) {
            if (key < n.right.key) n.right = right(n.right);
            return left(n);
        }
        return n;
    }
    public Integer[] solve(String[] types, int[] keys) {
        Node root = null;
        List < Integer > out = new ArrayList < >();
        for (int i = 0; i < types.length; i++) {
            if (types[i].equals("add")) root = insert(root, keys[i]);
            else {
                Node n = root;
                Integer best = null;
                while (n != null) {
                    if (n.key >= keys[i]) {
                        best = n.key;
                        n = n.left;
                    } else n = n.right;
                }
                out.add(best);
            }
        }
        return out.toArray(new Integer[0]);
    }
}

ops의 작업 종류와 정수를 같은 인덱스의 types,keys 배열로 전달합니다. solve가 next 결과 Integer[]만 반환하며 답이 없으면 null입니다.

#include <algorithm>
#include <memory>
#include <optional>
#include <string>
#include <vector>
class AVL {
    struct Node {
        int key, h = 1;
        Node * left = nullptr;
        Node * right = nullptr;
        explicit Node(int k) : key(k) {
        }
    };
    std::vector < std::unique_ptr < Node >> owned;
    Node * root = nullptr;
    int h(Node * n) {
        return n ? n->h : 0;
    }
    void update(Node * n) {
        n->h = 1 + std::max(h(n->left), h(n->right));
    }
    Node * right(Node * y) {
        Node * x = y->left;
        y->left = x->right;
        x->right = y;
        update(y);
        update(x);
        return x;
    }
    Node * left(Node * x) {
        Node * y = x->right;
        x->right = y->left;
        y->left = x;
        update(x);
        update(y);
        return y;
    }
    Node * insert(Node * n, int key) {
        if (! n) {
            owned.emplace_back(new Node(key));
            return owned.back().get();
        }
        if (key < n->key) n->left = insert(n->left, key);
        else if (key > n->key) n->right = insert(n->right, key);
        else return n;
        update(n);
        int b = h(n->left) - h(n->right);
        if (b > 1) {
            if (key > n->left->key) n->left = left(n->left);
            return right(n);
        }
        if (b < - 1) {
            if (key < n->right->key) n->right = right(n->right);
            return left(n);
        }
        return n;
    }
    public : void add(int key) {
        root = insert(root, key);
    }
    std::optional < int > next(int key) {
        Node * n = root;
        std::optional < int > best;
        while (n) {
            if (n->key >= key) {
                best = n->key;
                n = n->left;
            } else n = n->right;
        }
        return best;
    }
};
std::vector < std::optional < int >> solve(const std::vector < std::string > & types, const std::vector < int > & keys) {
    AVL tree;
    std::vector < std::optional < int >> out;
    for (size_t i = 0; i < types.size(); i++) if (types[i] == "add") tree.add(keys[i]);
    else out.push_back(tree.next(keys[i]));
    return out;
}

C++17 이상. ops를 동일 길이 types/keys 벡터로 전달하며 next 결과 optional<int> 벡터를 반환합니다. 답이 없으면 nullopt이며 JSON의 null에 해당합니다.

using System;
using System.Collections.Generic;
public class Solution {
    class Node {
        public int key, h = 1;
        public Node left, right;
        public Node(int k) {
            key = k;
        }
    }
    int H(Node n) {
        return n == null ? 0 : n.h;
    }
    void Update(Node n) {
        n.h = 1 + Math.Max(H(n.left), H(n.right));
    }
    Node Right(Node y) {
        Node x = y.left;
        y.left = x.right;
        x.right = y;
        Update(y);
        Update(x);
        return x;
    }
    Node Left(Node x) {
        Node y = x.right;
        x.right = y.left;
        y.left = x;
        Update(x);
        Update(y);
        return y;
    }
    Node Insert(Node n, int key) {
        if (n == null) return new Node(key);
        if (key < n.key) n.left = Insert(n.left, key);
        else if (key > n.key) n.right = Insert(n.right, key);
        else return n;
        Update(n);
        int b = H(n.left) - H(n.right);
        if (b > 1) {
            if (key > n.left.key) n.left = Left(n.left);
            return Right(n);
        }
        if (b < - 1) {
            if (key < n.right.key) n.right = Right(n.right);
            return Left(n);
        }
        return n;
    }
    public int ?[] Solve(string[] types, int[] keys) {
        Node root = null;
        var output = new List < int ? >();
        for (int i = 0; i < types.Length; i++) {
            if (types[i] == "add") root = Insert(root, keys[i]);
            else {
                Node n = root;
                int ? best = null;
                while (n != null) {
                    if (n.key >= keys[i]) {
                        best = n.key;
                        n = n.left;
                    } else n = n.right;
                }
                output.Add(best);
            }
        }
        return output.ToArray();
    }
}

ops를 동일 길이 types/keys 배열로 전달합니다. Solve가 next 결과 int?[]만 반환하며 답이 없으면 null입니다.

Node.js 24 CommonJS용 전체 풀이입니다. avl-problem.cjs로 저장하세요. 클래스 선언, solve 함수, 표준 입력 처리가 모두 들어 있어 가이드 파일을 별도로 가져오지 않습니다. 예시 입력을 input.json에 저장하고 터미널에서 실행합니다.

Windows PowerShell:
Get-Content -Raw -Encoding UTF8 ./input.json | node ./avl-problem.cjs

macOS / Linux:
node avl-problem.cjs < input.json

class AVLSet {
  constructor() {
    this.root = null;
    this.size = 0;
  }
  check(key) {
    if (!Number.isSafeInteger(key)) throw new TypeError('키는 안전한 정수여야 합니다.');
  }
  height(node) { return node?.height ?? 0; }
  update(node) {
    node.height = 1 + Math.max(this.height(node.left), this.height(node.right));
  }
  rotateRight(y) {
    const x = y.left, middle = x.right;
    x.right = y;
    y.left = middle;
    this.update(y);
    this.update(x);
    return x;
  }
  rotateLeft(x) {
    const y = x.right, middle = y.left;
    y.left = x;
    x.right = middle;
    this.update(x);
    this.update(y);
    return y;
  }
  add(key) {
    this.check(key);
    const before = this.size;
    this.root = this.insert(this.root, key);
    return this.size !== before;
  }
  insert(node, key) {
    if (!node) {
      this.size++;
      return { key, left: null, right: null, height: 1 };
    }
    if (key < node.key) node.left = this.insert(node.left, key);
    else if (key > node.key) node.right = this.insert(node.right, key);
    else return node;
    this.update(node);
    const balance = this.height(node.left) - this.height(node.right);
    if (balance > 1) {
      if (key > node.left.key) node.left = this.rotateLeft(node.left);
      return this.rotateRight(node);
    }
    if (balance < -1) {
      if (key < node.right.key) node.right = this.rotateRight(node.right);
      return this.rotateLeft(node);
    }
    return node;
  }
  has(key) {
    this.check(key);
    let node = this.root;
    while (node) {
      if (key === node.key) return true;
      node = key < node.key ? node.left : node.right;
    }
    return false;
  }
  ceiling(key) {
    this.check(key);
    let node = this.root, candidate = null;
    while (node) {
      if (node.key >= key) {
        candidate = node.key;
        node = node.left;
      } else node = node.right;
    }
    return candidate;
  }
  toArray() {
    const result = [];
    const visit = (node) => {
      if (!node) return;
      visit(node.left);
      result.push(node.key);
      visit(node.right);
    };
    visit(this.root);
    return result;
  }
}

function solve({ ops }) {
  const tree = new AVLSet(), out = [];
  for (const [type, key] of ops) {
    if (type === 'add') tree.add(key);
    else if (type === 'next') out.push(tree.ceiling(key));
    else throw new Error('알 수 없는 작업입니다.');
  }
  return out;
}

module.exports = { solve };

if (require.main === module) {
  const input = JSON.parse(require('node:fs').readFileSync(0, 'utf8'));
  console.log(JSON.stringify(solve(input)));
}

아직 번호가 없을 때 next(15)는 null입니다. 30,10,20 등록은 LR 회전을 만들고 최종 루트가 20이 됩니다. 20을 다시 넣어도 집합은 {10,20,30}입니다. 기준 15의 최소 후보는 20, 기준 30의 후보는 자기 자신 30, 기준 31에는 후보가 없습니다. solve는 등록 시 add, 질의 시 ceiling만 호출하므로 전체 정렬을 반복하지 않습니다.

모든 노드에서 왼쪽 키는 node.key보다 작고 오른쪽 키는 큽니다. 중복은 새 노드로 만들지 않으므로 엄격한 부등호를 쓸 수 있습니다. 동시에 node.height는 1+max(왼쪽 높이,오른쪽 높이)이고, 균형 인수 balance=왼쪽 높이−오른쪽 높이는 −1,0,1이어야 합니다.

삽입은 먼저 일반 BST와 같은 한 경로를 내려갑니다. 재귀가 돌아올 때 그 경로의 높이를 다시 계산하고 균형을 고칩니다. 회전은 중위 순서를 바꾸지 않고 부모·자식 관계만 재배치합니다. 오른쪽 회전에서 x.right였던 middle은 y.left로 옮겨야 모든 키가 x< middle <y 순서를 보존합니다.

q개 작업과 최대로 저장한 서로 다른 키 수 u에 대해 전체 작업 시간은 최악 O(q log(u+2))입니다. 아직 등록번호가 없어 u=0이어도 q개의 next 요청을 읽고 null을 기록하는 O(q) 비용은 남습니다. 구조 O(u+1), 삽입 재귀 O(log(u+2)), 반환 결과 O(q) 공간이며 삭제 비용은 포함하지 않습니다.

표본과 경계를 직접 확인하려면 다음 코드를 avl-check.cjs로 저장하고 같은 폴더에서 node avl-check.cjs를 실행하세요. assert가 맞으면 출력 없이 종료하고, 다르면 예외와 함께 실패합니다.

const assert = require('node:assert/strict');
const { solve } = require('./avl-problem.cjs');

assert.deepEqual(
  solve({
  "ops": [
    [
      "next",
      15
    ],
    [
      "add",
      30
    ],
    [
      "add",
      10
    ],
    [
      "add",
      20
    ],
    [
      "add",
      20
    ],
    [
      "next",
      15
    ],
    [
      "next",
      30
    ],
    [
      "next",
      31
    ]
  ]
}),
  [null,20,30,null],
);
assert.deepEqual(
  solve({
  "ops": []
}),
  [],
);

연결 학습과 공식 자료

JavaScript AVL 트리: 높이 불변식과 LL·RR·LR·RL 삽입 회전에서 연산별 이유와 전체 복잡도를 이어서 확인할 수 있습니다. 다른 형식의 공식 연습은 LeetCode 1382 – Balance a Binary Search Tree를 참고하세요. 외부 문제의 정답이나 지문은 이 페이지에 복제하지 않았습니다.

공식 자료 확인일: 2026년 9월 10일. 구현은 이 글의 JavaScript 계약에 맞춰 독립적으로 작성했습니다. 다른 언어 라이브러리의 API와 숫자 범위가 그대로 적용되는 것은 아닙니다.

이 문제를 푼 뒤 확인하기

삽입으로 트리 균형이 바뀌는 경우와 기준 이상의 키가 없는 경우를 구분해 보세요.

본문의 예제와 이 반례를 직접 실행해 예상 출력과 비교하고, 결과가 다르면 입력 조건과 반복 범위를 다시 확인하세요.

이 글이 도움이 되었나요?

조회 중

이어서 공부하기

체크포인트: 해설을 가리고 다시 풀고, 경계 입력을 하나 바꾸어 예상 결과와 실제 결과를 비교하세요. 표본 하나에 더해 경계 입력과 작은 기준 풀이를 비교하고 왜 이 구조를 고르는지 설명하세요.

다음 추천 · 자료구조 개념: Red-Black 트리 원리: 색과 검은 높이로 균형 읽기

같은 주제에서 다음 개념과 예제로 이해를 넓힙니다.

권장 순서는 학습 가이드와 같습니다. 다른 순서는 접힌 참고 목록에서 확인할 수 있습니다. 읽음 표시는 숙달이나 채점 결과가 아닙니다.

원래 과정 목록 순서 (선택)

읽음 기록

읽음 — / 전체 58개 · 필수 58개

이 글을 쓴 해비

웹사이트를 제작·운영하고, 개인 서비스와 자동화·AI 도구를 만듭니다. 직접 만들며 배운 내용과 문제 해결 과정을 BlogFlow에 기록합니다.

새 글 받아보기

RSS 리더에서 BlogFlow의 새 글을 확인할 수 있습니다.

RSS 피드 구독하기