intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Báo cáo - Cấu trúc dữ liệu - Cây đỏ đen

Chia sẻ: Son Nguu | Ngày: | Loại File: PDF | Số trang:31

Thêm vào BST
Báo xấu
755
lượt xem 139
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Cây đỏ đen là một trong những cấu trức dữ liệu hay, cùng với cây nhị phân tìm kiếm là những cấu trúc dữ liệu có điểm mạnh trong việc lưu trữ và tìm kiếm dữ liệu. Song cây đỏ đen có những đặc tính riêng mà nhờ đó nó đã làm nổi bật những điểm mạnh của mình. Trong phạm vi bài báo cáo này, chúng em xin trình bài về : khái quát cây đỏ đen, các thuật toán cơ bản, code cài đặt các thuật tóan cơ bản và có những nhận xét về cấu trúc cây đỏ đen này. Chúng em chân thành...

Chủ đề:

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

Lưu

Nội dung Text: Báo cáo - Cấu trúc dữ liệu - Cây đỏ đen

  1. TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CẤU TRÚC DỮ LIỆU 2 Lời nói đầu: Cây đỏ đen là một trong những cấu trức dữ liệu hay, cùng với cây nhị phân tìm kiếm là những cấu trúc dữ liệu có điểm mạnh trong việc lưu trữ và tìm kiếm dữ liệu. Song cây đỏ đen có những đặc tính riêng mà nhờ đó nó đã làm nổi bật những điểm mạnh của mình. Trong phạm vi bài báo cáo này, chúng em xin trình bài về : khái quát cây đỏ đen, các thuật toán cơ bản, code cài đặt các thuật tóan cơ bản và có những nhận xét về cấu trúc cây đỏ đen này. Chúng em chân thành cam ơn cô Phạm Phạm Tuyết Trinh đã tạo điều kiện cho chúng em tìm hiểu đề tài lý thú này. Dù hết sức cố gắng song vẫn không tránh được những sai xót nhất định chúng em mong được sư mong nhận được những đóng góp chân tình để bài làm trở nên hòan chỉnh hơn. Nhóm thực hiện
  2. Cây Đỏ Đen Mục lục: Lời nói đầu: ..................................................................................................................... 1 Mục lục:........................................................................................................................... 2 I- Giới thiệu: ................................................................................................................ 3 II- Định nghĩa: .......................................................................................................... 5 III- Các thuật toán cơ bản của Black and Red Tree............................................... 6 1- Thêm một Node mới ........................................................................................... 6 2- Xóa một node:.................................................................................................... 14 IV- Thuật toán cài đặt: ............................................................................................ 14 V- Nhận xét : ........................................................................................................... 31 2
  3. Cây Đỏ Đen I- Giới thiệu: Cây đỏ đen được ra giới thiệu bởi Rudolf Bayer trong quyển “Symmetric Binary B-Trees: Data Structure and maintenance Algorithms”, nhà xuất bản Acta Informatica, Tâp1, trang 290-306. Sau đó Leonidas J.Guibas và Robert Sedgewick đã thêm các đặc tính của cây đỏ đen và đặt tên cho nó ( Tham khảo: Guibas, L. and Sedgewick R. “ A dichromatic Framwork for Balanced Trees”, in Proc. 19th IEEE Symp. Foundations of Computer Science, trang 8-21, năm 1978). Ta đã biết cây tìm kiếm nhị phân thông thường có những thuận lợi lớn về mặt lưu trữ và truy xuất dữ liệu trong phép toán tìm kiếm thêm vào hay loại bỏ một phần tử. Do đó, cây tìm kiếm nhị phân xem ra là một cấu trúc lưu trữ dữ liệu tốt. 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ố 3
  4. Cây Đỏ Đen 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 . Có nhiều cách tiếp cận khác để bảo đảm cho cây cân bằng: chẳng hạn cây 2-3-4. Tuy vậy, trong phần lớn trường hợp, cây đỏ đen là cây cân bằng hiệu quả nhất, ít ra thì khi dữ liệu được lưu trữ trong bộ nhớ chứ không phải trong những tập tin. Trước khi khảo sát cây đỏ đen, hãy xem lại cây không cân bằng được tạo ra như thế nào. Hình 3.1. Các node được chèn theo thứ tự tăng dần Những node này tự sắp xếp thành một đường không phân nhánh. Bởi vì mỗi node lớn hơn node đã được chèn vào trước đó, mỗi node là con phải. Khi ấy, cây bị mất cân bằng hoàn toàn. Nếu ta chèn những mục (item) theo thứ tự giảm dần, mỗi node sẽ là con trái của node cha của chúng - cây sẽ bị mất cân bằng về phía bên kia. * Độ phức tạp: Khi cây một nhánh, sẽ trở thành một danh sách liên kết, dữ liệu sẽ là một chiều thay vì hai chiều. Trong trường hợp này, thời gian truy xuất giảm về O(N), thay vì O(logN) đối với cây cân bằng. Để bảo đảm thời gian truy xuất nhanh O(logN) của cây, chúng ta cần phải bảo đảm cây luôn luôn cân bằng (ít ra cũng là cây gần cân bằng). Điều này có nghĩa là mỗi node trên cây phải có xấp xỉ số node con bên phải bằng số node con bên trái. Một cách tiếp cận giải quyết vấn đề cân bằng lại cây: đó là cây đỏ đen-là cây tìm kiếm nhị phân vì thế nó có các tính chất của cây tìm kiếm nhị phân ví dụ : node con trái nhỏ hơn node cha, node cha nhỏ hơn node con phải, bên cạnh đó cây đỏ đen còn được bổ sung một số đắc điểm. 4
  5. Cây Đỏ Đen y Tro cây đỏ đen, việc cân bằng đư thực thi trong khi c ong ược chèn, xóa. K thêm m phần Khi một tử thì thủ tục chèn sẽ k c kiểm tra xem tính chấ cân bằng của cây c bị vi ph m ất g có hạm hay ông. Nếu có, sẽ xây d khô dựng lại cấu trúc cây. Bằng cách này, cây lu luôn đư giữ u uôn ược cân bằng. n II- Đị ngh ịnh hĩa: Cây đỏ đen là một cây nh phân tìm kiếm( BST tuân thủ c quy tắc sau: (hình 3.2) y hị T) các Mọi node phải là đỏ hoặc đen. Node gốc và các nod lá phải lu luôn đen de uôn n. Nếu một n node là đỏ, những nod con của n phải đen. de nó Mọi đườn dẫn từ gố đến một lá phải có c ng ốc cùng số lượ node đe ợng en. Kh chèn (hay xóa) một n hi y node mới, c phải tuâ thủ các q tắc trên -gọi là quy tắc đỏ cần ân quy y đen Nếu được tuân thủ, c sẽ được cân bằng. n. c cây c Hình 3.2. Mộ ví dụ về cây đỏ đen H ột Số lượng node đen trên một đườn dẫn từ gố đến lá đư gọi là c ng ốc ược chiều lack height) Ta có thể phát biểu q tắc 4 theo một cách khác cao đen (bl ). quy h là mọi đườn dẫn từ g đến lá phải có cùng chiều cao đen. ng gốc g Bổ đề: Một cây đỏ đen n-nod M ỏ de 5
  6. Cây Đỏ Đen Có: height
  7. Cây Đỏ Đen y · C phép qu khi node đã được c Các uay e chèn. · C phép qu trên đườ đi xuốn Các uay ờng ng. 1.1 1 Các phép lật màu trên đư p ường đi xu uống Phé thêm vào trong cây đỏ đen bắt đầu như trê cây tìm k ép o t ên kiếm nhị ph thông th hân hường: đi ttheo một đư ường dẫn từ node gốc đ vị trí cầ chèn, đi qua phải ha trái tùy v giá ừ đến ần ay vào trị của khóa no và khóa tìm kiếm. ode a Tuy nhiên, tro cây đỏ đ đến đư điểm ch là phức tạp bởi các phép lật m và y ong đen, ược hèn c màu qua ay. Để bảo đảm không vi phạ các quy tắc màu, cần phải tiến hành các p k ạm y n phép lật mà khi àu cần Theo quy tắc như sa nếu phép thêm vào làm xuất hi tình trạn một nod đen n. y au: p iện ng de có hai node co đỏ, chún ta đổi các node con t on ng c thành đen v node cha thành đỏ (trừ khi và a nod cha là no gốc, nó vẫn vẫn giữ màu là đe de ode en). Mộ phép lật màu ảnh hư ột m ưởng đến cá quy tắc đ ác đỏ-đen ra sa chúng ta gọi node ở đỉnh ao? a tam giác, node có màu đỏ trước phép lật là P (P thay cho n m e ỏ p P node cha). C Chúng ta gọ hai ọi nod con trái và phải của P là X1 và X2. Xem h de v a à hình 3.4a. Hìn 3.4. Lật màu nh 7
  8. Cây Đỏ Đen Hình 3.4a. trước khi lật màu, Hình 3.4b sau khi lật màu. Chúng ta nhận thấy sau khi lật màu chiếu con đen của cây không đổi. Như vậy phép lật màu không vi phạm quy tắc 4. Mặc dù quy tắc 4 không bị vi phạm qua phép lật, nhưng quy tắc 3 (một node con và node cha không thể đồng màu đỏ) lại có khả năng bị vi phạm. Nếu node cha của P là đen, không có vấn đề vi phạm khi P chuyển từ đen sang đỏ, nhưng nếu node cha của P là đỏ, thì sau khi đổi màu, ta sẽ có hai node đỏ trên một hàng. Điều này cần phải được chuẩn bị truớc khi đi xuống theo cây để chèn node mới. Chúng ta có thể giải quyết trường hợp này bằng một phép quay. Đối với node gốc thì phép lật màu node gốc và hai node con của nó vẫn làm cho node gốc cũng như hai node con có màu đen. Điều này tránh sự vi phạm quy tắc 2 và quy tắc 3 (xung đột đỏ-đỏ). Trong trường hợp này, chiều cao đen trên mỗi đường đi từ node gốc tăng lên 1, do đó quy tắc 4 cũng không bị vi phạm. 1.2 Các phép quay khi chèn node Thao tác chèn node mới có thể làm cho quy tắc đỏ-đen bị vi phạm. Do vậy sau khi chèn, cần phải kiểm tra xem có phạm quy tắc không và thực hiện những thao tác hợp lý. Như đã xét ở trên, node mới được chèn mà ta gọi là node X, luôn luôn đỏ. Node X có thể nằm ở những vị trí khác nhau đối với P và G, như trong hình 3.5. 8
  9. Cây Đỏ Đen y Hìn 3.5. Các biến dạng của node đư chèn nh ược X l một node cháu ngoạ nếu nó nằ cùng bên node cha P và P cùng bên node cha G. là e ại ằm n g Điề này có nghĩa là, X l node cháu ngoại nếu hoặc nó là node con t của P v P là ều n là u u à trái và nod con trái của G, hoặc nó là node con phải c P và node P là nod con phải của G. de c c e của de Ng gược lại, X là một node cháu nội. l e Nếu X là node cháu ngoạ nó có thể hoặc bên t hoặc bê phải của P, tùy vào việc e ại, ể trái ên nod P ở bên trái hay bên phải node G. Có hai k năng tư de t n khả ương tự nếu X là một n u node chá nội. Bốn trường hợp này được trình bày tr áu n p rong hình 3.5. Tha tác phục hồi quy tắc đỏ-đen đư xác địn bởi các m và cấu h ao c c ược nh màu hình của no X ode và những bà con của nó. Có 3 khả n c năng xảy ra được xem x như sau xét u:(hình 3.6) 9
  10. Cây Đỏ Đen y Hìn 3.6. Ba khả năng sa khi chèn nút nh k au i) K năng 1: P đen Khả ii) K năng 2: P đỏ và X là cháu ng của G Khả 2 goại iii) Khả năng 3: P đỏ và X là cháu n của G nội húng ta lần lượt xét các khả năng c thể như s Ch l c cụ sau: i) K năng 1: P đen Khả P đ là trườn hợp đơn giản. Node thêm vào l đen ng luôn đỏ. Nế node cha đen, không có ếu a g xun khắc đỏ- (quy tắc 3), và khô có việc cộng thêm vào số nod đen (quy tắc 4). ng -đỏ c ông de Do vậy, không bị vi phạm quy tắc về màu. Tha tác chèn đã hoàn tất. o g m ao ii) K năng 2: P đỏ và X là cháu ng của G Khả 2 goại Nếu node P đỏ và X là no cháu ng ỏ ode goại, ta cần một phép qquay đơn gi và một v iản vài tha đổi về mà Bắt đầu với giá trị 50 tại node gốc, và ch các node 25, 75 và 12. Ta ay àu. u e hèn e cần phải làm một phép lậ màu trước khi chèn n n m ật c node 12. 10
  11. Cây Đỏ Đen y Bây giờ, chèn node mới X là 6. (hìn 3.7a. )xuấ hiện lỗi: cha và con đều đỏ, vì v cần y nh ất vậy phả có các thao tác như sau: (hình 3 ải 3.7) Tro trường hợp này, ta có thể áp d ong a dụng ba bướ để phục hồi tính đỏ ớc ỏ-đen và làm cho m cân bằng cây. Sau đây là các bước ấ n ấy: Đổi Đ màu nod G - node ông bà của node X (tr de e a rong thí dụ này là node 25). e Đổi Đ màu nod P - node cha của node X (node 12) de e Quay với node G (25) ở vị trí đỉnh, theo huớn làm nâng node X lên (6). Đây l một Q ng g n là phé quay phả ép ải. Kh ta hoàn tấ ba buớc tr sẽ bảo t hi ất rên toàn cây đỏ đen. Xem hình 3.7b. Tro thí dụ này, node X là node ch ngoại củ một node con trái. C một trườ hợp ong n háu ủa e Có ờng đối xứng khi node X là n i n node cháu ng nhưng của một no con phả Thử làm điều goài g ode ải. m này bằng cách tạo nên câ 50, 25, 75 87, 93 (v phép lật màu khi cầ Chỉnh s cây y h ây 5, với ần). sửa bằn cách đổi màu node 75 và 87, v quay trái với node 75 là node đỉnh. Một lầ nữa ng và ần cây lại được cân bằng. y c 11
  12. Cây Đỏ Đen y Hìn 3.7. Nod P đỏ và X là node ch ngoại nh de háu iii) Khả năng 3: P đỏ và X là cháu n của G nội Nếu node P đỏ và X là no cháu nộ chúng ta cần thực h hai phé quay và m vài ỏ ode ội, a hiện ép một phé đổi màu. Cây đỏ đe được tạo thành từ cá node 50, 25, 75, 12 và 18. (cần phải ép . en ác n lật màu trước khi chèn no 12). Xe hình 3.8a. ode em Lưu ý là node 18 là node cháu nội. N u Node này và node cha đều đỏ (cha và con đề đỏ). a ều 12
  13. Cây Đỏ Đen y hình 3.8.c Hìn 3.8. Khả năng 3: P đỏ và X là n nh ả node cháu n nội hỉnh lại sự sắ xếp này cũng khá rắ rối hơn. Nếu ta cố q Ch ắp ắc quay phải n node ông bà G (25) à ởđđỉnh, như ta đã làm tron khả năng 2, node ch trong X (18) đi ng a ng g háu gang hơn là đi lên, như thế cây sẽ không còn cân bằng n trước. ( ư ẽ n như (Thử làm điều này, rồi quay trở lạ với i ại, nod 12 ở đỉnh để phục h cây nhu cũ). Phải c một giả pháp khác de h, hồi u cần ải c. 13
  14. Cây Đỏ Đen y Thủ thuật cần dùng khi X là node ch nội là ti hành ha phép quay hơn là mộ phép. ủ háu iến ai y ột Phé quay đầu biến X từ một node c ép u cháu nội thà node ch ngoại, n trong h ành háu như hình 3.8 Bây giờ, trường hợp là tương t như khả n 8b. , p tự năng 1, và t có thể áp dụng cùng một ta p g phé quay, vớ node ông bà ở đỉnh, như đã làm trước đây. Kết quả nh trong hìn 3.8c. ép ới m hư nh Ch húng ta cũng cần tô mà lại các nú Ta làm đ này trư khi làm bất cứ phép quay g àu út. điều ước p nào (thứ tự kh o hông quan tr rọng, nhưng nếu ta đợi đến khi sa khi quay mới tô màu lại g i au u nod thì khó mà biết phải gọi chúng như thế nà Các bướ là: de m i g ào). ớc Đổi Đ màu nod ông bà củ node X ( node 25). de ủa Đ màu nod X (không phải màu của node cha; node X đây là nod 18). Đổi de g de Quay với node P - node cha của X - ở đỉnh (k Q e không phải v node ôn bà; node cha với ng đây là 12). y Quay lần nữa với node ông bà của X (25) ở đỉ về hướ nâng X lên (quay p Q a ỉnh, ớng phải). 2- Xóa m node: một : Chú ta đã bi trong cậy nhị phân t kiếm vi xóa 1 ph tử ra kh cây úng iết y tìm iệc hần hỏi thì khó khăn ph tạp hơn việc insert 1 phần tử vào cậy, và ở cây đỏ đ k hức n à đen cũn vậy, thậm chí còn ph tạp hơn vì trong qu trình thê vào phải đảm ng m hức n uá êm i bảo qui tắc của cây đỏ đen o a n. IV- Th huật toá cài đ án đặt: typ pedef enum { STATUS_OK K, STATUS_ME EM_EXHAU USTED, STATUS_DU UPLICATE_ _KEY, STATUS_KE EY_NOT_FOUND }S StatusEnum m; 14
  15. Cây Đỏ Đen typedef int KeyType; /* Kiểu dữ liệu khoá */ /* Dữ liệu lưu trữ */ typedef struct { int stuff } RecType; #define compLT(a,b) (a < b) #define compEQ(a,b) (a == b) /* Khai báo cấu trúc dữ liêu */ typedef enum { BLACK, RED } nodeColor; typedef struct NodeTag { struct NodeTag *left; /* Con trái */ struct NodeTag *right; /* Con phải */ struct NodeTag *parent; /* Cha */ nodeColor color; /* Màu node (BLACK, RED) */ KeyType key; /* Khoá sử dụng tìm kiếm */ RecType rec; /* Dữ liệu node */ } NodeType; typedef NodeType *iterator; #define NIL &sentinel /* Node cầm canh */ static NodeType sentinel = { &sentinel, &sentinel, 0, BLACK, 0}; static NodeType *root = NIL; /* Node gốc */ 15
  16. Cây Đỏ Đen /************************** * Xoay tráI node x * **************************/ static void rotateLeft(NodeType *x) { NodeType *y = x->right; /* Thiết lập liên kết x->right */ x->right = y->left; if (y->left != NIL) y->left->parent = x; /* Thiết lập liên kết y->parent */ if (y != NIL) y->parent = x->parent; if (x->parent) { if (x == x->parent->left) x->parent->left = y; else x->parent->right = y; } else { root = y; } /* link x and y */ y->left = x; if (x != NIL) x->parent = y; 16
  17. Cây Đỏ Đen } static void rotateRight(NodeType *x) { /**************************** * Xoay node x bên phải * ****************************/ NodeType *y = x->left; /* Thiết lập liên kết x->left */ x->left = y->right; if (y->right != NIL) y->right->parent = x; /* Thiết lập liên kết y->parent */ if (y != NIL) y->parent = x->parent; if (x->parent) { if (x == x->parent->right) x->parent->right = y; else x->parent->left = y; } else { root = y; } /* liên kết x và y */ y->right = x; 17
  18. Cây Đỏ Đen if (x != NIL) x->parent = y; } /************************************* * Chương trình chính thêm node x vào cây đỏ đen* *************************************/ static void insertFixup(NodeType *x) { /* Kiểm tra thuộc tính đỏ đen */ while (x != root && x->parent->color == RED) { /* we have a violation */ if (x->parent == x->parent->parent->left) { NodeType *y = x->parent->parent->right; if (y->color == RED) { /* chú bác là RED */ x->parent->color = BLACK; y->color = BLACK; x->parent->parent->color = RED; x = x->parent->parent; } else { /* chú bác là BLACK */ if (x == x->parent->right) { /* tạo ra x là con trái*/ 18
  19. Cây Đỏ Đen x = x->parent; rotateLeft(x); } /* đổi màu và xoay */ x->parent->color = BLACK; x->parent->parent->color = RED; rotateRight(x->parent->parent); } } else { /* Tương tự như trên */ NodeType *y = x->parent->parent->left; if (y->color == RED) { /* chú bác là is RED */ x->parent->color = BLACK; y->color = BLACK; x->parent->parent->color = RED; x = x->parent->parent; } else { /* chú bác là BLACK */ if (x == x->parent->left) { x = x->parent; 19
  20. Cây Đỏ Đen rotateRight(x); } } x->parent->color = BLACK; x->parent->parent->color = RED; rotateLeft(x->parent->parent); } } root->color = BLACK; } /*********************************************** * Cấp phát và thêm vào trên cây * ***********************************************/ StatusEnum insert(KeyType key, RecType *rec) { NodeType *current, *parent, *x; /Tìm cha mới*/ current = root; parent = 0; while (current != NIL) { if (compEQ(key, current->key)) return STATUS_DUPLICATE_KEY; 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

TL.01: Bộ Tiểu Luận Triết Học
207 tài liệu
1470 lượt tải
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.

 

Đồng bộ tài khoản
2=>2