Cây tìm kiếm nhị phân BST: tìm, chèn và vì sao cây bị lệch

BST thêm tính chất gì cho cây nhị phân?

Một cây nhị phân chỉ giới hạn số con của mỗi nút. BST thêm quan hệ thứ tự giữa các khóa: mọi khóa ở cây trái nhỏ hơn khóa nút hiện tại, mọi khóa ở cây phải lớn hơn. Bài này dùng khóa nguyên phân biệt, vì vậy các dấu đều nghiêm ngặt.

Ví dụ chèn lần lượt [4, 2, 6, 1, 3, 5, 7]. Gốc là 4. Cây trái gồm 1, 2, 3; cây phải gồm 5, 6, 7. Khi cần tìm 5, so với 4 rồi đi phải tới 6; 5 nhỏ hơn 6 nên đi trái, gặp đúng 5. Những cây con còn lại chắc chắn không chứa khóa cần tìm theo quy tắc BST.

Quy tắc phải đúng với mọi hậu duệ. Một nút 5 nằm sâu trong cây con trái của gốc 4 làm cây không hợp lệ, dù nó có thể vẫn lớn hơn cha trực tiếp là 2. Vì vậy kiểm BST bằng so sánh từng nút với hai con trực tiếp là chưa đủ; thường cần truyền khoảng khóa cho phép xuống mỗi cây con.

Tìm kiếm: mỗi so sánh chọn một nhánh

Tại nút p, nếu khóa bằng x thì tìm thấy. Nếu x nhỏ hơn khóa p, chỉ tiếp tục ở con trái; nếu lớn hơn thì chỉ đi con phải. Đi tới nút rỗng nghĩa là x chưa có trong cây. Bản lặp trong code chỉ giữ một con trỏ hiện tại và không cần ngăn xếp đệ quy cho thao tác tìm.

Một đường tìm có tối đa h+1 nút theo quy ước chiều cao bằng số cạnh. Do đó chi phí O(h), bộ nhớ phụ O(1) cho bản lặp. Không kết luận O(log n) cho đến khi biết cây được giữ cân bằng hoặc có giả định phù hợp về hình dạng. Đây là điểm khác biệt quan trọng so với tìm kiếm nhị phân trên mảng đã sắp xếp.

Chèn khóa mới và xử lý khóa trùng

Chèn bắt đầu giống tìm kiếm. Khi nhánh cần đi còn rỗng, tạo nút mới tại nhánh đó. Vì mọi quyết định trên đường xuống đều giữ khoảng khóa hợp lệ, nút mới không phá quy tắc BST. Nếu cây rỗng, nút mới trở thành gốc, nên hàm phải trả gốc mới hoặc có cách cập nhật biến gốc của người gọi.

Code Python trả root sau mỗi lần chèn. Bản C++ nhận tham chiếu tới con trỏ gốc rồi dùng con trỏ tới vị trí liên kết cần sửa; đó là cách cập nhật được cả head gốc và liên kết con bằng một quy trình. Bạn có thể viết đệ quy cho dễ học hơn, nhưng vẫn cần gán lại con trỏ được trả về ở từng cấp.

Nếu x đã tồn tại, chương trình giữ nguyên cây, giống ý tưởng tập hợp. Với bài cần lưu các phần tử trùng, có thể thêm số đếm trong mỗi nút hoặc quy ước nhánh chứa bản trùng. Mọi hàm kiểm hợp lệ, tìm thứ hạng và xóa phải dùng đúng quy ước đó, không thay đổi giữa chừng.

#include <iostream>
#include <vector>
using namespace std;
struct Node{int key;Node*left=nullptr;Node*right=nullptr;explicit Node(int x):key(x){}};
void chen(Node*&root,int x){
    Node**p=&root;
    while(*p){if(x==(*p)->key)return;p=x<(*p)->key?&(*p)->left:&(*p)->right;}
    *p=new Node(x);
}
bool co(Node*p,int x){while(p){if(x==p->key)return true;p=x<p->key?p->left:p->right;}return false;}
void inorder(Node*p){if(p){inorder(p->left);cout<<p->key<<' ';inorder(p->right);}}
void huy(Node*p){if(p){huy(p->left);huy(p->right);delete p;}}
int main(){
    int n,x=5;vector<int>a={4,2,6,1,3,5,7};
    if(cin>>n>>x){a.resize(n);for(int&v:a)cin>>v;}
    Node*root=nullptr;for(int v:a)chen(root,v);
    inorder(root);cout<<'\n'<<co(root,x)<<'\n';huy(root);
}

class Node:
    def __init__(self,key):
        self.key,self.left,self.right=key,None,None

def chen(root,x):
    if root is None:
        return Node(x)
    p=root
    while True:
        if x==p.key:
            return root
        name='left' if x<p.key else 'right'
        child=getattr(p,name)
        if child is None:
            setattr(p,name,Node(x))
            return root
        p=child

def co(p,x):
    while p:
        if x==p.key:
            return True
        p=p.left if x<p.key else p.right
    return False

def inorder(root):
    out,st=[],[]
    p=root
    while p or st:
        while p:
            st.append(p)
            p=p.left
        p=st.pop()
        out.append(p.key)
        p=p.right
    return out

if __name__=='__main__':
    import sys
    d=list(map(int,sys.stdin.read().split()))
    a,x=(d[2:2+d[0]],d[1]) if d else ([4,2,6,1,3,5,7],5)
    root=None
    for v in a:
        root=chen(root,v)
    print(*inorder(root))
    print(int(co(root,x)))

Ví dụ mặc định in dòng 1 2 3 4 5 6 7, rồi dòng 1 vì tìm thấy 5. Để thử riêng, nhập n và khóa x cần tìm, sau đó n giá trị theo thứ tự chèn. n = 0 cho dòng duyệt rỗng và kết quả tìm 0. Code C++ hủy các nút sau khi dùng; không giữ con trỏ tới các nút đã giải phóng.

Inorder tăng dần và cây suy biến

Duyệt inorder thăm cây trái, nút hiện tại, cây phải. Với BST hợp lệ không trùng khóa, mọi phần bên trái nhỏ hơn gốc và mọi phần bên phải lớn hơn, nên toàn bộ dãy tăng dần. Tính chất này cho phép bạn tự kiểm tra cây bằng cách đối chiếu dãy duyệt inorder với sorted(set(a)) trên các bộ dữ liệu nhỏ.

Nhưng nếu chèn [1, 2, 3, 4, 5] theo đúng thứ tự tăng, cây có thể thành một chuỗi con phải. Chiều cao đạt n−1 và tìm khóa lớn nhất đi qua mọi nút. Dựng cây bằng n lần chèn trong tình huống này có tổng chi phí O(n²), dù mỗi lần chèn vẫn đúng quy tắc thứ tự.

AVL và cây đỏ đen bổ sung cơ chế cân bằng để tránh hình dạng quá lệch. Bản tự cài trong bài chưa có quay cây hay bảo đảm cân bằng, nên mục đích là hiểu quy tắc và chi phí theo chiều cao. Bản C++ duyệt/hủy dùng đệ quy cũng có thể cạn stack với cây cực lệch; dữ liệu lớn cần cách duyệt/hủy lặp phù hợp.

Khi nào dùng set, map hoặc bisect?

std::set và std::map C++ hỗ trợ thao tác có thứ tự với độ phức tạp logarithmic theo hợp đồng thư viện; không cần tự cài BST thường cho các bài chỉ cần chức năng đó. set.lower_bound(x) tìm phần tử đầu tiên không nhỏ hơn x. Không thay bằng thuật toán lower_bound tổng quát trên iterator của set rồi cho rằng tổng chi phí duyệt vẫn logarithmic.

Python có bisect để tìm vị trí trong list đã sắp xếp. Phần tìm vị trí O(log n), nhưng chèn vào giữa list vẫn có thể phải dồn O(n) phần tử. Vì vậy bisect cộng insert không phải bản thay thế có cùng chi phí cho cây cân bằng. Khi chỉ cần tra cứu tồn tại không cần thứ tự, bảng băm là lựa chọn khác với đánh đổi riêng.

Xóa nút cần xét những trường hợp nào?

Nút lá có thể bỏ trực tiếp. Nút có một con được thay bằng con đó. Nút có hai con thường đổi khóa với phần tử kế tiếp theo inorder, tức nút nhỏ nhất của cây phải, rồi xóa nút thay thế có ít con hơn. Phần code ở bài này chỉ cài tìm và chèn; đừng hiểu rằng có thể xóa nút hai con bằng một lệnh gán null mà giữ nguyên dữ liệu còn lại.

Sau mỗi thay đổi, tự kiểm dãy inorder còn tăng và số khóa đúng theo yêu cầu. Thử đầu vào tăng dần, giảm dần, toàn bằng nhau, cây rỗng và các truy vấn không tồn tại. Các ca này giúp phát hiện cả lỗi cập nhật gốc lẫn giả định cân bằng thiếu căn cứ.

Luyện ngay trên Big-O Coding

Ba bài luyện chèn, xác minh toàn bộ quy tắc BST và tìm khóa nhỏ thứ K. Bài thứ K cần đếm các nút được duyệt hoặc bổ sung kích thước cây con, không chỉ gọi hàm tìm khóa thông thường.

Câu hỏi thường gặp

Nguồn tham khảo

• Open Data Structures: BinarySearchTree
• cppreference: std::set
• Python: bisect