Red Black Tree - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.doc) (18 trang)

Trang chủ

Công Nghệ Thông Tin

Kỹ thuật lập trình

red black tree

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (353.26 KB, 18 trang )

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘIViện Công nghệ Thông tin và Truyền thôngBÀI TẬP LỚN MÔN HỌC CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Đề tài: "Red-Black Tree" Sinh viên thực hiện: Phùng Văn Chiến. SHSV:20111253 Mã lớp: Giáo viên hướng dẫn: PGS Nguyễn Đức Nghĩa HÀ NỘI – 2013 Mục lụcI.Định nghĩa 3 A.Giới Thiệu: 3 B.Cây đỏ đen 3 1.Đinh nghĩa: 3 2.Các tính chất của cây đỏ đen: 3 3.Chiều cao đen 4 4.Các định lí: 4 5.Khai báo cấu trúc 5 6.Các phép toán trên cây đỏ-đen 5II.Cài đặt 5 1.Khởi tạo 5 2.Tạo một nút mới 6 3.Các phép quay 6 4.Phép chèn(insertation) 7 5.Phép xóa(Deletation) 11 6.Tìm Kiếm(Search): 15III.Ứng Dụng 16I.Định nghĩa A.Giới Thiệu: Cây tìm kiếm nhị phân là một cấu trúc lưu trữ dữ liệu tốt với tốc độ tìm kiếm nhanh. Tuy nhiên trong một số trường hợp cây tìm kiếm nhị phân có một số hạn chế. Nó hoạt động tốt nếu dữ liệu được chèn vào cây theo thứ tự ngẫu nhiên. Tuy nhiên, nếu dữ liệu được chèn vào theo thứ tự đã đuợc sắp xếp sẽ không hiệu quả. Khi các trị số cần chèn đã đuợc sắp xếp thì cây nhị phân trở nên không cân bằng. Khi cây không cân bằng, nó mất đi khả năng tìm kiếm nhanh (hoặc chèn hoặc xóa) một phần tử đã cho. Chúng ta khảo sát một cách giải quyết vấn đề của cây không cân bằng: đó là cây đỏ đen, là cây tìm kiếm nhị phân có thêm một vài đặc điểm. B.Cây đỏ đen 1.Đinh nghĩa: Cây đỏ-đen 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à “B-cây cân bằng”, còn tên hiện nay được đưa ra năm 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(logn), trong đó n là số các phần tử của cây . 2.Các tính chất của cây đỏ đen: Tc1:Một nút hoặc là đỏ hoặc là đen. Tc2:Gốc là đen. Tc3:Tất cả các lá là đen. Tc4:Cả hai con của mọi nút đỏ là đen. (và suy ra mọi nút đỏ có nút cha là đen.) Tc5:Tất cả các đường đi từ một nút đã cho tới các lá chứa một số như nhau các nút đen. Tính chất 5 còn được gọi là tính chất "cân bằng đen". Số các nút đen trên một đường đi từ gôc tới mỗi lá được gọi là độ dài đen của đường đi đó. Sức mạnh của cây đỏ đen nằm trong các tính chất trên. Từ các tính chất này suy ra trong các đường đi từ gốc tới các lá đường đi dài nhất không vượt quá hai lần đường đi ngắn nhất. Do đó cây đỏ đen là gần cân bằng. Vì các thuật toán chèn, xóa, tìm kiếm trong trường hợp xấu nhất đều tỷ lệ với chiều cao của cây nên cây đỏ đen rất hiệu quả trong các trường hợp xấu nhất,không giống như cây tìm kiếm nhị phân thông thường . 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à Thời Gian Tính 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ẽ ở dưới. 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ữ liệ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á. Hình 1: Ví dụ về cây đỏ-đen 3.Chiều cao đen Chiều cao đen (Black -Height) của một nút P bằng số nút đen trên đường dẫn từ nút đó đến nút lá bất kì (không tính các nút von trỏ Null).Kí hiệu là bh(P).Ví dụ như hình vẽ trên có bh(root)=2. 4.Các định lí: Định lí 1:Một cây đỏ-đen bất kì có nút gốc là x có ít nhất n=2bh(x)- 1 nút trong,bh(x) là chiều cao đen của gốc x. Chứng minh:Ta chứng minh bằng quy nạp với 1 nút x bất kì(x không nhất thiết là nút gốc màu đen,ở đây ta tổng quát cho cả trường hợp x là nút đỏ hay x là con của 1 nút gốc khác) +) Nếu bh=0 thì x=NULL,do đó số nút trong =0=2bh(x)- 1. +) Nếu bh=1 thì x<> NULL,số nút trong ít nhất là 1=2bh(x)- 1. +)Giả sử các cây có chiều cao đen =bh(x)-1 đều thỏa mãn định lí.Xét cây gốc x có chiều cao đen bh(x),khi đó 2 con của nó có chiều cao đen hoặc =bh(x)-1(nếu x đen) hoặc =bh(x) (nếu x đỏ).Do đó số nút tối thiểu của cây gốc x bằng số nút trên 2 cây con cộng 1. (2bh(x)-1 - 1)+(2bh(x)-1 - 1)=2bh(x)- 1. ==> ĐPCM. Định lí 2:Trong một cây đỏ đen,ít nhất một nửa số nút trên đường dẫn từ gốc đến lá là nút đen. => Chứng minh dựa vào tính chất 4(mọi nút đỏ đều có 2 con là nút đen do đó không có 2 nút đỏ kề nhau trên đường đi từ gốc đến là). Định lí 3:Một cây đỏ-đen có n nút trong có chiều cao h<=2log(n+1). Chứng minh : Gọi h là chiều cao cây đỏ-đen gốc x. Theo định lí 2 ta có bh(x)>=h/2. Mặt khác từ định lí 1 ta có n>=2bh(x)- 1>=2h/2-1. Do đó h<=2log(n+1). ==> ĐPCM. 5.Khai báo cấu trúc typedef int Data; /* Kiểu dữ liệu khoá */ typedef enum { BLACK, RED } nodeColor; typedef struct Node { nodeColor color; /* Màu node (BLACK, RED) */ Data info; /* Khoá sử dụng tìm kiếm */ struct Node *left; /* Con trái */ struct Node *right; /* Con phải */ struct Node *parent; /* Cha */ }; typedef struct Node pNode typedef struct RedBlackTree{pNode **root}; struct RedBlackTree Tree; 6.Các phép toán trên cây đỏ-đen -init(item):Khởi tạo cây có gốc có khóa là item. - makeRedBlack(value,node):tạo 1 nút với khóa cho bởi value,và có nút cha là nút node. - rotate_left(RedBlack),rotate_right(RedBlack): quay trái quay phải nút RedBlack. - insert(item):chèn nút với khóa cho bởi item vào cây đỏ-đen ; - delete(item):xóa nút cho bởi khóa item trong cây đỏ-đen; - search(item):tìm nút với khóa item trong cây đỏ-đen; II.Cài đặt 1.Khởi tạo. pNode * init(Data item) { Tree.root=(pNode *)malloc(sizeof(pNode *)); Tree.root->info=item; Tree.root->color=BLACK; Tree.root->left=NULL; Tree->right=NULL; Tree->parent=NULL; return Tree.root; } 2.Tạo một nút mới. Input:phần tử cần tạo; Các bước: +) Cấp phát bộ nhớ cho nút mới. +)Kiểm tra lỗi cấp phát; +) Nếu cấp phát được thì đưa phần tử vào nút mới và gán nó màu đỏ (mặc định); +)Con trái con phải gán bằng NULL. OutPut:Con trỏ tới địa chỉ nút mới. pNode *makeRedBlack(Data x,pNode *node) { pNode * newRedBlack=NULL; newRedBlack=(pNode *)malloc( sizeof( pNode *)); //khởi tạo if(newRedBlack==NULL) { printf(”Out of memmory”) exit(1); } else { newRedBlack->info=x; newRedBlack->color=RED; newRedBlack->left=NULL; newRedBlack->right=NULL; newRedBlack->parent=node; } return newRedBlack; } .Thời Gian Tính: Dễ thấy Thời Gian Tính của thao tác là O(1). 3.Các phép quay Thực ra quay không có nghĩa là các node bị quay mà để chỉ sự thay đổi quan hệ giữa chúng. Một node được chọn làm "đỉnh" của phép quay. Nếu chúng ta đang thực hiện một phép quay qua phải, node "đỉnh" này sẽ di chuyển xuống dưới và về bên phải, vào vị trí của node con bên phải của nó. Node con bên trái sẽ đi lên để chiếm lấy vị trí của nó. hình 2:quay trái,quay phải Phải đảm bảo trong phép quay phải, node ở đỉnh phải có node con trái. Nếu không chẳng có gì để quay vào điểm đỉnh. Tương tự, nếu làm phép quay trái, node ở đỉnh phải có node con phải. a.Quay trái void rotate_left(pNode * x) { pNode * y=x->right;// set node x->right=y->left;//con phải của x được gán bằng con trái của y if(y->left!=NULL) y->left->parent=x;//cha của nút con trái của y giờ là x y->parent=x->parent;//gán cha cho y là cha của x if(x->parent==NULL) //x là nút gốc { T.root =y; //thì y giờ thành nút gốc. } else if(x==x->parent->left) //Trái lại thì gán cha của x cho cha y. { x->parent->left=y; } else x->parent->right=y; y->left=x; //đặt lại con trái cho node và cha của RedBlack; x->parent=y; } b.Quay phải void rotate_right(pNode * x) { pNode * y=x->left;// set y x->left=y->right;//con trái của x được gán bằng con phải của y if(y->right!=NULL) y->right->parent=x;//cha của nút con phải của y giờ là x y->parent=x->parent;//gán cha cho y là cha của x if(x->parent==NULL) { T.root=y;//x là nút gốc thì y giờ thành nút gốc. } else if(x==x->parent->left) //Trái lại thì gán cha của x cho cha y. { x->parent->left=y; } else x->parent->right=y; y->right=x; //đặt lại con phải cho y và cha của x; x->parent=y; }.Thời Gian Tính:Các thao tác quay đều có Thời Gian Tính là hằng số :O(1). 4.Phép chèn(insertation) -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ổ xung.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ú ý: .Tính chất 3(Tất cả các lá đều đen-là các nút NULL) giữ nguyên. .Tính chất 4(Cả 2 con của nút đỏ là đen) nếu bị thay vì thêm một nút đỏ có thể gán màu đen cho 1 nút đỏ hoặc thực hiện phép quay. .Tính chất 5(Tất 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 vì việc thêm 1 nút đỏ có thể gán 1 nút đỏ thành đen hoặc thực hiện phép quay. -Khi chèn cần chú ý các trường hợp sau(giả sử X trỏ đến nút vừa thêm): CASE 1:X là nút gốc,đổi màu X thành đen;(được thực hiện trong hàm makeRedBlack() ) CASE 2: Cả 2 nút: cha và chú đều đỏ thì thực hiện đổi mầu nút cha, chú thành đen, màu nút ông thành đỏ, X trỏ đến nút ông, tiếp tục kiểm tra X tại vị trí mới. hình 3:minh họa thao tác CASE 3 :Nút cha đỏ, chú đen. Nút cha và nút X không cùng là con trái hoặc phải. Thực hiện đổi mầu nút ông thành đỏ, X –đen, quay trái(phải) nút cha, quay phải(trái) nút ông. Hình 4:minh họa thao tác trên (nút cha quay trái,nút ông quay phải) CASE 4: Nút cha đỏ, chú đen. X và nút cha hoặc cùng là con trái hoặc cùng là con phải. Thực hiện đổi màu nút cha thành đen, ông thành đỏ, quay phải nút ông. hình 5:minh họa thao tác trên. a.Hàm sau minh họa thao tác chèn khóa có giá trị item vào cây đỏ-đen được trỏ bởi con trỏ RedBlack; void insert(Data item) { pNode * x=Tree.root; pNode * y=x->parent; while(x!=NULL) { if(item<x->info) { y=x; x=x->left; } else if(item>x->info) { y=x; x=x->right; } x=makeRedBlack(item,y); changecolor(x);//thao tác đổi màu theo nguyên tắc trên } Trong chương trình chính để chèn khóa key ta gọi insert(T.root,key). b.Hàm xác định nút chú bác và nút ông: pNode * grandparent(pNode * RedBlack) { return RedBlack->parent->parent; } pNode * uncle(pNode * RedBlack) { pNode * tmp; tmp=grandparent(RedBlack); if(RedBlack->parent==tmp->left) return tmp->right; else return tmp->left; } c. Hàm đổi màu:changecolor(RedBlack) {đổi màu theo các nguyên tắc đã nêu ở trên} void changecolor(pNode * RedBlack) { pNode * grandpt; pNode * ule; grandpt=grandparent(RedBlack); ule=uncle(RedBlack); if(RedBlack->parent==NULL) //case 1 { RedBlack->color=BLACK; } else if(RedBlack->parent->color==RED&&ule->color==RED) //case 2 { RedBlack->parent->color=BLACK; ule->color=BLACK; grandpt->color=RED; changecolor(T,grandpt); } else if(RedBlack->parent->color==RED&&(ule->color==BLACK|| ule==NULL)) { if(RedBlack->parent==grandpt->left&&RedBlack==RedBlack->parent->right) //case 3 { grandpt->color=RED; RedBlack->color=BLACK; rotate_left(T,RedBlack->parent);//quay trái; rotate_right(T,grandpt);//quay phải; } else if(RedBlack->parent==grandpt->right&&RedBlack==RedBlack->parent->left) //case 3 { grandpt->color=RED; RedBlack->color=BLACK; rotate_right(T,RedBlack->parent);//quay trái; rotate_left(T,grandpt);//quay phải; } else if(RedBlack->parent==grandpt->left&&RedBlack==RedBlack->parent->left) //case 4 { RedBlack->parent->color=BLACK; grandpt->color=RED; rotate_right(T,grandpt); } else if(RedBlack->parent==grandpt->right&&RedBlack==RedBlack->parent->right) //case 4 { RedBlack->parent->color=BLACK; grandpt->color=RED; rotate_left(T,grandpt); } } } .Thời Gian Tính: - Do cây đỏ đen là cây cân bằng nên nếu duyệt theo chiều cao của cây thì luôn có thời gian là O(logn) - Hàm changecolor(RedBlack) có thời gian là O(logn) trong trường hợp 1(đi từ dưới lên trên gốc) và O(1) trong các trường hợp còn lại. - Hàm insert(): .Việc duyệt nút từ gốc xuống tìm vị trí chèn có thời gian là O(logn) .Hàm đổi màu tối đa là O(logn)(case 1). .Hàm tạo nút là O(1) => Tổng là O(logn). 5.Phép xóa(Deletation) Trong cây tìm kiếm nhị phân bình thường khi xóa một nút có cả hai con (không là lá null), ta tìm phần tử lớn nhất trong cây con trái hoặc phần tử nhỏ nhất trong cây con phải, chuyển giá trị của nó vào nút đang muốn xóa (xem Cây tìm kiếm nhị phân). Khi đó chúng ta xóa đi nút đã được copy giá trị, nút này có ít hơn hai con (không là lá null) . Vì việc copy giá trị không làm mất tính chất đỏ đen nên không cần phải sửa chữa gì cho thao tác này. Việc này chỉ đặt ra khi xóa các nút có nhiều nhất một con (không là lá null). Chúng ta sẽ thảo luận về việc xóa một nút có nhiều nhất một con (không là lá null) . Nếu ta xóa một nút đỏ, ta có thể chắc chắn rằng con của nó là nút đen. Tất cả các đường đi đi qua nút bị xóa chỉ đơn giản bớt đi một nút đỏ do đó tính chất 5 không thay đổi. Ngoài ra, cả nút cha và nút con của nút bị xóa đều là nút đen, do đó tính chất 3 và 4 vẫn giữa nguyên Một trường hợp đơn giản khác là khi xóa một nút đen chỉ có có một con là nút đỏ. Khi xóa nút đó các tính chất 4 và 5 bị phá vỡ, nhưng nếu gán lại màu cho nút con là đen thì chúng lại được khôi phục. Trường hợp phức tạp xảy ra khi cả nút bị xóa và nút con của nó đều là đen. Chúng ta sẽ bắt đầu bằng việc thay nút bị xóa bằng nút con của nó. Chúng ta sẽ gọi nút con này (trong vị trí mới của nó là N, và anh em với nó (con khác của nút cha mới) là S. Tiếp theo ta vẫn dùng P chỉ cha mới của N, SL chỉ con trái của S, và SR chỉ con phải của S (chúng tồn tại vì S không thể là lá). Hàm xóa nút có khóa là k: void deleteRedBlack(Data k) { pNode *x,*y,*z; pNode *Null=null(); if(Tree.root==NULL) { printf("\ncay rong khong the xoa"); return; } z=Tree.root; while(z!=NULL&&z->info!=k) { if(z->info>k)z=z->left; else z=z->right; } if(z==NULL) { printf("khong tim thay nut nao co khoa = %d \n",k); return; } if(z->left==NULL||z->right==NULL) y=z; else y=find_min(z->right); if(y->left!=NULL) x=y->left; else x=y->right; if(x==NULL) x=Null; x->parent=y->parent; if(y->parent==NULL) Tree.root=x; else if(y==y->parent->left) y->parent->left=x; else y->parent->right=x; if(y!=z) z->info=y->info; if(y->color==BLACK) deletefix(x); y->left=y->right=Null; free(y); printf("\n xoa thanh cong"); } Nếu cả N và gốc ban đầu của nó là đen thì sau khi xóa các đường qua "N" giảm bớt một nút đen. Do đó vi phạm Tính chất 5, cây cần phải cân bằng lại. Có các trường hợp sau: Trường hợp 1: S là đỏ. Trong trường hợp này tráo đổi màu của P và S, và sau đó quay trái tai P, nó sẽ làm cho S trở thành nút ông của N. Chú ý rằng P có màu đen và có một con màu đỏ. Tất cả các đường đi có số các nút đen giống nhau, bây giờ N có một anh em màu đen và cha màu đỏ, chúng ta có thể tiếp tục với các trường hợp 4, 5, hoặc 6. (anh em mới của nó là đen ví chỉ có một con của nút đỏ S.) Trong các trường hợp sau la sẽ gọi anh em mới của N' là S. Trường hợp 2.1: P,S, và các con của S là đen. Trong trường hợp này, chúng ta gán lại cho S màu đỏ. Kết quả là mọi đường đi qua S, (tất nhiên chúng không qua N,có ít hơn một nút đen. Vì việc xóa đi cha trước đây của N' làm tất cả các đương đi qua N bớt đi một nút đen, nên chúng bằng nhau. Tuy nhiên tất cả các đường đi qua P bây giờ có ít hơn một nút đen so với các đường không qua P, do đó Tính chất 5 (Tất cả các đường đi từ gốc tới các nút lá có cùng số nút đen) sẽ bị vi phạm. Để sửa chữa nó chúng ta lại tái cân bằng tại P, bắt đầu từ trường hợp 1 . Trường hợp 2.2: S và các con của S là đen nhưng P là đỏ. Trong trường hợp này, chúng ta đổi ngược màu của S và P. Điều này không ảnh hưởng tới số nút đen trên các đường đi không qua N, nhưng thêm một nút đen trên các đường đi qua N, thay cho nút đen đã bị xóa trên các đường này: Trường hợp 3: S là đen, con trái của S là đỏ, con phải của S là đen, còn N là con trái của cha nó. Trong trường hợp này chúng ta quay phải tại S, khi đó con trái của S trở thành cha của S và N là anh em mới của nó. Sau đó ta tráo đổi màu của S và cha mới của nó. Tất cả các đường đi sẽ có số nút đen như nhau, nhưng bây giờ N có một người anh em đen mà con phải của nó lại là đỏ, chúng ta chuyển sang Trường hợp 6. Hoặc N hoặc cha của nó bị tác động bởi việc dịch chuyên này.(Lưu ý trong trường hợp 6, ta đặt lại nút anh em mới của N là S.) Trường hợp 4: S là đen, con phải của S là đỏ và N là con trái của nút cha P. Trong trường hợp này chúng ta quay trái tại P, khi đó S trở thành cha của P và con phải của S. Chúng ta hoán đổi màu của P và S, và gán cho con phải của S màu đen. Cây con giữ nguyên màu của gốc do đó Tính chất 4 (Cả hai con của nút đỏ là đen) và Tính chất 5 không bị vi phạm trong cây con này. Tuy nhiên, N bây giờ có thêm một nút đen tiền nhiệm: hoặc P mới bị tô đen, nó đã là đen và S là nút ông của nó trở thành đen. Như cậy các đương đi qua N có thêm một nút đen.Trong lúc đó, với một đường đi không đi qua N, có hai khả năng:đi qua nút anh em của N. Khi đó cả trước và sau khi quay nó phải đi qua S và P, khi thay đổi màu sắc hai nút này đã tráo đổi màu cho nhau. Như vây đường đi này không bị thay đổi số nút đen.đi qua nút bác của N', là con phải của S. Khi đó trước khi quay nó đi qua S, cha của S, và con phải của S, nhưng sau khi quay nó chỉ đi qua nút S và con phải của S, khi này S đã nhận màu cũ của cha P còn con phải của S's đã đổi màu từ đỏ thành đen. Kết quả là số các nút đen trên đường đi này không thay đổi.Như vậy, số các nút đen trên các đường đi là không thay đổi. Do đó các tính chất 4 và 5 đã được khôi phục. Nút trắng trong hình vẽ có thể là đỏ hoặc đen, nhưng phải ghi lại trước và sau khi thay đổi. -Thủ tục deletefix() được mô tả như sau:void deletefix(pNode * *x) { pNode *w; pNode *Null=null(); while(x!=Tree.root&&x->color==BLACK) { if(x==x->parent->left) { w=x->parent->right; if(w!=NULL) { if(w->color==RED) { w->color=BLACK; //case 1 x->parent->color=RED; //case 1 rotate_left(x->parent); //case 1 w=x->parent->right; //case 1 } if(w->left!=NULL&&w->right!=NULL) { if(w->left->color==BLACK&&w->right->color==BLACK) { w->color=RED; //case2 x=x->parent; //case2 } else { if(w->right->color=BLACK) { w->left->color=BLACK; //case 3 w->color=RED; //case 3 rotate_right(w); //case 3 w=x->parent->right; //case 3 } w->color=x->parent->color; //case 4 x->parent->color=BLACK; //case 4 w->right->color=BLACK; //case 4 rotate_left(x->parent); //case 4 x=Tree.root; } } } } else (Trường hợp x là con phải thực hiện tương tự) x->color=BLACK; } .Thời Gian Tính: -Tìm nút thay thế có thời gian là O(logn). -Thủ tục deletefix(x) sẽ thực hiện đến khi x là gốc như vậy sẽ duyệt lên gốc nên có thời gian là : O(logn). =>Tổng thời gian tính của thuật toán delete() là :O(logn). 6.Tìm Kiếm(Search): -Vì cây đỏ đen là cây nhị phân nên tìm kiếm giống như trên cây nhị phân thông thường: Xuất phát từ nút gốc,nếu khóa cần tìm lớn hơn nút gốc thì ta tìm trên cây con trái,nếu khóa lớn hơn gốc thì ta tìm trên cây con phải. Khi tìm được sẽ trả lại nút có khóa tìm được,ngược lại trả lại con trỏ NULL -Thuật toán tìm kiếm trên cây đỏ đen: pNode *search(Data key) { pNode *x=Tree.root; while(x->info!=key||x!=NULL) { if(x->info>key) x=x->left; else x=x->right; } return x; } .Thời Gian Tính: -Cũng giống như các cây nhị phân khác,thời gian tìm kiếm trung bình là O(logn).Tuy nhiên với những cây nhị phân bình thường thì trong trường hợp tồi nhất có thời gian là O(n) nhưng với cây đỏ đen vẫn đảm bảo thời gian là O(logn) trong trường hợp tồi nhất.Ta thấy rõ điều này vì theo định lí 3 ta có : Một cây đỏ đen có n nút có chiều cao h<=2log(n+1) (Định lí 3). Chương trình minh họa:• Các phép toán của cây đỏ đen được thực hiện trong file redblack.h.• Chương trình mô tả các hàm được thực hiên trong file main.cpp. III.Ứng Dụng Bài Toán cướp biển: a.Bài Toán: Tác phẩm truyện tranh onepiece nổi tiếng của tác giả người Nhật Bản Oda đã chiếm được nhiều tình cảm của các độc giả trên toàn thế giới và đã được chuyển thể thành phim hoạt hình thu hút người xem nhiều nhất trong các anime từng công chiếu.Câu chuyện kể về Luffy có ước mơ tìm được kho báu vĩ đại onepiece và trở thành vua hải tặc,hành trình của cậu trải qua nhiều khó khăn và phải chiến đấu với Hải Quân cũng như những cướp biển hùng mạnh khác.Để thể hiện sự nguy hiểm của hải tặc,chính quyền thế giới đã treo mức truy nã(đơn vị Beri) cho các hải tặc,mức truy nã càng cao thì hải tặc đó càng nguy hiểm.Mức truy nã thấp nhất là 100.000 Beri và cao nhất là 1.000.000.000 Beri đồng thời các hải tặc có số tiền truy nã khác nhau ,và các mức truy nã là bội số của 100.000.Một lần,tại 1 vùng biển tập trung một số lượng lớn hải tặc và chính quyền thế giới không muốn bỏ lỡ cơ hội tiêu diệt bọn chúng.Để phân công nhiệm vụ tiêu diệt hải tặc cho cấp dưới,tùy vào sức mạnh của câp dưới và mức truy nã của hải tặc.Thủy Sư Đô Đốc Sengoku cần phải xếp thuộc hạ của mình tiêu diệt những hải tặc nào. Yêu cầu:Hãy sắp xếp mức truy nã của các hải tặc tăng dần để giúp Thủy Sư Đô Đốc Sengoku dễ dàng phân công nhiệm vụ. Input: Dòng đầu là số hải tặc n(n<=10.000) n dòng tiếp theo mỗi dòng chứa tên(không dấu cách) và số tiền truy nã của hải tặc(là số nguyên =<10.000). Output:Dãy tên và số tiền truy nã tương ứng đã được sắp xếp. b.Thuật Giải: - Ta sẽ sử dụng cấu trúc dữ liệu cây đỏ đên để sắp xếp mức truy nã. - Đầu tiên ta chèn các số tiền tương ứng vào cây đỏ đen và dùng mảng ten[i] để lưu lại tên của hải tặc có mức truy nã là i . - Sau khi đã chèn vào cây đỏ đen,ta duyệt theo thứ tự giữa bắt đầu tại gốc.Kết quả sau khi duyệt chính là dãy đã sắp xếp tăng dần. c.Thuật Toán và Thời Gian Tính: *Chèn số tiền vào cây đỏ đen: for(i=1;i<=n;i++) { fflush(stdin); scanf("%s%d",&s,&m); strcpy(ten[m],s); //tên tương ứng insert(m); } *Duyệt cây: void trysort(pNode*x) { if(x==NULL||x->info==-1) return; trysort(x->left); dem++; printf("%d.%s: %d 00000 Beri \n",dem,ten[x->info],x->info); trysort(x->right); } *Thời Gian Tính: Thủ tục insert() có thời gian là O(logn).Do đó vòng lặp chèn n giá trị vào cây có thời gian là O(nlogn). Thủ tục duyệt cây trysort() sẽ duyệt qua tất cả các nút mỗi nút 1 lần nên có thời gian là O(n). ==> Thời Gian Tính của bài toán là O(nlogn) (cây đỏ đen là cây tự cân bằng nên bài toán luốn có thời gian tính là O(nlogn). **Chương trình được thực thi trong file onepiece.cpp** d.Ví dụ minh họa và cách sử dụng: *Ví dụ: Input: so hai tac:3 luff 4000 law 4120 kid 3150 Output: 1.kid 315000000 2.luff 400000000 3.law 412000000 *Cách sử dụng: Nhập tên mỗi hải tặc và số tiền tương ứng trên cùng 1 dòng và cách nhau 1 dấu cách.********************************************************************************** Cảm ơn thầy đã đọc báo cáo cây đỏ đen của em.Báo cáo còn nhiều sai sót vì có nhiều vẫn đề em chưa hiểu hết,mong thầy góp ý để em hiểu rõ và hoàn thiện hơn.

Tài liệu liên quan

Cây (tree)
- 80
- 432
- 1
CẤU TRÚC CÂY (TREES)
- 30
- 493
- 0
CẤU TRÚC DỮ LIỆU CÂY (TREE)
- 26
- 801
- 2
Trees, Hierarchies, and Graphs
- 63
- 421
- 0
Shell Process Tree
- 10
- 378
- 0
Red Hat Enterprise Linux 5 Administration - Unleashed
- 618
- 509
- 2
inux Toolbox 1000 Commands for Fedora CentOS and Red Hat Power Users - Introduction
- 6
- 425
- 1
The JSP Files (Part 3) - Black Light and White Rabbits
- 20
- 410
- 0
Black Box and White Box testing
- 9
- 596
- 1
Module 10: Creating and Managing Trees and Forests
- 62
- 504
- 0