Đồ Án Hai cây nhị phân tìm kiếm tương tự

LỜI NÓI ĐẦU
Ngày nay công nghệ thông tin đóng vai trò cực kỳ quan trọng và trở thành một phần không thể thiếu trong đời sống. Việc ứng dụng một cách rộng rãi vào mọi lĩnh vực đã đem lại hiệu quả, năng suất công việc khá cao. Điều đó đòi hỏi ngày càng cải tiến công nghệ, tối ưu hóa thuật toán để phát triển nhiều tính năng hơn nữa. Có rất nhiều công cụ, môn học để giải quyết vấn đề này. Một trong những môn học nền tảng quan trọng ảnh hưởng trực tiếp đến thuật toán đó là “Cấu trúc dữ liệu và thuật toán”.
Để nghiên cứu kỹ hơn và xây dựng hợp lý cấu trúc dữ liệu và thuật toán, nhóm chúng em đã chọn đề tài về “hai cây nhị phân tìm kiếm tương tự”.
Trong quá trình thực hiện, mặc dù đã có nhiều cố gắng song không tránh khỏi những thiếu sót, chúng em rất mong nhận được sự chỉ dẫn, đóng góp của quý thầy cô để đề tài của chúng em ngày càng hoàn thiện hơn.
Đồng thời, chúng em cũng gửi lời cảm ơn chân thành đến thầy Phan Thanh Tao đã giúp đỡ chúng em hoàn thành đề tài này.

I. GIỚI THIỆU ĐỀ TÀI:
Cây là khái niệm quan trọng trong lý thuyết đồ thị, cấu trúc dữ liệu và giải thuật. Cây là một đồ thị thỏa mãn các tính chất sau:
ã Có một đỉnh đặc biệt gọi là gốc.
ã Mỗi đỉnh B bất kỳ không phải là gốc, tồn tại duy nhất một đỉnh A có cung đi từ A đến B. Đỉnh A được gọi là đỉnh cha của B, đỉnh B được gọi là đỉnh con của A.
ã Có đường đi duy nhất từ gốc đến mỗi đỉnh của cây.
Một ví dụ quen thuộc về cây đó là cây thư mục hay trong thực tế, tập hợp các thành viên trong một dòng họ với quan hệ cha – con. Trừ ông tổ của dòng họ này, mỗi một người trong dòng họ là con của một người cha nào đó trong dòng họ. Biểu diễn dòng họ dưới dạng đồ thị hướng: quan hệ cha – con được biểu diễn bởi các cung của đồ thị, nếu A là cha của B, thì trong đồ thị có cung đi từ đỉnh A tới đỉnh B.
Cây được sử dụng rộng rãi trong rất nhiều vấn đề khác nhau. Chẳng hạn nó được áp dụng để tổ chức thông tin trong các hệ cơ sở dữ liệu, để mô tả cấu trúc cú pháp của các chương trình nguồn khi xây dựng các chương trình dịch. Rất nhiều các bài toán mà ta gặp trong các lĩnh vực khác nhau được quy về việc thực hiện các phép toán trên cây.
Trong thực tế thường hay gặp các bài toán liên quan cây nhị phân. Cây nhị phân là cây mà mỗi đỉnh có tối đa 2 nút con.
Trong nội dung đề tài này, chúng ta sẽ tìm hiểu về cây nhị phân tìm kiếm. Cây nhị phân tìm kiếm là cây nhị phân mà mỗi nút đều được gán một khóa, sao cho với mỗi nút k thì:
ã Mọi khóa trên cây con trái đều nhỏ hơn khóa trên nút k.
ã Mọi khóa trên cây con phải đều lớn hơn khóa trên nút k.