tailieunhanh - Cấu trúc dữ liệu và giải thuật (phần 2)

Trong tài liệu nay một số kiến thức toán học cần thiết sẽ được nhắc lại để đáp ứng cho môn học này, các cơ sở toán học cũng khá cơ bản, có đề cập đến cây nhị phân | Ộ UNIVERSITY Cơ sở toán học 1. Cận trên cận dưới LxJ - Giá trị nguyên lớn nhất nhỏ hơn hoặc bằng X. Ví dụ 2 -8 -Xq Giá trị nguyên nhỏ nhất lớn hơn hoặc bằng X. . Ví dụ 3 -7 2. Logarithms Giải thuật tăng chậm hơn sự tăng N log2N lgN log 0N logN X Y logBX logBY Ộ UNIVERSITY Cơ sở toán học logB1 0 l gpB l logB X Y logBX logBY logBXY Y logßX logAX logBX logBA 3. Cây nhị phân Khái niệm Cây nhị phân là cây mà mỗi nút có tối đa 2 cây con Ộ UNIVERSITY Cơ sở toán học Bậc của cây - Cây nhị phân có N nút Số bậc ít nhất LlgNJ Số bậc tối đa N-1 - Ví dụ Cây nhị phân có 15 nút có ít nhất là Llg15J 3 bậc - Ở bậc K có 2K .