zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Cây tổng quát

Chia sẻ: Hai Hoang | Ngày: | Loại File: PDF | Số trang:77

Báo xấu

848
lượt xem 63
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong chương này chúng ta sẽ nghiên cứu mô hình dữ liệu cây (tree). Cây là một cấu trúc phân cấp trên một tập hợp nào đó các đối tượng. Một ví dụ quen thuộc về cây, đó là cây thư mục hoặc mục lục của cuốn sách cũng là một cây. Cây được sử dụng rộng rãi trong rất nhiều vấn đề khác nhau.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Cây tổng quát

Giáo trình - Cấu trúc dữ liệu và Giải thuật Bài 21: CÂY TỔNG QUÁT Trong chương này chúng ta sẽ nghiên cứu mô hình dữ liệu cây (tree). Cây là một cấu trúc phân cấp trên một tập hợp nào đó các đối tượng. Một ví dụ quen thuộc về cây, đó là cây thư mục hoặc mục lục của cuốn sách cũng là một cây. 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 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 chương này chúng ta sẽ trình bày định nghĩa, các khái niệm cơ bản về cây. Chúng ta cũng sẽ xét các phương pháp cài đặt cây và thực hiện các phép toán cơ bản trên cây. Sau đó ta nghiên cứu kỹ một số dạng cây đặc biệt đó là cây nhị phân tìm kiếm và cây cân bằng. 21.1. Định nghĩa Định nghĩa 1: Một cây là tập hợp hữu hạn các nút trong đó có một nút đặc biệt gọi là gốc (root). Giữa các nút có một quan hệ phân cấp gọi là "quan hệ cha con". Định nghĩa 2: Cây được định nghĩa đệ qui như sau 1. Một nút là một cây và nút này cũng là gỗc của cây. 2. Giả sử T1, T2, …,Tn (n ≥ 1) là các cây có gốc tương ứng r1, r2,…, rn. Khi đó cây T với gốc r được hình thành bằng cách cho r trở thành nút cha của các nút r1, r2,…, rn 21.2. Các khái niệm về cây Bậc của một nút: là số con của nút đó Bậc của một cây: là bậc lớn nhất của các nút có trên cây đó (số cây con tối đa của một nút thuộc cây). Cây có bậc n thì gọi là cây n - phân nút gốc: là nút có không có nút cha Nút lá: là nút có bậc bằng 0 Nút nhánh: là nút có bậc khác 0 và không phải là nút gốc Mức của một nút Mức (gốc (T0)) =1 Gọi T1, T2,..., Tn là các cây con của T0. Khi đó Mức (T1) = Mức (T2) = ... = Mức (Tn) = Mức (T0) +1 Chiều cao của cây: là số mức lớn nhất có trên cây đó Đường đi: Dãy các đỉnh n1, n2, ...,nk được gọi là đường đi nếu ni là cha của ni+1 (1 ≤ i ≤ k- 1 Độ dài của đường đi: là số nút trên đường đi -1 Cây được sắp : Trong một cây, nếu các cây con của mỗi đỉnh được sắp theo một thứ nhất định, thì cây được gọi là cây được sắp (cây có thứ tự). Chẳng hạn, hình minh hoạ hai cây được sắp khác nhau A A B C C B Khoa CNTT- Trường ĐHSPKT Hưng Yên 1
Giáo trình - Cấu trúc dữ liệu và Giải thuật Hình 5.1. Hai cây được sắp khác nhau Rừng: là tập hợp hữu hạn các cây phân biệt A G O B C M N D E hình 5.2. Rừng gồm ba cây 21.3. Phép duyệt cây tổng quát Trong khoa học máy tính, duyệt cây là việc lần lượt viếng thăm các đỉnh của cây theo một thứ tự nào đó. Các cây nói trong bài này là cây có gốc. Định nghĩa phép duyệt cây như sau: 1) Sự nhất quán về thứ tự các nút được thăm giữa phép duyệt cây tổng quát và phép duyệt cây nhị phân tương đương của nó 2) Sự nhất quán giữa định nghĩa phép định nghĩa phép duyệt cây tổng quát với định nghĩa phép duyệt cây nhị phân. Vì cây nhị phân cũng có thể coi là cây tổng quát và ta có thể áp dụng định nghĩa phép duyệt cây tổng quát cho cây nhị phân. Ta có thể xây dựng được định nghĩa của phép duyệt cây tổng quát T như sau Duyệt theo thứ tự trước a) nếu T rỗng thì không làm gì b) Nếu T khác rỗng thì Thăm gốc của T Duyệtcác cây con thứ nhất T1 của gốc của cây T theo thứ tự trước Duyệt các cây con còn lại T2, T3,...,Tn của gốc T theo thứ tự trước Duyệt theo thứ tự giữa a) Nếu T rỗng thì không làm gì b) Nếu T khác rỗng thì Duyệtcác cây con thứ nhất T1 của gốc của cây T theo thứ tự giữa Thăm gốc của T Duyệt các cây con còn lại T2, T3,...,Tn của gốc T theo thứ tự giữa Tuy nhiên người ta ít xem xét việc duyệt trung thứ tự của cây tổng quát Duyệt theo thứ tự sau a) Nếu T rỗng thì không làm gì b) Nếu T khác rỗng thì Duyệtcác cây con thứ nhất T1 của gốc của cây T theo thứ tự sau Duyệt các cây con còn lại T2, T3,...,Tn của gốc T theo thứ tự sau Thăm gốc của T ví dụ với cây ở hình vẽ 5.17 Khoa CNTT- Trường ĐHSPKT Hưng Yên 2
Giáo trình - Cấu trúc dữ liệu và Giải thuật A B C D E F G H I J Hình 5.17 Thì dãy tên các nút được thăm sẽ là Thứ tự trước: ABCEHIFJDg Thứ tự giữa : BAhEICJFGD Thứ tự sau : BHIEJFCGDa Bây giờ ta dựng cây nhị phân tương đương với cây tổng quát ở hình 5.17 A B C E D H F G I J Hình 5.18. Cây nhị phân tương đương Dãy các nút được thăm khi duyệt nó theo phép duyệt của cây nhị phân: Thứ tự trước: ABCEHIFJDG Thứ tự giữa: BHIEJFCGDA Thứ tự sau: I H JF E G D C B A Duyệt theo mức Một phương pháp duyệt cây khác là duyệt theo mức. Bắt đầu duyệt từ gốc (đỉnh mức 0), rồi duyệt các con của gốc từ trái sang phải (các đỉnh mức 1), tiếp đến là các đỉnh mức 2,... 21.4. Cài đặt cây tổng quát Có nhiều phương pháp biểu diễn cây. Cách thường dùng nhất là biểu diễn mỗi nút như một dữ liệu kiểu bản ghi, mỗi nút chứa các con trỏ tới các con hoặc cha của nó, hoặc cả hai. Cây cũng có thể biểu diễn bằng các mảng cùng với quan hệ giữa các vị trí trong mảng. Khoa CNTT- Trường ĐHSPKT Hưng Yên 3
Giáo trình - Cấu trúc dữ liệu và Giải thuật Khi biểu diễn cấu trúc cây tổng quát, vì mỗi nút có thể có nhiều con, số con có thể khác nhau, nên ta không dùng cho mỗi nút con một liên kết đến nút cha mà với mỗi nút vẫn chỉ dành hai liên kết, một liên kết (trường Child) trỏ đến nút con đầu bên trái của nó, một liên kết (trường Next)trỏ đến nút cùng cha kề bên phải nó. Nếu coi liên kết trường Child như liên kết Left, liên kết Next như liên kết Right ta có một cây nhị phân tương đương với cây tổng quát. Ví dụ • Cây tổng quát A /|\ B C D /\ | E F G • Cây nhị phân tương đương A / B / \ E C \ \ F D / G • Lưu trữ của cây tổng quát như sau Root=A A.Value="A",A.Child=B,A.Next=Null B.Value="B",B.Child=E,B.Next=C C.Value="C",C.Child=Null,C.Next=D D.Value="D",D.Child=G,D.Next=Null E.Value="E",E.Null,E.Next=F F.Value="F",F.Child=Null,F.Next=Null G.Value="G",D.Child=Null,G.Next=Null Khoa CNTT- Trường ĐHSPKT Hưng Yên 4
Giáo trình - Cấu trúc dữ liệu và Giải thuật Bài 22: CÂY NHỊ PHÂN 22.1. Định nghĩa, tính chất Định nghĩa: Cây nhị phân là cây mà mỗi nút có tối đa hai cây con. Đối với cây con của một nút người ta cũng phân biệt cây con trái và cây con phải. Như vậy cây nhị phân là cây có thứ tự. A A A B B B C C D C D C D E E E Hình 5.3. Một số cây nhị phân Tính chất: Đối với cây nhị phân cần chú ý tới một số tính chất sau i) Số lượng tối đa các nút có ở mức i trên cây nhị phân là 2i -1 (i ≥ 1) ii) Số lượng nút tối đa trên một cây nhị phân có chiều cao h là 2h-1(h ≥ 1 ) Chứng minh i) Sẽ được chứng minh bằng qui nạp Bước cơ sở: với i = 1, cây nhị phân có tối đa 1 = 20 nút.Vậy mệnh đề đúng với i = 1 Bước qui nạp: Giả sử kết quả đúng với mức i, nghĩa là ở mức này cây nhị phân có tối đa 2i - 1 nút, ta chứng minh mệnh đề đúng với mức i + 1. Theo định nghĩa cây nhị phân thì tại mỗi nút có tối đa hai cây con nên mỗi nút ở mức i có tối đa hai con. Do đó theo giả thiết qui nạp ta suy ra tại mức i+ 1 ta có 2i - 1x 2 = 2i nút. ii) Ta đã biết rằng chiều cao của cây là số mức lớn nhất có trên cây đó. Theo i) ta suy ra số nút tối đa có trên cây nhị phân với chiều cao h là : 20 + 21 + ... + 2h-1 = 2h -1. Từ kết quả này có thể suy ra: Nếu cây nhị phân có n nút thì chiều cao của no là h = ⎡log2(n + 1)⎤ (Ta qui ước : ⎡x⎤ là số nguyên trên của x ⎣x⎦ là số nguyên dưới của x ) 22.2. Phép duyệt cây nhị phân Khi xét một cây nhị phân, mỗi đỉnh cùng với các đỉnh đứng sau nó là gốc của một cây con. Ta xét một đỉnh A là đỉnh trong của cây nhị phân. Theo thứ tự người ta xem xét thứ tự thăm đỉnh A so với việc thăm hai con của nó là thăm A trước rồi 2 con sau, thăm A xen giữa việc thăm hai con, thăm A sau thi thăm hai con: • A, con trái, con phải • Con trái, A, con phải • Con trái, con phải, A Khoa CNTT- Trường ĐHSPKT Hưng Yên 5
Giáo trình - Cấu trúc dữ liệu và Giải thuật Tất nhiên nếu không có con nào thì việc thăm con ấy không diễn ra. Còn nếu con L hoặc con R của A lại là gốc của một cây con, thì việc thăm thay bằng việc duyệt cây con có gốc tại đó. Từ đó có các phương pháp duyệt tiền thứ tự, trung thứ tự, hậu thứ tự đối với cây nhị phân có gốc tại đỉnh A như sau Duyệt tiền thứ tự cây con gốc A • Nếu Cây là rỗng Return • Thăm A • Duyệt tiền thứ tự cây con gốc L • Duyệt tiền thứ tự cây con gốc R Duyệt trung thứ tự cây con gốc A • Nếu Cây là rỗng Return • Duyệt trung thứ tự cây con gốc L • Thăm A • Duyệt trung thứ tự cây con gốc R Duyệt hậu thứ tự cây con gốc A • Nếu Cây là rỗng Return • Duyệt hậu thứ tự cây con gốc L • Duyệt hậu thứ tự cây con gốc R • Thăm A Ví dụ Giả sử có cây nhị phân sau A / \ B C /\ / \ D EF G • Duyệt tiền thứ tự với cây này diễn ra tuần tự như sau 1. Thăm A, Duyệt cây gốc B, Duyệt cây gốc C 2. Thăm A, Thăm B, Thăm D, Thăm E, Thăm C, Thăm F, Thăm G • Duyệt trung thứ tự với cây này diễn ra tuần tự như sau 1. Duyệt cây gốc B, Thăm A, Duyệt cây gốc C 2. Thăm D, Thăm B, Thăm E, Thăm A, Thăm F, Thăm C, Thăm G • Duyệt hậu thứ tự với cây này diễn ra tuần tự như sau 1. Duyệt cây gốc B, Duyệt cây gốc C, Thăm A 2. Thăm D, Thăm E, Thăm B, Thăm F, Thăm G, Thăm C, Thăm A Khoa CNTT- Trường ĐHSPKT Hưng Yên 6
Giáo trình - Cấu trúc dữ liệu và Giải thuật Giả mã Giả sử có một cây nhị phân mà cấu trúc mỗi nút của nó chứa một giá trị value và các tham chiếu left và right trỏ tới hai con của nút đó. Ta có thể viết các hàm sau: Duyệt tiền thứ tự (pre-order (prefix) traversal) visit(node) print node.value if node.left != null then visit(node.left) if node.right != null then visit(node.right) Duyệt hậu thứ tự (post-order (postfix) traversal) visit(node) if node.left != null then visit(node.left) if node.right != null then visit(node.right) print node.value Duyệt trung thứ tự (in-order (infix) traversal) visit(node) if node.left != null then visit(node.left) print node.value if node.right != null then visit(node.right) 22.3. Cài đặt cây nhị phân Cây nhị phân là một cấu trúc bao gồm các phần tử (nút) được kết nối với nhau theo quan hệ “cha-con” với mỗi cha có tối đa 2 con. Để biểu diễn cây nhị phân ta chọn phương pháp cấp phát liên kết. Ứng với một nút, ta dùng một biến động lưu trữ các thông tin: - Thông tin lưu trữ tại nút. - Địa chỉ nút gốc của cây con trái trong bộ nhớ. - Địa chỉ nút gốc của cây con phải trong bộ nhớ. Khai báo tương ứng trong ngôn ngữ C có thể như sau: typedef struct tagTNODE Khoa CNTT- Trường ĐHSPKT Hưng Yên 7
Giáo trình - Cấu trúc dữ liệu và Giải thuật { Data Key;//Data là kiểu dữ liệu ứng với thông tin lưu tại nút struct tagNODE *pLeft, *pRight; }TNODE; typedef TNODE *TREE; Do tính chất mềm dẻo của cách biểu diễn bằng cấp phát liên kết, phương pháp này được dùng chủ yếu trong biểu diễn cây nhị phân. Từ đây trở đi, khi nói về cây nhị phân, chúng ta sẽ dùng phương pháp biểu diễn này. Khoa CNTT- Trường ĐHSPKT Hưng Yên 8
Giáo t trình - Cấu tr dữ liệu và Giải thuật rúc v Bài 23 Thảo luận về cây 3: n 23.1. C loại câ thường gặp Các ây g 23.3.1 Cây nhị p 1 phân tìm ki iếm Định nghĩa Cây tì kiếm ứng với n khó k1,k2,...kn là cây nhị p ìm óa phân mà m nút đều được gán m mỗi đ một khóa s cho với mỗi mỗi nú k: sao i út • Mọi khóa trên cây co trái đều n hơn khó trên nút k on nhỏ óa • Mọi khóa trên cây co phải đều lớn hơn kh trên nút k on hóa Dưới đ là một ví dụ về câ nhị phân tìm kiếm: đây ây Nhận xét Cây tì kiếm nhị phân là một cấu trúc dữ liệu cơ bản được sử dụng để xây dựng cá cấu ìm ị m b ử x ác trúc dữ liệu trừu tượng hơn n các tập hợp, đa tập hợp, các d kết hợp ữ như p p dãy p. Nếu m BST có chứa các g trị giống nhau thì nó biểu diễn một đa tập hợp. Cây l một giá g ó n p loại này sử dụng các b đẳng th không n ử bất hức nghiêm ngặt Mọi nút tr t. rong cây co trái có kh on hóa nhỏ hơ khóa của nút cha, mọi nút trên cây con ph có nút lớ hơn hoặc bằng khóa của ơn a m n hải ớn nút ch ha. Nếu m BST kh một hông chứa c giá trị gi các iống nhau th nó biểu d một tập hợp đơn t như hì diễn p trị trong lý thuyết tậ hợp. Cây loại này sử dụng các bất đẳng th nghiêm ngặt. Mọi n ập y ử hức nút trong cây con trái có khóa n hơn khó của nút c mọi nút trên cây co phải có n lớn nhỏ óa cha, t on nút hơn kh của nút cha. hóa t Việc chọn đưa cá giá trị bằ nhau và cây con phải (hay trá là tùy th mỗi ngư c ác ằng ào p ái) heo ười. Một số người cũn đưa các giá trị bằng nhau vào c hai phía, nhưng khi đó việc tim kiếm ố ng g cả , m trở nên phức tạp hơn. Kh CNTT T ờ ĐHSP PKT H Y Yê 9
Giáo trình - Cấu trúc dữ liệu và Giải thuật Nhờ ràng buộc về khóa trên BST, việc tìm kiếm trở nên có định hướng. Hơn nữa, do cấu trúc cây việc tìm kiếm trở nên nhanh đáng kể. Nếu số nút trên cây là N thì chi phí tìm kiếm trung bình chỉ khoảng log2N. Trong thực tế, khi xét đến cây nhị phân chủ yếu người ta xét BST. Chúng ta sẽ trở lại vấn đề này trong phần tìm kiếm 23.1.2. Cây cân bằng hoàn toàn (CCBHT) Định nghĩa: Cây cân bằng hoàn toàn là câynhị phân tìm kiếm mà tại mỗi nút của nó, số nút của cây con trái và cây con phải không chênh lệch nhau qúa một. Một cây rất khó đạt được trạng thái cân bằng hoàn toàn và cũng rất dễ mất cân bằng vì khi thêm hay huỷ các nút trên cây có thể làm mất cân bằng (xác suất rất lớn), chi phí cân bằnglại cây là rất lớn vì phải thao tác trên toàn bộ cây. Tuy nhiên nếu cây cân đối thì việc tìm kiếm sẽ rất nhanh. Đối với CCBHT, trong trường hợp xấu nhất ta cũng chỉ phải tìm qua log2n phần tử (n là số nút trên cây) Sau đây là ví dụ về một CCBHT 25 90 2 30 5 Hình 5.25. Cây cân bằng hoàn toàn CCBHT có n nút, có chiều cao h = log2n. Đây chínhlà lý do cho phép đảm bảo khả năng tìm kiếm nhanh trên cấu trúc dữ liệu này. Do CCBHT là một cấu trúc kém ổn định nên trong thực tế không thể sử dụng. Nhưng ưu điểm của nó lại rất quan trọng. V ì vậy, cần đưa ra một cấu trúc dữ liệu khác có đặc tính giống CCBHT nhưng ổn định hơn. Như vậy, cần tìm cách tổ chức một cây đạt trạng thái cân bằng yếu hơn và việc cân bằng lại chỉ xảy ra ở phạm vi cục bộ nhưng vẫn đảm bảo chi phí cho thao tác tìm kiếm đạt ở mức O(log2n). 23.1.3 Cây cân bằng Năm 1962, P.M. ADELSON - VELSKI và E.LANDIS đã mở đầu phương hướng giải quyết này bằng cách đưa ra dạng cây cân đối mới mà sau này mang tên của họ, đó là cây nhị phân cân đối AVL. Từ nay về sau, chúng ta sẽ dùng thuật ngữ cây AVL thay cho cây cân bằng. Từ khi được giới thiệu, cây AVL đã nhanh chóng tìm thấy ứng dụng trong nhiều bài toán khác nhau. Vì vậy, nó mau chóng trở nên thịnh hành và thu hút nhiều nghiên cứu. Từ câyAVL, người ta đã phát triển thêm nhiều loại cấu trúc dữ liệu hữu dụng khác như cây đỏ - đen, B - Tree,... Định nghĩa: cây AVL là cây nhị phân tìm kiếm mà tại mỗi nút của nó độ cao của cây con trái và của cây con phải chênh lệch nhau không qúa một. Khoa CNTT- Trường ĐHSPKT Hưng Yên 10
Giáo trình - Cấu trúc dữ liệu và Giải thuật Dưới đây là ví dụ cây cân bằng 25 90 12 35 60 98 1 32 40 52 70 Hình 5.26. Cây AVL Dễ dàng thấy CCBHT là cây cân bằng. Điều này ngược lại không đúng. Tuy nhiên cây AVL là cấu trúc dữ liệu ổn định hơn hẳn CCBHT. Chiều cao của cây AVL Một vấn đề quan trọng, như đã đề cập đến ở phần trước, là ta phải khẳng định cây AVL n nút phải có chiều cao khoảng log2n. Để đánh giá chính xác về chiều cao của cây AVL, ta xét bài toán: cây AVL có chiều cao h sẽ có tối thiểu bao nhiêu nút ? Gọi N(h) số nút tối thiểu của cây AVL có chiều cao h. Ta có N(0) = 0, N(1) = 1và N(2) = 2. Cây AVL tối thiểu có chiều cao h sẽ có một cây con AVL tối thiểu chiều cao h - 1 và cây con AVL tối thiểu chiều cao h - 2. Như vậy: N(h) = 1 + N(h - 1) + N(h - 2) (1) Ta lại có: N(h - 1) > N(h - 2) Nên từ (1) suy ra N(h) > 2N(h - 2) N(h) > 22 N(h - 4) ... N(h) > 2i N(h - 2i) ⇒ N(h) > 2h/2-1 ⇒ h < 2log2(N(h)) + 2 Như vậy, cây AVL có chiều cao O(log2n). Ví dụ cây AVL tối thiểu có chiều cao h = 4 25 90 12 35 98 1 Cây AVL tối thiểu Khoa CNTT- Trường ĐHSPKT Hưng Yên 11
Giáo trình - Cấu trúc dữ liệu và Giải thuật Chỉ số cân bằng của một nút Định nghĩa: chỉ số cân bằng của một nút là hiệu của chiều cao cây con phải và cây con trái của nó. Đối với cây AVL chỉ số cân bằng của mỗi nút có thể nhận một trong ba giá trị sau đây: 0: độ cao cây con trái bằng độ cao cây con phải -1: cây con phải có độ cao lớn hơn độ cao cây con trái là 1 (lệch phải) 1: cây con trái có độ cao lớn hơn độ cao cây con phải là 1 (lệch trái) Khi bæ sung nót míi víi kho¸ x cho tr-íc ®-îc thùc hiÖn b»ng c¸ch sau: • ¸p dông thuËt to¸n bæ sung vµo c©y nhÞ ph©n t×m kiÕm • C©n b»ng l¹i c¸c ®Ønh mµ t¹i ®ã tÝnh c©n b»ngbÞ ph¸ vì (®é cao cña hai c©y con kh¸c nhau 2). XÐt c¸c tr-êng hîp sau TH1: C©y lÖch tr¸i (lÖch ph¶i ) sau khi bæ sung vµo c©y con ph¶i (tr¸i) c©y c©n b»ng TH2: Hai c©y con cã ®é cao b»ng nhau sau khi bæ sung th× c©y lÖch tr¸i hoÆc lÖch ph¶i TH3: C©y con tr¸i (ph¶i) cao h¬n c©y con ph¶i (tr¸i)1, sau khi bæ sung vµo c©y con tr¸i (ph¶i) th× hai c©y nµy cã ®é cao chªnh nhau lµ 2. Nh- vËy, tÝnh c©n b»ng bÞ ph¸ vì. §èi víi c¸c tr-êng hîp TH1 vµ TH2 khi bæ sung nót míi th× tÝnh c©n b»ng kh«ng bÞ ph¸ vì nªn ta chØ cÇn chØnh l¹i c¸c hÖ sè c©n b»ng ë nót ®ang xÐt vµ ë c¸c nót tiÒn bèi cña nã. §èi víi tr-êng hîp TH3 ta ph¶i söa l¹i c©y con mµ ta ®ang xÐt lµ nót gèc (ta sÏ gäi lµ nót bÊt th-êng). Qui -íc: chØ nót bÊt th-êng øng víi kho¸ b»ng 2 2 chØ nót míi bæ sung α(h) chØ c©y con α cã chiÒu cao h • TH3.1: Nót bæ sung lµm t¨ng chiÒu cao c©y con tr¸i cña nót con tr¸i nót nót bÊt th-êng 2 2 1 Khoa CNTT-1Trường ĐHSPKT Hưng Yên 12 γ γ (h) h + 2 (h) h + α β
Giáo trình - Cấu trúc dữ liệu và Giải thuật a) Tr-íc khi bæ H×nh 5.28 Sau khi bæ sung c©y mÊt b) © ®èi §èi víi tr-êng hîp nµy ®Ó t¸i c©n ®èi ta ph¶i thùc hiÖn phÐp quay tõ tr¸i sang ph¶i ®Ó ®-a nót (1) lªn vÞ trÝ gèc c©y con, nót (2) sÏ trë thµnh con ph¶i cña nã vµ β ®-îc g¾n vµo thµnh con tr¸i cña (2). Ng-êi ta gäi phÐp quay nµy lµ phÐp quay ®¬n (single rotation) hay ta cßn gäi lµ phÐp quay ph¶i. P P Q 1 1 Q γ 2 (h) h + 2 h + 2 α β (h) (h) α β γ (h+1) (h) (h) H×nh 5.29. Quay ph¶i c©y P VÝ dô: Cho CNPTK sau 25 25 12 90 25 90 12 35 10 35 90 12 35 10 a) C©y ban ®Çu b) Bæ sung thªm c) T¸i c©n ®èi ót (10) b»ng phÐp quay ®¬n H×nh 5.30 TH3.2: Nót míi bæ sung lµm t¨ng chiÒu cao c©y con ph¶i cña nót con tr¸i nót bÊt th-êng. 3 3 1 1 2 δ 2 h + 2 δ Khoa CNTT- Trường ĐHSPKT h + 1 Hưng Yên (h) 13 (h) α β γ α β γ (h) h h-1 (h) h-1 h-1
Giáo trình - Cấu trúc dữ liệu và Giải thuật H×nh 5.31 §çi víi tr-êng hîp nµy ®Ó t¸i c©n ®èi ta sö dông phÐp quay kÐp (double rotation), ®ãlµ viÖc phèi hîp hai phÐp quay ®¬n: quay tr¸i ®èi víi c©y con tr¸i ((1), (2)) vµ quay ph¶i ®èi víi c©y ((3), (2)) nh- h×nh 5.32 3 2 2 1 δ 1 3 γ (h-1) (h) γ α β α β (h-1) δ (h) (h) (h) (h) (h) a)Sau phÐp quay ®¬n b)Sau phÐp quay ®¬n thø nhÊt thø hai quay tr i quay ph¶i H×nh 5.32 VÝ dô: cho c©y nh- h×nh vÏ 35 90 25 90 25 25 45 12 35 12 12 30 90 30 30 a)Bæ sung thªm b)Sau phÐp ®¬n c)Sau phÐp quay ®¬n ót (30) th hÊt th h i H×nh 5.33 NhËn xÐt: Sau khi thùc hiÖn phÐp quay ®Ó t¸i c©n ®èi c©y con mµ nót gèc lµ nót bÊt th-êng kh«ng lµm ¶nh h-ëng ®Õn chiÒu cao cña c¸c c©y con ®ã vÉn gi÷ nguyªn nh- tr-íc lóc bæ sung, nghÜa lµ phÐp quay kh«ng lµm ¶nh h-ëng tíi chiÒu cao c¸c c©y cã liªn quan tíi c©y con nµy. Trong qu¸ tr×nh thùc hiÖn c¸c phÐp quay, tÝnh chÊt cña c©y nhÞ ph©n t×m kiÕm lu«n lu«n ®-îc ®¶m b¶o. Khoa CNTT- Trường ĐHSPKT Hưng Yên 14
Giáo trình - Cấu trúc dữ liệu và Giải thuật §èi víi c¸c tr-êng hîp khi bæ sung thªm nót míi lµm t¨ng chiÒu cao c©y con ph¶i cña nót con ph¶i vµ nót míi bæ sung lµm chiÒu cao c©y con tr¸i cña nót con ph¶i nót bÊt th-êng, th× ta lÇn l-ît thùc hiÖn theo thø tù ng-îc l¹i t-¬ng øng víi tr-êng hîp TH3.1 vµ TH3. 2. VÝ dô sau ®©y minh ho¹ cô thÓ vµ c¸c phÐp xö lý t-¬ng øng 5 5 5 2 7 4 25 2 7 7 90 1 3 12 2 1 4 10 1 a) C©y ban ®Çu b) Bæ sung thªm c) T¸i c©n ®èi nót (1): mÊt c©n b»ng phÐp ®èi tr-êng hîp quay ®¬n TH3.1 5 5 4 2 7 4 7 2 5 1 4 2 1 3 7 3 1 3 d) Bæ sung thªm e) T¸i c©n ®èi f) Sau phÐp quay nót (3): mÊt c©n b»ng phÐp quay ®¬n thø hai ®èi tr-êng hîp kÐp TH3.1 Sau phÐp ®¬n thø 4 4 4 2 5 2 5 2 6 1 3 7 1 3 1 3 5 6 6 7 g) Bæ sung thªm h) Sau phÐp quay i) Sau phÐp quay nót (6): mÊt c©n ®¬n thø nhÊt ®¬n thø hai (quay ®èi tr-êng hîp (quay ph¶i) tr¸i) TH3.2 H×nh 5.34 Huû mét nót trªn c©y AVL Khoa CNTT- Trường ĐHSPKT Hưng Yên 15
Giáo trình - Cấu trúc dữ liệu và Giải thuật Còng gièng nh- thao t¸c thªm mét nót, viÖc huû nót x ra khái c©y AVL thùc hiÖn gièng nh- trªn CNPTK. ChØ sau khi huû, nÕu tÝnh c©n b»ng bÞ ph¸ vì th× ta sÏ thùc hiÖn viÖc c©n b»ng l¹i. Tuy nhiªn viÖc c©n b»ng l¹i trong thao t¸c huû sÏ phøc t¹p h¬n nhiÒu so víi viÖc c©n b»ng khi thªm mét nót do cã thÓ x¶y ra ph¶n øng d©y chuyÒn. NhËn xÐt • Thao t¸c thªm mét nót cã ®é phøc t¹p O(1) • Thao t¸c huû mét nót cã ®é phøc t¹p O(h) • Víi c©y c©n b»ng trung b×nh hai lÇn thªm vµo c©y th× cÇn mét lÇn c©n b»ng l¹i; 5 lÇn huû th× cÇn mét lÇn c©n b»ng l¹i • ViÖc huû mét nót cã thÓ ph¶i c©n b»ng d©y chuyÒn c¸c nót tõ gèc cho ®Õn phÇn tö bÞ huû trong khi thªm vµo chØ cÇn mét lÇn c©n b»ng côc bé • §é dµi ®-êng t×m kiÕm trung b×nh trong c©y c©n b»ng gÇn b»ng c©y c©n b»ng hoµn toµn, nh-ng viÖc c©n b»ng l¹i ®¬n gi¶n h¬n nhiÒu • Mét c©y c©n b»ngkh«ng bao giê cao h¬n 45% c©y c©n b»ng hoµn toµn t-¬ng øng dï sè nót trªn c©y lµ bao nhiªu. 23.1.4 Cây đỏ đen Cây đỏ đen (tiếng Anh: red-black tree) là một dạng cây tìm kiếm nhị phân tự cân bằng, một cấu trúc dữ liệu được sử dụng trong khoa học máy tính. Cấu trúc ban đầu của nó được đưa ra vào năm 1972 bởi Rudolf Bayer. Ông gọi chúng là các "B-cây cân bằng" còn tên hiện nay được đưa ra từ 1978 bởi Leo J. Guibas và Robert Sedgewick. Nó là cấu trúc phức tạp nhưng cho kết quả tốt vế thời gian trong trường hợp xấu nhất. Các phép toán trên chúng như tìm kiếm (search), chèn (insert), và xóa (delete) trong thời gian O (log n), trong đó n là số các phần tử của cây. Định nghĩa Một cây đỏ-đen là một cây nhị phân, là một cấu trúc dữ liệu trong khoa học máy tính để tổ chức các thành phần dữ liệu có thể so sánh, chẳng hạn các số. Trong cây nhị phân các thành phần dữ liệu được đưa vào các nút (node). Trong các nút có một nút nằm ở vị trí khởi đầu không là con của nút nào được gọi là gốc. Các nút khác đều là con của một nút nào đó và có không quá hai con. Từ nút gốc có một đường đi duy nhất đến mỗi nút khác trên cây. Các nút không có con được gọi là lá (leaf node). Trong cây đỏ đen, các lá được gán giả là null; nghĩa là chúng không chưa bất kỳ dữ liệu nào Khoa CNTT- Trường ĐHSPKT Hưng Yên 16
Giáo t trình - Cấu tr dữ liệu và Giải thuật rúc v Ví dụ một cây đ ụ đỏ-đen Các tí chất ính Mỗi n của cây đỏ-đen có thuộc tinh "màu" nhận một trong hai giá trị "đỏ" hoặc "đen". nút n g ị c Ngoài ra: i 1. Một nút hoặc là đỏ ho đen. oặc 2. Gốc là đenn. 3. Tất cả các lá là đen. c 4. Cả hai con của mọi n đỏ là đen (và suy ra mọi nút đ có nút ch là đen.) n nút n. đỏ ha 5. Tất cả các đường đi t một nút đ cho tới c lá chứa m số như nhau các n đen. c từ đã các một ư nút Tính chất 5 còn đ c được gọi là tính chất "c bằng đe Số các nút đen trê một đườn đi từ cân en". ên ng gôc tớ mỗi lá đư gọi là độ dài đen củ đường đi đó. Trong bài này ch xét các đư ới ược ủa đ g hỉ ường đi từ gốc tới các lá n ta sẽ gọ tắt các đư c nên ọi ường đi như vậy là đườ đi. Sức mạnh của cây đỏ ư ờng c a đen nằ trong cá tính chấ trên. Từ c tính chấ này suy r trong cá đường đi từ gốc ằm ác ất các ất ra ác i tới các lá đường đ dài nhất không vượ quá hai lầ đường đi ngắn nhất. Do đó cây đỏ đen c đi ợt ần là gần cân bằng. Vì các thu toán chè xóa, tìm kiếm trong trường hợ xấu nhất đều tỷ n uật èn, m g ợp t lệ với chiều cao của cây nên cây đỏ đen rất hiệu quả trong cá trường hợ xấu nhất c n n q ác ợp t,không giống như cây tìm kiếm nhị phân thông thường. m g Để thấ rõ sức m ấy mạnh này, ta chú ý rằng không có đường đi n từ gôc tới một lá ch hai a g nào t hứa nút đỏ liền nhau (theo tính chất 4). Do đó trên mỗi đường số nút đỏ kh ỏ o m hông nhiều hơn số nút đe Đường đi ngắn nh là đườn đi chỉ có nút đen, đường đi d nhất có thể là en. hất ng ó dài ó đường đi xen kẽ giữa các nú đỏ và đe Theo tín chất 5, số các nút đ trên hai đường g út en. nh đen i đi đó b bằng nhau, và do đó đưường đi dài nhất không vượt quá hai lần đườ đi ngắn nhất. i g ờng n Trong nhiều biểu diễn của d liệu cây có thể có các nút ch có một co và có cá lá có g u dữ y, hỉ on ác chứa d liệu. Tu nhiên có thể biểu d dữ uy ó diễn cây đỏ đen ta có một chút th đổi mà không hay à làm th đổi tính chất cơ bản của cây và độ phứ tạp của c thuật to hay h b y ức các oán. Với mụ đích ục này, ta đưa thêm các lá nul vào làm con phải hoặc con trá hoặc cả h của nhữ nút m ll h ái hai ững không có chúng, các lá này không chứ dữ liệu mà chỉ làm nhiệm vụ t g y ứa m thông báo r rằng tại đây câ đã kết th ây húc, như hình vẽ ở tr rên. Việc th hêm các nú này làm c tất cả c nút út cho các trong của cây đề chứa dữ lieụu và có hai con, h khác đi cây đỏ đe cùng với các lá ều ó hay i en i null là cây nhị ph đầy dủ. Khi đó số các "lá null nhiều hơ số các nú chứa dữ l của à hân l" ơn út liệu cây m lá. một Kh CNTT T ờ ĐHSP PKT H Y Yê 17
Giáo trình - Cấu trúc dữ liệu và Giải thuật Một số người định nghĩa cây đỏ đen bằng cách gán màu đỏ đen cho các cạnh chứ không phải các nút. Tuy nhiên điều đó không tạo nên sự khác biệt. Khi ấy màu của mỗi nút tương ứng với màu của cạnh nối nó với nút cha. ể thấy rõ sức mạnh này, ta chú ý rằng không có đường đi nào từ gôc tới một lá chứa hai nút đỏ liền nhau (theo tính chất 4). Do đó trên mỗi đường số nút đỏ không nhiều hơn số nút đen. Đường đi ngắn nhất là đường đi chỉ có nút đen, đường đi dài nhất có thể là đường đi xen kẽ giữa các nút đỏ và đen. Theo tính chất 5, số các nút đen trên hai đường đi đó bằng nhau, và do đó đường đi dài nhất không vượt quá hai lần đường đi ngắn nhất. Trong nhiều biểu diễn của dữ liệu cây, có thể có các nút chỉ có một con và có các lá có chứa dữ liệu. Tuy nhiên có thể biểu diễn cây đỏ đen ta có một chút thay đổi mà không làm thay đổi tính chất cơ bản của cây và độ phức tạp của các thuật toán. Với mục đích này, ta đưa thêm các lá null vào làm con phải hoặc con trái hoặc cả hai của những nút không có chúng, các lá này không chứa dữ liệu mà chỉ làm nhiệm vụ thông báo rằng tại đây cây đã kết thúc, như hình vẽ ở trên. Việc thêm các nút này làm cho tất cả các nút trong của cây đều chứa dữ lieụu và có hai con, hay khác đi cây đỏ đen cùng với các lá null là cây nhị phân đầy dủ. Khi đó số các "lá null" nhiều hơn số các nút chứa dữ liệu của cây một lá. Một số người định nghĩa cây đỏ đen bằng cách gán màu đỏ đen cho các cạnh chứ không phải các nút. Tuy nhiên điều đó không tạo nên sự khác biệt. Khi ấy màu của mỗi nút tương ứng với màu của cạnh nối nó với nút cha. Các phép toán trên cây đỏ đen Có thể áp dụng ngay các phép chèn, xóa trong cây tìm kiếm nhị phân vào cây đỏ đen mà không cần sửa chữa gì vì cây đỏ đen là trường hợp riêng của cây tìm kiếm nhị phân. Tuy nhiên, khi đó có thể có một số tính chất trong định nghĩa của cây đỏ đen sẽ bị vi phạm. Việc khôi phục các tính chất đỏ đen sẽ cần một số nhỏ cỡ O(log n) hoặc trung bình chỉ O(1) các phép đổi màu (tốn rất ít thời gian) và không quá ba phép quay cho phép xóa, hai cho phép chèn. Toàn bộ các giải thuật chèn và xóa có độ phức tạp thời gian cỡ O(log n). Phép chèn Phép chèn bắt đầu bằng việc bổ sung một nút như trong cây tìm kiếm nhị phân bình thường và gán cho nó màu đỏ. Ta xem xét để bảo toàn tính chất đỏ đen từ các nút lân cận với nút mới bổ sung. Thuật ngữ nút chú bác sẽ dùng để chỉ nút anh (hoặc em) với nút cha của nút đó như trong cây phả hệ. Chú ý rằng: • Tính chất 3 (Tất cả các lá -là các nút null là đen) giữ nguyên. • Tính chất 4 (Cả hai con của nút đỏ là đen) nếu bị thay đổi chỉ bởi việc thêm một nút đỏ có thể sửa bằng cách gán màu đen cho một nút đỏ hoặc một phép quay. • Tính chất 5 (Tất các các đường đi từ gôc tới các lá có cùng một số nút đen) nếu bị thay đổi chỉ bởi việc thêm một nút đỏ có thể sửa bằng cách gán màu đen cho một nút đỏ hoặc một phép quay. Khoa CNTT- Trường ĐHSPKT Hưng Yên 18
Giáo trình - Cấu trúc dữ liệu và Giải thuật Chú ý: Nhãn N sẽ dùng để chỉ nút đang chèn vào, P chỉ nút cha của N', G chỉ ông của N', và U chỉ chú bác của N'. Nhớ rằng,giữa các trường hợp, vai trò và nhãn của các nút có thể thay đổi còn trong cùng một trường hợp thì không. Mỗi trường hợp được giới thiệu bằng một đoạn mã C. Nút chú bác và nút ông dế dàng xác định nhờ các hàm sau: struct node *grandparent(struct node *n) { return n->parent->parent; } struct node *uncle(struct node *n) { if (n->parent == grandparent(n)->left) return grandparent(n)->right; else return grandparent(n)->left; } Trường hợp 1: Nút mới thêm N ở tại gốc. Trong trường hợp này, gán lại màu đen cho N, để bảo toàn tính chất 2 (Gốc là đen). Vid mới chỉ bổ sung một nút, Tính chất 5 được bảo đảm vì mọi đường đi chỉ có một nút. void insert_case1(struct node *n) { if (n->parent == NULL) n->color = BLACK; else insert_case2(n); } Trường hợp 2: Nút cha P của nút mới thêm là đen, khi đó Tính chất 4 (Cả hai nút con của nút đỏ là đen) không bị vi phạm vì nút mới thêm có hai con là "null' là đen. Tính chất 5 cũng không vi phạm vì nút mới thêm là đỏ không ẩnh hưởng tới số nút đen trên tất cả đường đi. void insert_case2(struct node *n) { if (n->parent->color == BLACK) return; /* Tree is still valid */ else insert_case3(n); } Chú ý: Trong trường hợp tiếp theo nếu N có ông là nút G, vì nếu cha P là đỏ và P không ở gốc thì G là đen. Như vậy, N cũng có chú bác là U, although it may be a leaf in cases 4 and 5. Khoa CNTT- Trường ĐHSPKT Hưng Yên 19
Giáo trình - Cấu trúc dữ liệu và Giải thuật Trường hợp 3: Cả cha P và bác U là đỏ, thì thể đổi cả hai thành đen còn G thành đỏ (để bảo toàn tính chất 5 .Khi đó nút mới N có cha đen. Vì đường đi bất kỳ đi qua cha và bác của "N" phải đi qua ông của N nên số các nút đen trên đường đi này không thay đổi. Tuy thế nút ông G có thể vi phạm tính chất 2 (Gốc là đen) hoặc 4 (Cả hai con của nút đỏ là nút đen) (tính chất 4 bị vi phạm khi cha của G là đỏ). Để sửa chữa trường hợp này gọi một thủ tục đệ quy trên G từ trường hợp 1. Note that this is the only recursive call, and it occurs prior to any rotations, which proves that a constant number of rotations occur. void insert_case3(struct node *n) { if (uncle(n) != NULL && uncle(n)->color == RED) { n->parent->color = BLACK; uncle(n)->color = BLACK; grandparent(n)->color = RED; insert_case1(grandparent(n)); } else insert_case4(n); } Chú ý: Trong các trường hợp tiếp theo, giả sử rằng nút cha P là con trái của cha của nó. Nếu nó là con phải, left và right đổi chỗ cho nhau trong cases 4 and 5. Trường hợp 4: Nút cha P là đỏ nhưng nút chú bác U là đen, nút mới N là con phải của nút P, và P là con trái của nút G. Trong trường hợp này, thực hiện quay trái chuyển đổi vai trò của nút mới N và nút cha P do đó định dạng lại nút P bằng Trường hợp 5 (đổi vai trò N và P) vì tính chất 4 bị vi phạm (Cả hai con của nút đỏ là đen) . Phép quay cũng làm thay đổi một vài đường đi (các đường đi qua cây con nhãn "1") phải đi qua thêm nút mới N, nhưng vì N là đỏ nên không làm chúng vi pham tính chất 5 void insert_case4(struct node *n) { if (n = = n->parent->right && n->parent = = grandparent(n)->left) { rotate_left(n->parent); n = n->left; } else if (n = = n->parent->left && n->parent = = grandparent(n)->right) { rotate_right(n->parent); n = n->right; } insert_case5(n); } Khoa CNTT- Trường ĐHSPKT Hưng Yên 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.