Bài giảng Cây - Tree

Bài 7: Cây - Tree Nội dung Các thuật ngữ cơ bản Các phép toán cơ bản trên cây Cài đặt cây Cây nhị phân ứng dụng Giới thiệu Tổ chức phân cấp (hierarchy) trên tập hợp các phần tử được dùng trong nhiều ngành khoa học khác nhau sơ đồ tổ chức bộ máy nhà nước từ trung ương xuống cơ sở như tỉnh, huyện, xã... tổ chức thông tin trong cơ sở dữ liệu, tổ chức chỉ mục, tổ chức các cấu trúc lưu trữ tri thức (knowledge) của các hệ chuyên gia (expert system)... Tìm hiểu các thuật ngữ cơ bản + một số phép toán chung nhất trên cây, các phép duyệt cây Cây nhị phân Giải thuật Huffman để mã hoá kí tự như là một ứng dụng của cây nhị phân. cây tìm kiếm nhị phân như là một ứng dụng lưu trữ và tìm kiếm dữ liệu dựa trên cấu trúc cây. 1. CÁC THUẬT NGỮ CƠ BẢN Cây là một tập hợp các phần tử gọi là nút (nodes) trong đó có một nút được phân biệt gọi là nút gốc (root). Trên tập hợp các nút này có một quan hệ → quan hệ cha - con (parenthood), xác định hệ thống cấu trúc trên các nút. nút, trừ nút gốc, có duy nhất một nút cha. Một nút có thể có nhiều nút con hoặc không có nút con nào. Mỗi nút biểu diễn một phần tử trong tập hợp đang xét và nó có thể có một kiểu nào đó bất kỳ biểu diễn nút bằng một kí tự, một chuỗi hoặc một số ghi trong vòng tròn. Mối quan hệ cha con được biễu diễn theo qui ước nút cha ở dòng trên nút con ở dòng dưới và được nối bởi một đoạn thẳng. Định nghĩa Định nghĩa cây một cách đệ qui như sau: Một nút là một cây. Nút này cũng chính là nút gốc của cây. Giả sử ta có n là một nút và k cây T1,.., Tk với các nút gốc tương ứng là n1,.., nk thì có thể tạo ra một cây mới bằng cách cho nút n là cha của các nút n1,.., nk. Cây mới này có nút gốc là nút n và các cây T1,.., Tk được gọi là các cây con. Tập rỗng cũng được coi là một cây và gọi là cây rỗng kí hiệu^. Ví dụ Ví dụ: xét mục lục của một quyển sách. Mục lục này có thể xem là một cây Một số khái niệm Nếu n1,.., nk là một dãy các nút trên cây sao cho ni là nút cha của nút ni+1, với i=1..k-1, thì dãy này gọi là một đường đi trên cây (đường đi ) từ n1 đến nk. Ðộ dài đường đi này được định nghĩa bằng số nút trên đường đi trừ 1. Độ dài đường đi từ một nút đến chính nó bằng không. Cây con. Từ định nghĩa cây ta có, mỗi đỉnh a bất kỳ của cây T là gốc của một cây nào đó, ta gọi cây này là cây con của cây T. Nó gồm đỉnh a và tất cả các đỉnh là hậu thế của a Một số khái niệm Nếu có đường đi từ nút a đến nút b thì ta nói a tiền thân của b, còn b gọi là hậu thế của nút a. Rõ ràng một nút vừa là tiền thân vừa là hậu duệ của chính nó. số các con của 1 nút gọi là cấp (degree) của nút đó Nút có cấp bằng 0 gọi là nút lá (leaf). Nút không phải là lá ta còn gọi là nút trong hay nút nhánh (interior, branch). Cấp cao nhất của nút trên cây gọi là cấp của cây độ cao của một đỉnh a là độ dài của đường đi dài nhất từ a đến một lá Độ cao của gốc được gọi là độ cao của cây Mức của đỉnh a là độ dài của đường đi từ gốc đến a. Như vậy gốc có mức 0 Các nút có cùng một độ sâu i ta gọi là các nút có cùng một mức i. +) Thứ tự các nút Nếu ta phân biệt thứ tự các nút con của cùng một nút thì cây gọi là cây có thứ tự, thứ tự qui ước từ trái sang phải. Như vậy, nếu kể thứ tự thì hai cây sau là hai cây khác nhau: Thứ tự… Trong trường hợp ta không phân biệt rõ ràng thứ tự các nút → cây không có thứ tự. Các nút con có cùng một cha gọi là các nút anh em ruột (siblings). Giả sử trong một cây được sắp T, đỉnh a có các con được sắp theo thứ tự : b1, b2, ..., bk (k  1). Khi đó ta nói b1 là con trưởng của a, và bi là anh liền kề của bi+1 (bi+1 là em liền kề của bi), i = 1,2, ..., k-1. Ta còn nói, với i value=v; n->leftmost_child=left; n->right_sibling=right; n->parent= nil; left->parent = n; right->parent=n; return n; } 3) Cây nhị phân Định nghĩa Cây nhị phân là một tập hợp hữu hạn các đỉnh được xác định đệ qui như sau. 1. Một tập trống là cây nhị phân 2. Giả sử T1 và T2 là hai cây nhị phân không cắt nhau (T1T2 = ) và r là một đỉnh mới không thuộc T1, T2. Khi đó ta có thể thành lập một cây nhị phân mới T với gốc r có T1 là cây con bên trái, T2 là cây con bên phải của gốc. Tính chất Cây nhị phân là cây rỗng hoặc là cây mà mỗi nút chỉ có tối đa hai nút con. Nút con của cây được phân biệt thứ tự rõ ràng, cây con trái và cây con phải. Cây có thứ tự 3) Cây nhị phân … Cây nhị phân suy biến (thực chất là một ds tuyến tính – degenerate binary tree) Cây lệch trái, lệch phải, zic-zac Cây nhị phân hoàn chỉnh, đầy đủ NX: các cây nhị phân có cùng số lượng nút: Cây suy biến có chiều cao lớn nhất Cây hoàn chỉnh có chiều cao nhỏ nhất-cân đối b) Tính chất số lượng tối đa các nút ở mức i trên 1 cây nhị phân là 2i-1 (i≥1) số lượng tối đa các nút trên 1 cây nhị phân có chiều cao h là 2h-1 (h≥1) CMinh Quy nạp 20 + 21 + 22 +… + 2h-1=2h – 1 Cây nhị phân hoàn chỉnh n nút → chiều cao? c) Biểu diễn Bằng mảng Con của nút thứ i là nút 2i và 2i+1 Cha của j là [j/2] Cây kô đầy đủ → lãng phí Thao tác loại bỏ và bổ sung → khó khăn Lưu trữ móc nối Lptr: trỏ tới cây con trái của nút đó Rptr: trỏ tới cây con phải của nút đó Ứng dụng Biểu diễn biểu thức Cây quyết định Mã hóa huffman Biểu diễn biểu thức Phép toán 2 ngôi → hoàn toàn tự nhiên Phép toán một ngôi → quy ước Duyệt theo thứ tự trước: biểu thức tiền tố Duyệt theo thứ tự sau: biểu thức hậu tố Duyệt theo thứ tự giữa: biểu thức trung tố Vấn đề: Tính toán giá trị biểu thức Nối hai cây biểu thức để được biểu thức mới Cây quyết định Biểu diễn lời giải của bài toán Mã hóa Huffman Giả sử ta có thông báo là chuỗi các kí tự, mỗi kí tự xuất hiện độc lập với cùng một xác suất tại bất kỳ vị trí nào trong thông báo. Mã hoá chuỗi thông báo này thành một chuỗi các bít 0,1. đảm bảo có thể giải mã trở lại được chuỗi thông báo ban đầu. Lưu ý phương pháp mã hoá phải ko thoả mãn tính chất tiền tố: mã hoá của mỗi kí tự không được là tiền tố của chuỗi mã hoá của kí tự khác a được mã 10, b được mã 1011 là không thể được tiết kiệm nhất mã hoá trên là hợp lệ cách mã hoá 2 cho độ dài trung bình mã 2.24 (vì 3*0.10 + 2*0.40 + 2*0.12 + 3*0.18 + 2* 0.20 = 2.24) Có cách mã hoá nào cho độ dài mã trung bình nhỏ hơn 2.24 không? Giải thuật huffman Lập cây nhị phân từ tập các kí hiệu trong thông báo, mỗi kí hiệu là một nút lá của cây. Chọn hai nút a,b có xác suất nhỏ nhất trong tập hợp các nút (P(a)  P(b) → cây nhị phân có nút gốc x, con trái là a, con phải là b. P(x)=P(a)+P(b) Lặp lại một cách đệ qui quá trình trên tập các nút còn lại cho đến khi tập này chỉ còn lại một nút. Mã của a, b sẽ tìm được bằng cách lấy mã của x nối thêm 0 cho a và 1 cho b. Mã của nút gốc là rỗng. xây dựng một cây nhị phân có lá là các ký tự muốn mã hoá Mã của một ký tự là một đường đi trên cây từ gốc đến lá chứa kí tự, với 0 đi sang trái còn 1 đi sang phải. Đảm bảo yêu cầu tiết kiệm kô? Ví dụ: xét tập hợp các kí tự với xác xuất được cho trong bảng trên ta có Bước khởi đầu ta có 5 nút với xác xuất như sau: a b c d e .10 .40 .12 .18 .20 hai nút a và c có xác suất nhỏ nhất vậy ta kết hợp hai nút này lại ta có Kế đến ta thấy hai nút d và e có sác xuất nhỏ nhất trong tập hợp trên nên ta kết hợp chúng lại ta được Tiếp tục ta kết hợp hai nút có xác suất bé nhất lại, ta được Bây giờ tập hợp chỉ còn hai nút ta kết hợp hai nút này lại và giải thuật kết thúc. CÂY TÌM KIẾM NHỊ PHÂN (BINARY SEARCH TREES) 1.Định nghĩa           2.Cài đặt cây tìm kiếm nhị phân           3.Các giải thuật trên cây tìm kiếm nhị phân    Định nghĩa Cây tìm kiếm nhị phân (TKNP) là cây nhị phân mà khoá tại mỗi nút của cây lớn hơn khoá của tất cả các nút thuộc cây con bên trái và nhỏ hơn khoá của tất cả các nút thuộc cây con bên phải. Lưu ý: dữ liệu lưu trữ tại mỗi nút có thể rất phức tạp như là một record chẳng hạn, trong trường hợp này khoá của nút được tính trường khoá. Trường khoá phải chứa các giá trị có thể so sánh được, tức là nó phải lấy giá trị từ một tập hợp có thứ tự. Ví dụ: hình minh hoạ một cây TKNP có khoá là số nguyên (với quan hệ thứ tự trong tập số nguyên). Qui ước: Cũng như tất cả các cấu trúc khác, ta coi cây rỗng là cây TKNP Nhận xét: Trên cây TKNP không có hai nút cùng khoá. Cây con của một cây TKNP là cây TKNP. Khi duyệt thứ tự giữa (InOrder) cây TKNP ta được một dãy có thứ tự tăng. Ví dụ duyệt thứ tự giữa cây trên ta có dãy: 5, 10, 15, 17, 20, 22, 30, 35, 42. Cài đặt cây tìm kiếm nhị phân Cây TKNP, là một cây nhị phân. có thể áp dụng các cách cài đặt như đã trình bày trong phần cây nhị phân không khác biệt trong việc cài đặt cấu trúc dữ liệu cho cây TKNP so với cây nhị phân khác biệt trong các giải thuật thao tác trên cây TKNP như tìm kiếm, thêm hoặc xoá một nút trên cây TKNP để luôn đảm bảo tính chất cuả cây TKNP. Một cách cài đặt cây TKNP thường gặp là cài đặt bằng con trỏ. Mỗi nút của cây như là một mẩu tin (record) có ba trường: một trường chứa khoá, hai trường kia là hai con trỏ trỏ đến hai nút con (nếu nút con vắng mặt ta gán con trỏ bằng NIL) Cấu trúc dữ liệu như sau #define KeyType kiểu dữ liệu của khoá struct _record{ KeyType Key; TREE Left,Right; }; typedef struct _record record; record *node Khởi tạo cây TKNP rỗng Ta cho con trỏ quản lý nút gốc (Root) của cây bằng NIL. void MakeNullTree(TREE *Root) { Root = NULL; } Các giải thuật trên cây TKNP Tìm kiếm một nút có khoá cho trước trên cây TKNP Thêm một nút có khoá cho trước vào cây tìm kiếm nhị phân Xoá một nút có khoá cho trước trên cây tìm kiếm nhị phân Tìm kiếm một nút có khoá cho trước trên cây TKNP Ðể tìm kiếm 1 nút có khoá x trên cây TKNP, ta tiến hành từ nút gốc bằng cách so sánh khoá cuả nút gốc với khoá x. Nếu nút gốc bằng NIL thì không có khoá x trên cây. Nếu x bằng khoá của nút gốc thì giải thuật dừng và ta đã tìm được nút chứa khoá x. Nếu x lớn hơn khoá của nút gốc thì ta tiến hành (một cách đệ qui) việc tìm khoá x trên cây con bên phải. Nếu x nhỏ hơn khoá của nút gốc thì ta tiến hành (một cách đệ qui) việc tìm khoá x trên cây con bên trái. Ví dụ: tìm nút có khoá 30 trong cây ở trong hình trên So sánh 30 với khoá nút gốc là 20, vì 30 > 20 vậy ta tìm tiếp trên cây con bên phải, tức là cây có nút gốc có khoá là 35. So sánh 30 với khoá của nút gốc là 35, vì 30 22 vậy ta tìm kiếm trên cây con bín phải, tức là cây có nút gốc có khoá là 30. So sánh 30 với khoá nút gốc là 30, 30 = 30 vậy đến đây giải thuật dừng và ta tìm được nút chứa khoá cần tìm. Hàm dưới đây trả về kết quả là con trỏ trỏ tới nút chứa khoá x hoặc NIL nếu không tìm thấy khoá x trên cây TKNP Tree Search(KeyType x, Tree Root) { if Root == NULL {không tìm thấy khoá x} Search = NULL; else if Root->Key == x then {tìm thấy khoá x} Search = Root; else if Root->Key Right) else {tìm tiếp trên cây bên trái} Search = Search(x, Root->Left) } Nhận xét: giải thuật này sẽ rất hiệu quả về mặt thời gian nếu cây TKNP được tổ chức tốt, nghĩa là cây tương đối "cân bằng". Cây cân bằng – nói đến sau Thêm một nút có khoá cho trước vào CTKNP Muốn thêm một nút có khoá x vào cây TKNP tìm kiếm để xác định có nút nào chứa khoá x chưa. Nếu có thì giải thuật kết thúc (không làm gì cả!). sẽ thêm một nút mới chứa khoá x này. phải đảm bảo cấu trúc cây TKNP không bị phá vỡ. Giải thuật cụ thể như sau Ta tiến hành từ nút gốc bằng cách so sánh khoá cuả nút gốc với khoá x. Nếu nút gốc bằng NULL thì khoá x chưa có trên cây, do đó ta thêm một nút mới chứa khoá x. Nếu x bằng khoá của nút gốc thì giải thuật dừng, trường hợp này ta không thêm nút. Nếu x lớn hơn khoá của nút gốc thì ta tiến hành (một cách đệ qui) giải thuật này trên cây con bên phải. Nếu x nhỏ hơn khoá của nút gốc thì ta tiến hành (một cách đệ qui) giải thuật này trên cây con bên trái. Ví dụ: thêm khoá 19 vào cây ở trong hình III.15 So sánh 19 với khoá của nút gốc là 20, vì 19 10 vậy ta xét tiếp đến cây bên phải, tức là cây có nút gốc có khoá là 17. So sánh 19 với khoá của nút gốc là 17, vì 19 > 17 vậy ta xét tiếp đến cây bên phải. Nút con bên phải bằng NULL, chứng tỏ rằng khoá 19 chưa có trên cây, ta thêm nút mới chứa khoá 19 và nút mới này là con bên phải của nút có khoá là 17 Thủ tục sau đây tiến hành việc thêm một khoá vào cây TKNP. void InsertNode(keyType x, TREE *A); { If A == NULL { {thêm nút mới chứa khoá x} new(A); A->Key = x; A->Left = NIL; A->Right = NIL; } else if x Key InsertNode(x, A^.Left) else if x > A->Key InsertNode(x,A^.Right) } Xoá một nút có khoá cho trước trên cây tìm kiếm nhị phân xoá một nút có khoá x, tìm kiếm nút chứa khoá x trên cây. ta phải bảo đảm cấu trúc cây TKNP không bị phá vỡ. Ta có các trường hợp sau: các trường hợp có thể xảy ra khi xoá một nút Nếu không tìm thấy nút chứa khoá x thì giải thuật kết thúc. Nếu tìm gặp nút N có chứa khoá x, ta có ba trường hợp sau Nếu N là lá ta thay nó bởi NIL. N chỉ có một nút con ta thay nó bởi nút con của nó. N có hai nút con ta thay nó bởi nút lớn nhất trên cây con trái của nó (nút cực phải của cây con trái ) hoặc là nút bé nhất trên cây con phải của nó (nút cực trái của cây con phải). Trong giải thuật sau, ta thay x bởi khoá của nút cực trái của cây con bên phải rồi ta xoá nút cực trái này. Việc xoá nút cực trái của cây con bên phải sẽ rơi vào một trong hai trường hợp trên. Giải thuật xoá một nút có khoá nhỏ nhất Hàm dưới đây trả về khoá của nút cực trái, đồng thời xoá nút này. KeyType DeleteMin(TREE *A) { if A->Left == NULL then { DeleteMin = A->Key; A = A->Right; } else DeleteMin = DeleteMin(A->Left); end; Thủ tục xóa một nút có khoá cho trước trên cây TKNP void DeleteNode(key X, TREE A) { if A != NULL if x Key DeleteNode(x, A->left) ; else if x > A->Key DeleteNode(x, A->right) ; else if (A->Left == NULL) && (A->Right == NULL) A= NULL; else if (A->Left = NIL) then A = A->Right ; else if A->Right = NIL then A = A->Left; else A->Key = DeleteMin(A->Right); }