Cây tìm kiếm

Cây tìm kiếm lưu trữ các khóa được sắp xếp theo thứ tự trong một cấu trúc phân cấp để việc tìm kiếm, chèn và xóa tuân theo một đường dẫn từ gốc đến lá; các biến thể tự cân bằng giữ cho đường dẫn đó ngắn để đảm bảo các thao tác có thời gian logarit.

Definition

Cây tìm kiếm là một cấu trúc dữ liệu dạng cây duy trì các khóa theo thứ tự đã sắp xếp theo một bất biến sắp xếp trên mỗi nút, hỗ trợ tìm kiếm, chèn, xóa và truy vấn dựa trên thứ tự hiệu quả; một cây tìm kiếm cân bằng bổ sung giới hạn hình dạng của nó để chiều cao vẫn là logarit theo số lượng khóa.

Scope

Chủ đề này bao gồm các cấu trúc từ điển có thứ tự dựa trên cây: cây tìm kiếm nhị phân và bất biến sắp xếp của nó, các lược đồ tự cân bằng giới hạn chiều cao (AVL, cây đỏ-đen và các loại khác), và cây cân bằng đa chiều như cây B được thiết kế cho bộ nhớ ngoài. Nó đề cập đến các thao tác mà các cấu trúc này hỗ trợ ngoài việc tra cứu đơn giản — tiền nhiệm, kế nhiệm, truy vấn phạm vi và duyệt theo thứ tự — và đối chiếu chúng với bảng băm, vốn không bảo toàn thứ tự.

Core questions

• Bất biến sắp xếp của cây tìm kiếm nhị phân làm cho việc tìm kiếm trở thành một đường đi từ gốc đến lá như thế nào?
• Tại sao một cây không cân bằng có thể suy biến thành thời gian tuyến tính, và việc cân bằng ngăn chặn điều đó như thế nào?
• Những phép quay hoặc quy tắc cấu trúc nào giữ cho cây AVL và cây đỏ-đen cân bằng?
• Tại sao cây B phù hợp với lưu trữ đĩa và cơ sở dữ liệu hơn là cây nhị phân?
• Khi nào các thao tác bảo toàn thứ tự đáng giá hơn chi phí bổ sung so với bảng băm?

Key concepts

• bất biến cây tìm kiếm nhị phân
• phép quay cây
• cây AVL
• cây đỏ-đen
• cây B
• chiều cao và sự cân bằng của cây
• duyệt theo thứ tự giữa (in-order traversal)
• truy vấn phạm vi và kế nhiệm

Key theories

Cân bằng chiều cao đảm bảo các thao tác logarit

Bằng cách duy trì một bất biến cân bằng thông qua các phép quay hoặc quy tắc cấu trúc, các cây tự cân bằng giữ chiều cao O(log n), đảm bảo tìm kiếm, chèn và xóa trong trường hợp xấu nhất là O(log n) bất kể thứ tự đầu vào.

Cây đa chiều cho bộ nhớ ngoài

Cây B lưu trữ nhiều khóa trên mỗi nút để phù hợp với kích thước khối đĩa, giảm thiểu số lần truy cập bộ nhớ ngoài chậm; điều này làm cho chúng trở thành cấu trúc tiêu chuẩn cho cơ sở dữ liệu và hệ thống tệp.

Clinical relevance

Cây tìm kiếm là trung tâm của các hệ thống cần truy cập có thứ tự: cây đỏ-đen triển khai các bản đồ và tập hợp có thứ tự trong các thư viện chuẩn, cây B và các biến thể của chúng là cấu trúc chỉ mục thống trị trong các cơ sở dữ liệu quan hệ và hệ thống tệp, và cây cân bằng hỗ trợ truy vấn phạm vi, lập lịch khoảng thời gian và cấu trúc tìm kiếm hình học.

History

Cây AVL, cây tìm kiếm nhị phân tự cân bằng đầu tiên, được Adelson-Velsky và Landis giới thiệu vào năm 1962. Bayer và McCreight đã giới thiệu cây B vào năm 1972 cho các chỉ mục có thứ tự lớn, và cây đỏ-đen được Guibas và Sedgewick phát triển vào năm 1978 như một lược đồ cân bằng thực tế, trở thành cơ sở của nhiều triển khai thư viện chuẩn.

Key figures

• Georgy Adelson-Velsky
• Evgenii Landis
• Rudolf Bayer
• Robert Sedgewick
• Robert Tarjan

Seminal works

• bayer1972
• cormen2009

Frequently asked questions

Tại sao không phải lúc nào cũng sử dụng bảng băm thay vì cây tìm kiếm?

Bảng băm cho phép tra cứu trung bình nhanh hơn nhưng không có thứ tự. Cây tìm kiếm giữ các khóa được sắp xếp, cho phép truy vấn phạm vi, lặp lại theo thứ tự và tra cứu tiền nhiệm/kế nhiệm trong O(log n), điều mà bảng băm không thể thực hiện hiệu quả. Lựa chọn phụ thuộc vào việc thứ tự có quan trọng hay không.

Tại sao cơ sở dữ liệu sử dụng cây B thay vì cây tìm kiếm nhị phân?

Cây B đóng gói nhiều khóa vào mỗi nút để phù hợp với kích thước của một khối đĩa, do đó một tìm kiếm chạm vào ít khối bộ nhớ ngoài chậm hơn nhiều so với một cây nhị phân có cùng số lượng khóa. Điều này giảm thiểu I/O, yếu tố chi phối hiệu suất trong cơ sở dữ liệu và hệ thống tệp.