Wiki › Thuật toán › Toán học › Cây Stern-Brocot

Cây Stern-Brocot

Cây nhị phân chứa mọi phân số dương tối giản đúng một lần, dựng bằng phép trung vị. Dùng để tìm kiếm nhị phân trên số hữu tỉ, xấp xỉ phân số với mẫu giới hạn và tìm phân số đơn giản nhất trong một khoảng.

huunguyen huunguyen Updated Tháng 11. 16, 2026 Đọc 15 phút 3 lượt xem

Cây Stern-Brocot (Stern-Brocot tree) là cây nhị phân tìm kiếm vô hạn chứa mọi phân số dương tối giản, mỗi phân số đúng một lần. Nó được dựng chỉ bằng một phép toán: trung vị (mediant) của hai phân số ab và cd là a+cb+d. Đường đi từ gốc tới pq chính là thuật toán Euclid trên (p,q), và độ dài đường đi khi nén theo đoạn bằng độ dài liên phân số của pq, tức O(logmax(p,q)).

Cây này là công cụ để tìm kiếm nhị phân trên tập số hữu tỉ: tìm phân số mẫu không quá N gần một số thực nhất, phân số "đơn giản nhất" trong một khoảng, phân số thứ k trong một dãy phân số có thứ tự, hoặc giải các bài mà một quá trình "cộng tử với tử, mẫu với mẫu" xuất hiện ngầm.

Ý tưởng / Trực giác

Cách dựng. Bắt đầu với hai biên 01 và 10 (vô cực). Nút gốc là trung vị 11. Mỗi nút có một biên trái ab và biên phải cd, giá trị là trung vị a+cb+d; con trái nhận biên (ab,nút), con phải nhận biên (nút,cd).

           0/1 .................................................... 1/0
                                    1/1
                   1/2                                 2/1
         1/3                2/3               3/2               3/1
    1/4       2/5      3/5       3/4     4/3       5/3     5/2       4/1

Bổ đề 1 (định thức bằng 1). Với hai biên kề nhau ab<cd của mọi nút, bc−ad=1. Chứng minh: đúng với (0/1,1/0): 1·1−0·0=1. Thay biên phải bằng trung vị: b(a+c)−a(b+d)=bc−ad=1; thay biên trái cũng vậy. Hệ quả: mọi nút a+cb+d là tối giản (một ước chung của tử và mẫu sẽ chia hết bc−ad=1), và nó nằm thực sự giữa hai biên.

Bổ đề 2 (mọi phân số đều xuất hiện). Nếu ab<pq<cd với bc−ad=1 thì q≥b+d và p≥a+c. Chứng minh: cq−dp≥1 và bp−aq≥1 (là số nguyên dương), nên q=q(bc−ad)=b(cq−dp)+d(bp−aq)≥b+d; tương tự cho p. Vậy khi đi xuống cây theo hướng của pq, mẫu của nút tăng thực sự mỗi bước nhưng không bao giờ vượt q, nên sau hữu hạn bước ta gặp đúng pq. Bổ đề này cũng nói: trung vị của hai biên là phân số có mẫu nhỏ nhất (và tử nhỏ nhất) nằm giữa hai biên.

Đường đi là thuật toán Euclid. Từ pq đi ngược lên: nếu p>q thì nút nằm ở nhánh phải và nút cha có dạng p−qq; nếu p<q thì ở nhánh trái với cha pq−p. Đó là Euclid dạng trừ. Một loạt k bước cùng hướng gộp thành một phép chia, nên đường đi nén có dạng Ra0La1Ra2⋯ với [a0;a1,a2,…] là liên phân số của pq (số hạng cuối giảm 1).

Tìm kiếm nhị phân trên số hữu tỉ. Cho một vị từ đơn điệu pred (đúng với phân số nhỏ, sai với phân số lớn) và giới hạn mẫu N. Duy trì hai biên L (pred đúng) và R (pred sai). Lặp: dịch L←L+sR với s lớn nhất còn giữ pred đúng và mẫu ≤N; rồi dịch R←R+sL tương tự. Khi trung vị L+R có mẫu vượt N, theo bổ đề 2 không còn phân số mẫu ≤N nào nằm giữa, nên L,R là hai phân số kề nhau cần tìm. Nếu đi từng bước một, số bước có thể tới N (hoặc vô hạn với R=1/0); dùng nhân đôi rồi tìm nhị phân cho s, mỗi đoạn tốn O(log) lần gọi pred, và số lần đổi hướng là độ dài liên phân số O(logN).

Ví dụ chạy tay

Đường đi tới 53. So 53 với từng nút:

Bước Biên trái Biên phải Nút (trung vị) So với 5/3 Đi
1 0/1 1/0 1/1 lớn hơn R
2 1/1 1/0 2/1 nhỏ hơn L
3 1/1 2/1 3/2 lớn hơn R
4 3/2 2/1 5/3 bằng dừng

Đường đi nén là R1 L1 R1. Cách Euclid cho cùng kết quả: (5,3)→ 5>3, ⌊4/3⌋=1 bước R, còn (2,3)→ ⌊2/2⌋=1 bước L, còn (2,1)→ ⌊1/1⌋=1 bước R, còn (1,1). Liên phân số 53=[1;1,2], số hạng cuối giảm 1 thành 1,1,1. Tương tự, 38 có đường đi L2 R1 L1.

Tìm hai phân số mẫu ≤4 kẹp x=0,7 (pred: pq≤710):

Vòng Thao tác Thử Kết quả
1 L=0/1 dịch về R=1/0 1/1≤0,7? sai s=0
1 R=1/0 dịch về L: 1s 1/1 sai, 1/2 đúng s=1, R=1/1
2 L=0/1 dịch về R: s1+s 1/2, 2/3 đúng; 3/4 sai s=2, L=2/3
2 R=1/1 dịch về L: 1+2s1+3s 3/4 sai, mẫu 4; 5/7 mẫu quá 4 s=1, R=3/4
3 trung vị 5/7 có mẫu 7>4 dừng

Kết quả L=23≤0,7<34=R, và 3·3−2·4=1. Phân số có mẫu nhỏ nhất nằm thực sự giữa 23 và 34 là trung vị 57.

Cài đặt

sb_search nhận vị từ pred(p, q) tùy ý, nên dùng được cho mọi bài "tìm phân số lớn nhất thỏa điều kiện đơn điệu". Khi pred so sánh với một phân số, nhân chéo bằng __int128 để tránh tràn.

C++
typedef long long ll;

// Đường đi từ gốc 1/1 tới p/q (p, q > 0, nguyên tố cùng nhau), nén theo đoạn: (ký tự, số lần).
// 'R' = sang phải (lớn hơn), 'L' = sang trái. Chính là thuật toán Euclid.
vector<pair<char, ll>> sb_path(ll p, ll q) {
    vector<pair<char, ll>> path;
    while (p != q) {
        if (p > q) {
            ll k = (p - 1) / q;  // số bước R liên tiếp, dừng trước khi p <= 0
            path.push_back({'R', k});
            p -= k * q;
        } else {
            ll k = (q - 1) / p;
            path.push_back({'L', k});
            q -= k * p;
        }
    }
    return path;
}

// Ngược lại: từ đường đi suy ra phân số. Giữ hai biên trái a/b, phải c/d; nút hiện tại là trung vị.
pair<ll, ll> sb_node(const vector<pair<char, ll>>& path) {
    ll a = 0, b = 1, c = 1, d = 0;  // biên 0/1 và 1/0
    for (auto [ch, k] : path) {
        if (ch == 'R') { a += k * c; b += k * d; }  // k lần: biên trái = trung vị
        else { c += k * a; d += k * b; }            // k lần: biên phải = trung vị
    }
    return {a + c, b + d};
}

// pred(p, q) đơn điệu: đúng với phân số nhỏ, sai với phân số lớn (đúng tại 0/1, sai tại 1/0).
// Trả về L = phân số lớn nhất có pred đúng và R = phân số nhỏ nhất có pred sai,
// xét các phân số mẫu <= N. R có thể là 1/0. Mỗi lần đổi hướng: nhân đôi rồi tìm nhị phân.
pair<pair<ll, ll>, pair<ll, ll>> sb_search(ll N, function<bool(ll, ll)> pred) {
    ll a = 0, b = 1, c = 1, d = 0;
    while (true) {
        bool moved = false;
        for (int side = 0; side < 2; side++) {
            // side 0: L += s*R, cần mẫu <= N và pred đúng; side 1: R += s*L, cần pred sai
            auto ok = [&](ll s) {
                ll p = side == 0 ? a + s * c : c + s * a, q = side == 0 ? b + s * d : d + s * b;
                return q <= N && pred(p, q) == (side == 0);
            };
            ll s = 0, step = 1;
            while (ok(s + step)) { s += step; step *= 2; }  // nhân đôi
            for (; step > 0; step /= 2)                     // rồi thu hẹp
                if (ok(s + step)) s += step;
            if (s > 0) moved = true;
            if (side == 0) { a += s * c; b += s * d; }
            else { c += s * a; d += s * b; }
        }
        if (!moved) break;  // trung vị (a+c)/(b+d) có mẫu > N
    }
    return {{a, b}, {c, d}};
}

// Phân số có mẫu nhỏ nhất nằm thực sự giữa a/b và c/d (0 <= a/b < c/d, b, d > 0).
pair<ll, ll> simplest_between(ll a, ll b, ll c, ll d) {
    ll k = a / b;  // tách phần nguyên chung
    a -= k * b;
    c -= k * d;
    if (c > d) return {k + 1, 1};       // số nguyên k+1 nằm trong khoảng
    if (a == 0) return {k * (d / c + 1) + 1, d / c + 1};  // dạng 1/q với q nhỏ nhất
    auto [p, q] = simplest_between(d, c, b, a);  // lấy nghịch đảo: (d/c, b/a)
    return {k * p + q, p};  // nghịch đảo lại (q/p) rồi cộng k
}
Python
# Đường đi từ gốc 1/1 tới p/q (p, q > 0, nguyên tố cùng nhau), nén theo đoạn: (ký tự, số lần).
# "R" = sang phải (lớn hơn), "L" = sang trái. Chính là thuật toán Euclid.
def sb_path(p, q):
    path = []
    while p != q:
        if p > q:
            k = (p - 1) // q  # số bước R liên tiếp, dừng trước khi p <= 0
            path.append(("R", k))
            p -= k * q
        else:
            k = (q - 1) // p
            path.append(("L", k))
            q -= k * p
    return path


# Ngược lại: từ đường đi suy ra phân số. Giữ hai biên trái a/b, phải c/d; nút hiện tại là trung vị.
def sb_node(path):
    a, b, c, d = 0, 1, 1, 0  # biên 0/1 và 1/0
    for ch, k in path:
        if ch == "R":
            a, b = a + k * c, b + k * d  # k lần: biên trái = trung vị
        else:
            c, d = c + k * a, d + k * b  # k lần: biên phải = trung vị
    return a + c, b + d


# pred(p, q) đơn điệu: đúng với phân số nhỏ, sai với phân số lớn (đúng tại 0/1, sai tại 1/0).
# Trả về L = phân số lớn nhất có pred đúng và R = phân số nhỏ nhất có pred sai,
# xét các phân số mẫu <= N. R có thể là 1/0. Mỗi lần đổi hướng: nhân đôi rồi tìm nhị phân.
def sb_search(N, pred):
    a, b, c, d = 0, 1, 1, 0
    while True:
        moved = False
        for side in (0, 1):
            # side 0: L += s*R, cần mẫu <= N và pred đúng; side 1: R += s*L, cần pred sai
            def ok(s):
                if side == 0:
                    p, q = a + s * c, b + s * d
                else:
                    p, q = c + s * a, d + s * b
                return q <= N and pred(p, q) == (side == 0)

            s, step = 0, 1
            while ok(s + step):  # nhân đôi
                s += step
                step *= 2
            while step > 0:  # rồi thu hẹp
                if ok(s + step):
                    s += step
                step //= 2
            if s > 0:
                moved = True
            if side == 0:
                a, b = a + s * c, b + s * d
            else:
                c, d = c + s * a, d + s * b
        if not moved:
            break  # trung vị (a+c)/(b+d) có mẫu > N
    return (a, b), (c, d)


# Phân số có mẫu nhỏ nhất nằm thực sự giữa a/b và c/d (0 <= a/b < c/d, b, d > 0).
def simplest_between(a, b, c, d):
    k = a // b  # tách phần nguyên chung
    a -= k * b
    c -= k * d
    if c > d:
        return k + 1, 1  # số nguyên k+1 nằm trong khoảng
    if a == 0:
        return k * (d // c + 1) + 1, d // c + 1  # dạng 1/q với q nhỏ nhất
    p, q = simplest_between(d, c, b, a)  # lấy nghịch đảo: (d/c, b/a)
    return k * p + q, p  # nghịch đảo lại (q/p) rồi cộng k

Ví dụ gọi: sb_search(4, [&](ll p, ll q) { return (__int128)p * 10 <= (__int128)7 * q; }) trả về (2/3,3/4) như bảng ở trên.

Độ phức tạp

Thao tác Thời gian Bộ nhớ
sb_path(p, q), sb_node O(logmax(p,q)) O(logmax(p,q))
sb_search với giới hạn mẫu N O(log2N) lần gọi pred O(1)
simplest_between O(logmax(b,d)) O(log) đệ quy
Đi xuống từng bước một (không nén) tới O(N) O(1)

Số đoạn của đường đi bằng độ dài liên phân số, bị chặn bởi số bước của thuật toán Euclid: O(log) (mỗi hai bước, số lớn ít nhất giảm một nửa). Trong sb_search, mỗi đoạn tìm s bằng nhân đôi rồi chia đôi, O(logN) lần gọi pred; nếu pred tự tốn O(log) (ví dụ một tổng phần nguyên kiểu Euclid) thì tổng là O(log3).

⚠️ Lỗi thường gặp

  • Đi xuống từng bước: với 1109 hay 10181, đường đi không nén dài tới 109 hoặc 1018 bước. Luôn gộp các bước cùng hướng bằng phép chia hoặc nhân đôi.
  • Đếm thừa một bước ở đoạn cuối: khi p chia hết cho q (ví dụ 31), số bước R là pq−1=2, không phải 3; vì vậy code dùng ⌊(p−1)/q⌋. Phân số chưa tối giản làm vòng lặp không dừng ở (1,1): rút gọn trước.
  • Tràn số khi nhân chéo: so sánh pq≤xy bằng p·y≤x·q với các giá trị cỡ 1018 cần __int128; khi nhân đôi s, tử số tạm thời cũng có thể vượt long long nếu pred không chặn sớm.
  • Biên vô cực 1/0: khi R=1/0, dịch L←L+sR không tăng mẫu, nên giới hạn mẫu không chặn được s; vị từ bắt buộc phải sai với các phân số đủ lớn, nếu không vòng nhân đôi chạy mãi.
  • Nhầm "mẫu nhỏ nhất" với "gần nhất": trung vị của hai biên kề nhau là phân số mẫu nhỏ nhất trong khoảng, nhưng phân số mẫu ≤N gần x nhất phải so khoảng cách tới cả L và R sau khi tìm xong.

Biến thể / Mở rộng

  • Cây Calkin-Wilf: cùng tập phân số, con trái của ab là aa+b, con phải là a+bb; duyệt theo tầng cho dãy s(n)s(n+1) của dãy Stern. Đường đi tới một phân số vẫn là thuật toán Euclid, chỉ đảo thứ tự các bước so với Stern-Brocot.
  • Dãy Farey FN: các phân số trong [0,1] có mẫu ≤N, theo thứ tự tăng; hai phần tử kề nhau thỏa bc−ad=1 và phần tử chen vào đầu tiên là trung vị. Phần tử kế tiếp sau ab,cd là kc−akd−b với k=⌊(N+b)/d⌋.
  • Phân số thứ k / xấp xỉ tốt nhất: kết hợp sb_search với một hàm đếm số phân số ≤x (tổng phần nguyên kiểu Euclid ∑q⌊xq⌋).
  • Bao lồi các điểm nguyên dưới một đường cong: mỗi cạnh của bao lồi là một hướng tìm bằng cây Stern-Brocot, dùng để đếm điểm nguyên dưới cung tròn hay dưới hyperbol.
  • Liên hệ: Thuật toán Euclid mở rộng (cùng cấu trúc thương số), Sắp xếp & Tìm kiếm nhị phân (tìm nhị phân trên số nguyên), Số lớn và __int128.

Bài tập luyện

  • Hàm số (icpc22mbe): (Very Hard) Tìm n nhỏ nhất với f(n)/f(n+1)=p/q cho một dãy truy hồi; đó là dãy Stern, và n là chỉ số của p/q trên cây Calkin-Wilf, đọc ra từ đường đi Euclid (cần số lớn).
  • Cam, táo và dãy thẻ (fruitcard): (Expert) Tìm dãy thẻ (in dạng nén) để chia hết x cam và y táo với x,y≤1018; mỗi lá thẻ là một phép lấy trung vị, nên dãy thẻ là đường đi tới x/y trên cây Stern-Brocot, tồn tại khi và chỉ khi gcd(x,y)=1.
  • Dãy phân số vô hạn (icpc23nati): (Expert) Tìm phân số thứ k trong dãy các p/q với q≤n≤109; tìm kiếm nhị phân trên cây Stern-Brocot với vị từ đếm ∑q⌊xq⌋≥k.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0