›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 11: Cây đa phân

*Định nghĩa

*Cây đa phân

*Cây rỗng

*Hoặc có một node gọi là gốc (root) và nhiều cây con.

*Biểu diễn:

*Mỗi node gồm có nhiều nhánh con

*Mỗi node có 2 liên kết first_child và next_sibling

*Dùng cây nhị phân

Thiết kế Trie

class Trie {

public: // Add method prototypes here.

private: // data members

    Trie_node *root;

};

const int num chars = 28;

struct Trie_node {

    // data members

    Record *data;

    Trie_node *branch[num_chars];

    // constructors

    Trie_node( );

};

ppt 25 trang thiennv 07/11/2022 2800
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 11: Cây đa phân", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.

File đính kèm:

  • pptbai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_11_cay_da_ph.ppt

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 11: Cây đa phân

  1. Đánh giá trie Tìm kiếm: Lần so sánh = chiều dài khóa Từ điển tiếng Anh 100.000 từ, chiều dài tối đa 15 ký tự: Trie: Số lần so sánh tối đa = 15 Tìm nhị phân = k*lg (100.000) = 17k (k: chiều dài trung bình của từ tiếng Anh) 11 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 11. Cây đa phân
  2. Cây đa phân tìm kiếm Cây đa phân tìm kiếm bậc m: mỗi node có tối đa m nhánh con 12 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 11. Cây đa phân
  3. Cây đa phân cân bằng (B-tree) Một B-tree bậc m là một cây đa phân tìm kiếm bậc m: 1. Tất cả các node lá ở cùng một mức. 2. Tất cả các node trung gian trừ node gốc có tối đa m nhánh con và tối thiểu m/2 nhánh con (khác rỗng). 3. Số khóa của mỗi node trung gian ít hơn một so với số nhánh con và phân chia các khóa trong các nhánh con theo cách của cây tìm kiếm. 4. Node gốc có tối đa m nhánh con, tối thiểu là 2 nhánh con khi node gốc không là node lá hoặc không có nhánh con khi cây chỉ có node gốc. 13 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 11. Cây đa phân
  4. Ví dụ B-tree B-tree bậc 4 14 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 11. Cây đa phân
  5. Thiết kế B-tree template class B_tree { public: // Add public methods. private: // data members B_node *root; // Add private auxiliary functions here. }; template struct B_node { // data members: int count; Record data[order − 1]; B_node *branch[order]; // constructor: B_node( ); }; 15 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 11. Cây đa phân
  6. Giải thuật tìm kiếm trên B-tree Algorithm search_B_tree Input: subroot là gốc của cây và target là khóa cần tìm Output: dữ liệu tìm thấy 1. if (cây rỗng) 1.1. return not_present 2. else 2.1. Tìm target trên dữ liệu của subroot 2.2. if (tìm thấy) 2.2.1. return dữ liệu tìm thấy 2.3. else //Tìm không thấy sẽ ngừng tại vị trí có khóa vừa lớn hơn khóa cần //tìm, ở đó có liên kết đến nhánh con gồm các khóa nhỏ hơn nó. 2.3.1. Nhảy đến nhánh con của vị trí không tìm thấy 2.3.1. Call search_B_tree với nhánh con mới End search_B_tree 16 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 11. Cây đa phân
  7. Mã C++ tìm kiếm trên B-tree template Error_code B_tree :: recursive_search_tree (B_node *current, Record &target) { Error_code result = not_present; int position = 0; if (current != NULL) { while (position count && target > current->data[position]) position++; if (position count && target == current->data[position]) result = success; if (result == not_present) result =recursive_search_tree(current->branch[position], target); else target = current->data[position]; } return result; } 17 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 11. Cây đa phân
  8. Thêm vào B-tree 18 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 11. Cây đa phân
  9. Thêm vào B-tree (tt.) 19 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 11. Cây đa phân
  10. Thêm vào B-tree (tt.) 20 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 11. Cây đa phân
  11. Thêm vào B-tree (tt.) 21 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 11. Cây đa phân
  12. Xóa giá trị trên B-tree 22 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 11. Cây đa phân
  13. Xóa giá trị trên B-tree (tt.) 23 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 11. Cây đa phân
  14. Xóa giá trị trên B-tree (tt.) 24 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 11. Cây đa phân
  15. Xóa giá trị trên B-tree (tt.) 25 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 11. Cây đa phân