Giáo trình Cấu trúc dữ liệu 2: Phần 2 - Trương Hải Bằng (biên soạn)

Chia sẻ: Hoa La Hoa | Ngày: | Loại File: PDF | Số trang:60

Thêm vào BST

Báo xấu

96
lượt xem 24
download

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

Phần 2 Giáo trình Cấu trúc dữ liệu 2 do tác giả Trương Hải Bằng biên soạn tiếp tục giới thiệu đến bạn đọc các nội dung tiếp theo về chương 3 và chương 4. Theo đó, chương 3 giới thiệu đến bạn đọc nội dung về cây đỏ đen, chương 4 giới thiệu về B-tree và bộ nhớ ngoài. Giáo trình trình bày kết hợp giữa nội dung và hình vẽ minh họa với sau mỗi chương đều có tóm tắt từng chương giúp cho các bạn sinh viên ngành Công nghệ thông tin và bạn đọc dễ dàng nghiên cứu và học tập.

Chủ đề:

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

Lưu

Nội dung Text: Giáo trình Cấu trúc dữ liệu 2: Phần 2 - Trương Hải Bằng (biên soạn)

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 3 bằng: đó là cây đỏ đen, là cây tìm kiếm nhị phân có thêm một vài CHƯƠNG 3 – CÂY ĐỎ ĐEN đặ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 1. GIỚI THIỆU 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ây tìm kiếm nhị phân thông thường có những thuận lợi lớn về mặt được tạo ra như thế nào. 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 Những node này tự sắp xếp thành một đường không phân nhánh. cấu trúc lưu trữ dữ liệu tốt. 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 Tuy nhiên trong một số trường hợp cây tìm kiếm nhị phân có một số những mục (item) theo thứ tự giảm dần, mỗi node sẽ là con trái của hạn chế. Nó hoạt động tốt nếu dữ liệu được chèn vào cây theo thứ tự node cha của chúng - cây sẽ bị mất cân bằng về phía bên kia. ngẫu nhiên. Tuy nhiên, nếu dữ liệu được chèn vào theo thứ tự đã được sắp xếp sẽ không hiệu quả. Khi các trị số cần chèn đã được sắp Độ phức tạ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 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à phần tử đã cho. 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 được bổ sung một số đặc điểm. Trong cây đỏ đen, việc cân bằng được thực thi trong khi chèn, xóa. Khi thêm một phần tử thì thủ tục chèn sẽ kiểm tra xem tính chất cân bằng của cây có bị vi phạm hay không. Nếu có, sẽ xây dựng lại cấu trúc cây. Bằng cách này, cây luôn luôn được giữ cân bằng. Hình 3.1 Các node được chèn theo thứ tự tăng dần 125 126
2. ĐỊNH NGHĨA CÂY ĐỎ ĐEN Thời gian tìm kiếm: O( log n ) Cây đỏ đen là một cây nhị phân tìm kiếm( BST) tuân thủ các quy tắc 3. PHÉP QUAY sau: (hình 3.2) Mọi node phải là đỏ hoặc đen. Để cân bằng cây, cần phải tái sắp xếp node về mặt vật lý. Nếu tất cả các node nằm bên trái node gốc, ta cần phải di chuyển một vài node Node gốc và các node lá phải luôn luôn đen. qua bên phải. Điều này làm được nhờ các phép quay. Trong phần Nếu một node là đỏ, những node con của nó phải đen. này, chúng ta sẽ học phép quay là gì và làm sao thực hiện những phép quay này. Mọi đường dẫn từ gốc đến một lá phải có cùng số lượng node đen. Phép quay là cách tái sắp xếp các nút, chúng được thiết kế làm các Khi chèn (hay xóa) một node mới, cần phải tuân thủ các quy tắc trên công việc sau: -gọi là quy tắc đỏ đen. Nếu được tuân thủ, cây sẽ được cân bằng. Nâng một số node lên và hạ một số khác xuống để giúp cân bằng cây. Bảo đảm những tính chất của cây tìm kiếm nhị phân không bị vi phạm. Trong cây tìm kiếm nhị phân, các node con trái có giá trị khóa nhỏ hơn node gốc, trong khi các node con phải có giá trị khóa lớn hơn hay bằng node gốc. Phép quay phải đảm bảo tính chất này. Quay là gì? Thuật ngữ quay có thể bị hiểu nhầm. Thực ra quay không có nghĩa Hình 3.2 Một ví dụ về cây đỏ đen là các node bị quay mà để chỉ sự thay đổi quan hệ giữa chúng. Một Số lượng node đen trên một đường dẫn từ gốc đến lá được gọi là node được chọn làm "đỉnh" của phép quay. Nếu chúng ta đang thực chiều cao đen (black height). Ta có thể phát biểu quy tắc 4 theo một hiện một phép quay qua phải, node "đỉnh" này sẽ di chuyển xuống cách khác là mọi đường dẫn từ gốc đến lá phải có cùng chiều cao dưới và về bên phải, vào vị trí của node con bên phải của nó. Node đen. con bên trái sẽ đi lên để chiếm lấy vị trí của nó. Bổ đề: Một cây đỏ đen n-node Node đỉnh không phải là "tâm" của phép quay. Nếu lấy bánh xe hơi làm ví dụ, vị trí node đỉnh không ở trục của mâm bánh xe, mà đúng Có: height
i) Các phép lật màu trên đường đi xuống Phép thêm vào trong cây đỏ đen bắt đầu như trên cây tìm kiếm nhị phân thông thường: đi theo một đường dẫn từ node gốc đến vị trí • cần chèn, đi qua phải hay trái tùy vào giá trị của khóa node và khóa tìm kiếm. • Tuy nhiên, trong cây đỏ đen, đến được điểm chèn là phức tạp bởi Hình 3.3. Phép quay các phép lật màu và quay. Để bảo đảm không vi phạm các quy tắc màu, cần phải tiến hành các •Kết quả của hai phép quay thứ cây trong phép duyệt không thay đổi: phép lật màu khi cần. Theo quy tắc như sau: nếu phép thêm vào làm • AxByC xuất hiện tình trạng một node đen có hai node con đỏ, chúng ta đổi các node con thành đen và node cha thành đỏ (trừ khi node cha là Ta phải đảm bảo là nếu làm phép quay phải, node đỉnh phải có node node gốc, nó vẫn vẫn giữ màu là đen). 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. Một phép lật màu ảnh hưởng đến các quy tắc đỏ-đen ra sao? chúng ta gọi node ở đỉnh tam giác, node có màu đỏ trước phép lật là P (P 4. THÊM NODE MỚI thay cho node cha). Chúng ta gọi hai node con trái và phải của P là X1 và X2. Xem hình 3.4a. Chúng ta sẽ xem xét việc mô tả qui trình chèn. Gọi X, P, và G để chỉ định nhãn những node liên quan. X là node vi phạm quy tắc ( X có thể là một node mới được chèn, hoặc node con khi node cha và node P P con xung đột đỏ-đỏ, nghĩa là có cùng màu đỏ). a. b.  X là một node cho trước  P là node cha của X X1 X2  G là node ông bà của X (node cha của P). X1 X2 Trong quá trình thêm vào node mới có thể vi phạm các quy tắc của cây đỏ đen, chúng ta sẽ thực hiện các thao tác sau đây:  Các phép lật màu trên đường đi xuống  Các phép quay khi node đã được chèn Hình 3.4a. Trước khi lật màu Hình 3.4b sau khi lật màu.  Các phép quay trên đường đi xuống. 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. 129 130
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 G G P chuyển từ đen sang đỏ, nhưng nếu node cha của P là đỏ, thì sau a khi đổi màu, ta sẽ có hai node đỏ trên một hàng. . b X là cháu X là cháu Điều này cần phải được chuẩn bị trước khi đi xuống theo cây để . P ngoại nội chèn node mới. Chúng ta có thể giải quyết trường hợp này bằng một P 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 X X 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. ii) Các phép quay khi chèn node G G X là cháu Thao tác chèn node mới có thể làm cho quy tắc đỏ-đen bị vi phạm. nội d Do vậy sau khi chèn, cần phải kiểm tra xem có phạm quy tắc không c và thực hiện những thao tác hợp lý. . . X là cháu P Như đã xét ở trên, node mới được chèn mà ta gọi là node X, luôn P ngoại 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. X X là một node cháu ngoại nếu nó nằm cùng bên node cha P và P X G cùng bên node cha G. Điều này có nghĩa là, X là node cháu ngoại nếu hoặc nó là node con trái của P và P là node con trái của G, hoặc Hình 3.5 Các biến dạng của node được chèn nó là node con phải của P và node P là node con phải của G. Ngược lại, X là một node cháu nội. Nếu X là node cháu ngoại, nó có thể hoặc bên trái hoặc bên phải của P, tùy vào việc node P ở bên trái hay bên phải node G. Có hai khả năng tương tự nếu X là một node cháu nội. Bốn trường hợp này được trình bày trong hình 3.5. Thao tác phục hồi quy tắc đỏ-đen được xác định bởi các màu và cấu hình của node X và những bà con của nó. Có ba khả năng xảy ra được xem xét như sau(hình 3.6) 131 132
ii) Khả năng 2: P đỏ và X là cháu ngoại của G G Nếu node P đỏ và X là node cháu ngoại, ta cần một phép quay đơn G giản và một vài thay đổi về màu. Bắt đầu với giá trị 50 tại node gốc, . (i) và chèn các node 25, 75 và 12. Ta cần phải làm một phép lật màu (ii) trước khi chèn node 12. P P Bây giờ, chèn node mới X là 6 (hình 3.7a.) xuất hiện lỗi: cha và con đều đỏ, vì vậy cần phải có các thao tác như sau: (hình 3.7) Trong trường hợp này, ta có thể áp dụng ba bước để phục hồi tính P đỏ-đen và làm cho cân bằng cây. Sau đây là các bước ấy: X 1. Đổi màu node G - node ông bà của node X (trong thí dụ này là node 25). G 2. Đổi màu node P - node cha của node X (node 12) 3. Quay với node G (25) ở vị trí đỉnh, theo hướng làm nâng P node X lên (6). Đây là một phép quay phải. Khi ta hoàn tất ba buớc trên sẽ bảo toàn cây đỏ đen. Xem hình 3.7b. (iii) Trong thí dụ này, node X là node cháu ngoại của một node con trái. X Có một trường hợp đối xứng khi node X là node cháu ngoài nhưng của một node con phải. Thử làm điều này bằng cách tạo nên cây 50, Hình 3.6 Ba khả năng sau khi chèn nút 25, 75, 87, 93 (với phép lật màu khi cần). Chỉnh sửa cây bằng cách đổi màu node 75 và 87, và quay trái với node 75 là node đỉnh. Một i) Khả năng 1: P đen lần nữa cây lại được cân bằng. ii) Khả năng 2: P đỏ và X là cháu ngoại của G iii) Khả năng 3: P đỏ và X là cháu nội của G Chúng ta lần lượt xét các khả năng cụ thể như sau: i) Khả năng 1: P đen P đen là trường hợp đơn giản. Node thêm vào luôn đỏ. Nếu node cha đen, không có xung khắc đỏ-đỏ (quy tắc 3), và không có việc cộng thêm vào số node đen (quy tắc 4). Do vậy, không bị vi phạm quy tắc về màu. Thao tác chèn đã hoàn tất. 133 134
50 50 6 a) G 25 75 G 25 Đổi màu Ñoåi maøu 75 5 0 Xoay 12 P 12 P X Ñoåi maøu Xoay 18 Đổi màu 6 a. 50 50 75 12 25 75 b) 18 6 25 Xoay b. 12 Hình 3.7 Node P đỏ và X là node cháu ngoại 50 iii) Khả năng 3: P đỏ và X là cháu nội của G c) 18 75 Nếu node P đỏ và X là node cháu nội, chúng ta cần thực hiện hai phép quay và một vài phép đổi màu. Cây đỏ đen được tạo thành từ các node 50, 25, 75, 12 và 18. (cần phải lật màu trước khi chèn node 12 25 12), xem hình 3.8a. Lưu ý là node 18 là node cháu nội. Node này và node cha đều đỏ (cha và con đều đỏ). Hình 3.8 Khả năng 3: P đỏ và X là node cháu nội 135 136
Chỉnh lại sự sắp xếp này cũng khá rắc rối hơn. Nếu ta cố quay phải 6. TÍNH HIỆU QUẢ CỦA CÂY ĐỎ ĐEN node ông bà G (25) ở đỉnh, như ta đã làm trong khả năng 2, node cháu trong X (18) đi ngang hơn là đi lên, như thế cây sẽ không còn Giống như cây tìm kiếm nhị phân thông thường, cây đỏ đen có thể cân bằng như trước. (Thử làm điều này, rồi quay trở lại, với node 12 cho phép việc tìm kiếm, chèn và xóa trong thời gian O(log2N). Thời ở đỉnh, để phục hồi cây như cũ). Phải cần một giải pháp khác. gian tìm kiếm là gần như bằng nhau đối với hai loại cây, vì những Thủ thuật cần dùng khi X là node cháu nội là tiến hành hai phép đặc điểm của cây đỏ đen không sử dụng trong quá trình tìm kiếm. quay hơn là một phép. Phép quay đầu biến X từ một node cháu nội Điều bất lợi là việc lưu trữ cần cho mỗi node tăng chút ít để điều tiết thành node cháu ngoại, như trong hình 3.8b. Bây giờ, trường hợp là màu đỏ-đen (một biến boolean). tương tự như khả năng 1, và ta có thể áp dụng cùng một phép quay, Đặc thù hơn, theo Sedgewick, trong thực tế tìm kiếm trên cây đỏ với node ông bà ở đỉnh, như đã làm trước đây. Kết quả như trong đen mất khoảng log2N phép so sánh, và có thể chứng minh rằng nó hình 3.8c. không cần hơn 2*log2N phép so sánh. Chúng ta cũng cần tô màu lại các nút. Ta làm điều này trước khi làm Thời gian chèn và xóa tăng dần bởi một hằng số vì việc phải thực thi bất cứ phép quay nào (thứ tự không quan trọng, nhưng nếu ta đợi phép lật màu và quay trên đường đi xuống và tại những điểm chèn. đến khi sau khi quay mới tô màu lại node thì khó mà biết phải gọi Trung bình một phép chèn cần khoảng chừng một phép quay. Do chúng như thế nào). Các bước là: đó, chèn hãy còn chiếm O(log2N) thời gian, nhưng lại chậm hơn 1. Đổi màu node ông bà của node X ( node 25). phép chèn trong cây nhị phân thường. 2. Đổi màu node X (không phải màu của node cha; node X đây Bởi vì trong hầu hết các ứng dụng, có nhiều thao tác tìm kiếm hơn là là node 18). chèn và xóa, có lẽ không có nhiều bất lợi về thời gian khi dùng cây đỏ đen thay vì cây nhị phân thuờng. Dĩ nhiên, điều thuận lợi là trong 3. Quay với node P - node cha của X - ở đỉnh (không phải với cây đỏ đen, dữ liệu đã sắp xếp không làm giảm hiệu suất O(N). node ông bà; node cha đây là 12). Một trở ngại trong cây đỏ đen là việc cài đặt các phép toán phức tạp 4. Quay lần nữa với node ông bà của X (25) ở đỉnh, về hướng hơn so với cây BST. Chúng ta có thể tham khảo các phép toán thêm nâng X lên (quay phải). vào và loại bỏ trong phần cài đặt. 5. LOẠI BỎ NODE 7. CÀI ĐẶT Trong cây BST chúng ta thấy rằng phép loại bỏ phức tạp hơn so với phép thêm vào. Trong cây đỏ đen phép loại bỏ càng phức tạp hơn rất nhiều so với phép thêm vào vì yêu cầu đảm bảo quy tắc đỏ đen. Chúng ta có thể tham khảo trong phần cài đặt. 137 138
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) */ y là chú bác của x KeyType key; /* Khoá sử dụng tìm kiếm */ RecType rec; /* Dữ liệu node */ } NodeType; typedef enum { STATUS_OK, typedef NodeType *iterator; STATUS_MEM_EXHAUSTED, STATUS_DUPLICATE_KEY, #define NIL &sentinel /* Node cầm canh */ STATUS_KEY_NOT_FOUND static NodeType sentinel = { &sentinel, &sentinel, 0, BLACK, 0}; } StatusEnum; static NodeType *root = NIL; /* Node gốc */ typedef int KeyType; /* Kiểu dữ liệu khoá */ static void rotateLeft(NodeType *x) { /* Dữ liệu lưu trữ */ typedef struct { /********************************************************* int stuff} RecType; * Xoay tráI node x * *********************************************************/ #define compLT(a,b) (a < b) #define compEQ(a,b) (a == b) NodeType *y = x->right; /* Khai báo cấu trúc dữ liêu */ /* Thiết lập liên kết x->right */ typedef enum { BLACK, RED } nodeColor; x->right = y->left; 139 140
if (y->left != NIL) y->left->parent = x; 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; /* Thiết lập liên kết y->parent */ if (x->parent) { if (y != NIL) y->parent = x->parent; if (x == x->parent->left) if (x->parent) { x->parent->left = y; if (x == x->parent->right) else x->parent->right = y; x->parent->right = y; else } else { x->parent->left = y; root = y; } else { } root = y; } /* link x and y */ y->left = x; /* liên kết x và y */ if (x != NIL) x->parent = y; y->right = x; } if (x != NIL) x->parent = y; } static void rotateRight(NodeType *x) { static void insertFixup(NodeType *x) { /********************************************************* * Xoay node x bên phải * /********************************************************* *********************************************************/ * Chương trình chính thêm node x vào cây đỏ đen* *********************************************************/ NodeType *y = x->left; /* Kiểm tra thuộc tính đỏ đen */ while (x != root && x->parent->color == RED) { /* Thiết lập liên kết x->left */ 141 142
/* vi phạm thuộc tính đỏ đen */ NodeType *y = x->parent->parent->left; if (x->parent == x->parent->parent->left) { if (y->color == RED) { NodeType *y = x->parent->parent->right; if (y->color == RED) { /* chú bác là is RED */ x->parent->color = BLACK; /* chú bác là RED */ y->color = BLACK; x->parent->color = BLACK; x->parent->parent->color = RED; y->color = BLACK; x = x->parent->parent; x->parent->parent->color = RED; } else { x = x->parent->parent; } else { /* chú bác là BLACK */ if (x == x->parent->left) { /* chú bác là BLACK */ x = x->parent; if (x == x->parent->right) { rotateRight(x); /* tạo ra x là con trái*/ } x = x->parent; x->parent->color = BLACK; rotateLeft(x); x->parent->parent->color = RED; } rotateLeft(x->parent->parent); } /* đổi màu và xoay */ } x->parent->color = BLACK; } x->parent->parent->color = RED; root->color = BLACK; rotateRight(x->parent->parent); } } } else { StatusEnum insert(KeyType key, RecType *rec) { NodeType *current, *parent, *x; /* Tương tự như trên */ 143 144
/********************************************************* if(compLT(key, parent->key)) * Cấp phát và thêm vào trên cây * parent->left = x; *********************************************************/ else parent->right = x; /Tìm cha mới*/ } else { current = root; root = x; parent = 0; } while (current != NIL) { if (compEQ(key, current->key)) insertFixup(x); return STATUS_DUPLICATE_KEY; parent = current; return STATUS_OK; current = compLT(key, current->key) ? } current->left : current->right; } void deleteFixup(NodeType *x) { /* Thiết lập node mới */ /********************************************************* if ((x = malloc (sizeof(*x))) == 0) * Chương trình chính loại bỏ node x * return STATUS_MEM_EXHAUSTED; *********************************************************/ x->parent = parent; x->left = NIL; while (x != root && x->color == BLACK) { x->right = NIL; if (x == x->parent->left) { x->color = RED; NodeType *w = x->parent->right; x->key = key; if (w->color == RED) { x->rec = *rec; w->color = BLACK; x->parent->color = RED; /* Thêm node */ rotateLeft (x->parent); if(parent) { w = x->parent->right; 145 146
} x = x->parent; if (w->left->color == BLACK && w->right->color == BLACK) { } else { w->color = RED; if (w->left->color == BLACK) { x = x->parent; w->right->color = BLACK; } else { w->color = RED; if (w->right->color == BLACK) { rotateLeft (w); w->left->color = BLACK; w = x->parent->left; w->color = RED; } rotateRight (w); w->color = x->parent->color; w = x->parent->right; x->parent->color = BLACK; } w->left->color = BLACK; w->color = x->parent->color; rotateRight (x->parent); x->parent->color = BLACK; x = root; w->right->color = BLACK; } rotateLeft (x->parent); } x = root; } } x->color = BLACK; } else { } NodeType *w = x->parent->left; if (w->color == RED) { StatusEnum erase(iterator z) { w->color = BLACK; NodeType *x, *y; x->parent->color = RED; if (z->left == NIL || z->right == NIL) { rotateRight (x->parent); /* y có một node con là NIL */ w = x->parent->left; y = z; } } else { if (w->right->color == BLACK && w->left->color == BLACK) { /* Tìm cây thay thế với node con NIL */ w->color = RED; y = z->right; 147 148
while (y->left != NIL) y = y->left; } return STATUS_OK; } /* y chỉ có một con */ if (y->left != NIL) StatusEnum eraseKey(KeyType key) { x = y->left; NodeType *z; else /* Tìm node */ x = y->right; z = root; while(z != NIL) { /* Xoá y */ if(compEQ(key, z->key)) x->parent = y->parent; break; if (y->parent) else if (y == y->parent->left) z = compLT(key, z->key) ? z->left : z->right; y->parent->left = x; } else if (z == NIL) return STATUS_KEY_NOT_FOUND; y->parent->right = x; return erase(z); else } root = x; iterator next(iterator i) { if (y != z) { if (i->right != NIL) { z->key = y->key; z->rec = y->rec; for (i = i->right; i->left != NIL; i = i->left); } } else { iterator p = i->parent; if (y->color == BLACK) while (p && i == p->right) { deleteFixup (x); i = p; free (y); p = p->parent; 149 150
} if(compEQ(key, current->key)) { *iter = current; /* trả về node "inorder" */ return STATUS_OK; i = p; } else { } current = compLT (key, current->key) ? return i; current->left : current->right; } } } iterator begin() { return STATUS_KEY_NOT_FOUND; /* Trả về con trỏ đến giá trị đầu tiên */ } iterator i; for (i = root; i->left != NIL; i = i->left); int main(int argc, char **argv) { return i; int maxnum, ct, n; } RecType rec; KeyType key; iterator end() { StatusEnum status; /* Trả về con trỏ đến giá trị cuối cùng */ return NULL; /* Chạy bằng dòng lệnh: } * RecType value(iterator i) { * rbt maxnum return i->rec; * } * rbt 2000 * Xử lý 2000 records StatusEnum find(KeyType key, iterator *iter) { * NodeType *current; */ current = root; while(current != NIL) { iterator iter; 151 152
} maxnum = atoi(argv[1]); return 0; } printf("maxnum = %d\n", maxnum); for (ct = maxnum; ct; ct--) { THẢO LUẬN VỀ CÂY CÂN BẰNG key = rand() % 90 + 1; Cây AVL là cây cân bằng xuất hiện sớm nhất. Nó được đặt tên theo if ((status = find(key, &iter)) == STATUS_OK) { nhà phát minh Adelson Velskii và Landis. Trong cây AVL mỗi node rec = value(iter); lưu trữ một mẫu dữ liệu phụ: sự khác biệt chiều cao của cây con bên if (rec.stuff != key) printf("fail rec\n"); trái và bên phải. Sự khác biệt này không thể lớn hơn 1. Có nghĩa là chiều cao cây con bên trái của node không thể là hơn một mức khác status = erase(iter); với chiều cao của cây con bên phải. if (status) printf("fail: status = %d\n", status); Lần theo việc chèn, cần kiểm tra node gốc của cây con thấp nhất mà } else { node mới cần được chèn vào. Nếu chiều cao của nhũng node con rec.stuff = key; khác nhau hơn 1, cần phải tiến hành một phép quay đơn hay quay status = insert(key, &rec); kép để cân bằng chiều cao của chúng. Thuật toán lúc đó sẽ di chuyển lên và kiểm tra những node ở trên, cân bằng chiều cao nếu if (status) printf("fail: status = %d\n", status); cần. Điều này tiếp tục tiến hành thụt lùi đến node gốc. } Thời gian tìm kiếm trong cây AVL là O(logN) vì cây là được bảo } đảm cân bằng. Tuy nhiên vì phải đi qua cây hai lần để chèn hay xóa một nút, một lần đi xuống để tìm điểm chèn và một lần đi lên để tái cân bằng cây, cây AVL là cây đỏ đen không hiệu quả và không /* Hiển thị các node */ thường được sử dụng . { Một loại cây cân bằng quan trọng khác là cây nhiều nhánh iterator i; (Multiway Tree), trong đó mỗi node có thể có hơn hai node con. Chúng ta sẽ xét một phiên bản của cây nhiều nhánh, cây 2-3-4 trong for (i = begin(); i != end(); i = next(i)) { phần tiếp theo. Một vấn đề cho cây nhiều nhánh là mỗi node phải lớn hơn so với cây nhị phân, bởi vì chúng cần tham khảo mỗi node RecType rec; con của nó. rec = value(i); printf("%d\n", rec.stuff); } 153 154
TÓM TẮT  Cây tìm kiếm nhị phân được cân bằng giảm thời gian tìm kiếm.  Thao tác chèn dữ liệu đã được sắp xếp trước có thể tạo nên một cây hoàn toàn mất cân bằng, cây này sẽ có thời gian tìm kiếm là O(N).  Trong cây đỏ đen, mỗi node được gán cho một đặc tính mới: một màu có thể hoặc là đỏ hay đen.  Quy tắc đỏ-đen, chỉ ra cách sắp xếp những node khác màu.  Một phép lật màu đổi một node đen với hai node con đỏ thành một node đỏ với hai node đen.  Trong phép quay, một node được chỉ định là node đỉnh.  Một phép quay phải di chuyển node đỉnh vào vị trí của node con phải của nó, và node con trái của node đỉnh vào vị trí node đỉnh.  Một phép quay trái di chuyển node đỉnh vào vị trí của node con trái của nó và node con phải của node đỉnh vào vị trí node đỉnh.  Các phép lật màu, và đôi khi các phép quay, được sử dụng trong khi đi xuống cây để tìm nơi chèn node mới. Những phép lật màu này chỉ phục hồi tính đỏ-đen của cây sau khi chèn nút.  Sau khi đã chèn một node mới, cần phải rà soát lại xem có xung khắc đỏ-đỏ không. Nếu có, phải tiến hành các phép quay để làm cho cây đúng quy tắc đỏ-đen.  Những điều chỉnh này làm cho cây được cân bằng hay gần như cân bằng.  Việc bổ sung tính cân bằng cho cây nhị phân chỉ tác động ít lên hiệu suất trung bình, và tránh được hiệu suất thấp trong trường hợp xấu nhất khi dữ liệu đã được sắp xếp. 155 156
4 50 CHƯƠNG 4 – B-TREE VÀ BỘ NHỚ NGOÀI 30 60, 70, 80 Đối với cây nhị phân, mỗi node chỉ có một mục dữ liệu và có thể có hai node con. Nếu chúng ta cho phép một node có nhiều mục dữ liệu 10, 20 20 55 62, 64, 66 75 83, 86 và nhiều node con thì kết quả là ta được cây nhiều nhánh. Cây 2-3-4 là cây nhiều nhánh mà mỗi node của nó có thể có đến bốn node con và có ba mục dữ liệu. Hình 4.1 Cây 2-3-4 Để bước đầu làm quen với B-tree chúng ta khảo sát cây 2-3-4. Cây 2-3-4 là cây cân bằng giống như cây đỏ-đen. Tuy nhiên, ít hiệu quả Các số 2, 3 và 4 trong cụm từ cây 2-3-4 có ý nghĩa là khả năng có hơn cây đỏ-đen nhưng ngược lại chúng lại dễ lập trình. bao nhiêu liên kết đến các node con có thể có được trong một node B-tree là một dạng của cây nhiều nhánh, B-tree đặc biệt hữu dụng cho trước. Đối với các node không phải là lá, có thể có ba cách sắp đối với việc tổ chức dữ liệu ở bộ nhớ ngoài. Một node trong B-tree xếp sau: có thể có hàng chục thậm chí hàng trăm node con. Chúng ta sẽ thảo - Một node với một mục dữ liệu thì luôn luôn có 2 con. luận về bộ nhớ ngoài và B-tree trong phần tiếp theo. - Một node với hai mục dữ liệu thì luôn luôn có 3 con. 1. CÂY 2-3-4 - Một node với ba mục dữ liệu thì luôn luôn có 4 con. Như vậy, một node không phải là lá phải luôn luôn có số node con 1.1. Giới thiệu về cây 2-3-4 nhiều hơn 1 so với số mục dữ liệu của nó. Nói cách khác, đối với mọi node với số con là l và số mục dữ liệu là d, thì : l = d + 1 Chúng ta sẽ xem xét các đặc tính của cây 2-3-4 và mối quan hệ khá gần gũi giữa cây 2-3-4 và cây đỏ-đen. Hình 4.1 trình bày một cây 2-3-4 đơn giản. Mỗi node có thể lưu trữ 1, 2 hoặc 3 mục dữ liệu. 155 156
node, và một node với bốn liên kết gọi là một 4-node, nhưng ở đây 0 không có loại node nào là 1-node. 25 2- node 1.2. Tổ chức cây 2-3-4 0 1 Các mục dữ liệu trong mỗi node được sắp xếp theo thứ tự tăng dần từ trái sang phải (sắp xếp từ thấp đến cao). 12 33, 37 Một đặc tính quan trọng của bất kỳ cấu trúc cây là mối liên hệ giữa 0 1 các liên kết với giá trị khóa của các mục dữ liệu. Trong cây tìm 40, 62 3- node kiếm nhị phân, tất cả node của cây con bên trái có khoá nhỏ hơn khóa của node đang xét và tất cả node của cây con bên phải có khoá lớn hơn hoặc bằng khóa của node đang xét. Trong cây 2-3-4 thì 0 1 2 nguyên tắc cũng giống như trên, nhưng có thêm một số điểm sau: 27, 33 - Tất cả các node con của cây con có gốc tại node con thứ 0 51, 55, 59 83 thì có các giá trị khoá nhỏ hơn khoá 0. - Tất cả các node con của cây con có gốc tại node con thứ 1 0 1 953 thì có các giá trị khoá lớn hơn khoá 0 và nhỏ hơn khoá 1. 50,75, 4- node - Tất cả các node con của cây con có gốc tại node con thứ 2 thì có các giá trị khoá lớn hơn khoá 1 và nhỏ hơn khoá 2. 0 1 2 3 - Tất cả các node con của cây con có gốc tại node con thứ 3 thì có 30, 35 55 78 100, 105 các giá trị khoá lớn hơn khoá 2. Trong tất cả cây 2-3-4, các lá đều nằm trên cùng một mức. Các node Hình 4.2. Các trường hợp của cây 2-3-4 ở mức trên thường không đầy đủ, nghĩa là chúng có thể chứa chỉ 1 Với mọi node lá thì không có node con nhưng có thể chứa 1, 2 hoặc hoặc 2 mục dữ liệu thay vì 3 mục. 3 mục dữ liệu, không có node rỗng. Lưu ý rằng cây 2-3-4 là cây cân bằng. Nó vẫn giữ được sự cân bằng Một cây 2-3-4 có thể có đến bốn cây con nên được gọi là cây nhiều khi thêm vào các phần tử có thứ tự (tăng dần hoặc giảm dần). nhánh bậc 4. 1.3. Tìm kiếm Trong cây 2-3-4 mỗi node có ít nhất là hai liên kết, trừ lnode lá (node không có liên kết nào). Thao tác tìm kiếm trong cây 2-3-4 tương tự như thủ tục tìm kiếm Hình 4.2 trình bày các trường hợp của cây 2-3-4. Một node với hai trong cây nhị phân. Việc tìm kiếm bắt đầu từ node gốc và chọn liên liên kết gọi là một 2-node, một node với ba liên kết gọi là một 3- kết dẫn đến cây con với phạm vi giá trị phù hợp. 157 158
Ví dụ, để tìm kiếm mục dữ liệu với khoá là 64 trên cây ở hình 4.1, 28, 35 bạn bắt đầu từ gốc. Tại node gốc không tìm thấy mục khoá này. Bởi vì 64 lớn 50, chúng ta đi đến node con 1, (60/70/80)(lưu ý node con 1 nằm bên phải, bởi vì việc đánh số của các node con và các liên kết 11 42 74 bắt đầu tại 0 từ bên trái). Tại vị trí này vẫn không tìm thấy mục dữ liệu, vì thế phải đi đến node con tiếp theo. Tại đây bởi vì 64 lớn hơn 60 nhưng nhỏ hơn 70 nên đi tiếp đến node con 1. Tại thời điểm chúng ta tìm được mục dữ liệu đã cho với liên kết là 62/64/66. 5, 9 13, 23 30 44, 47 63, 67, 72 97 1.4. Thêm vào (i) Các mục dữ liệu mới luôn luôn được chèn vào tại các node lá . Nếu mục dữ liệu được thêm vào node mà có node con, thì số lượng của các node con cần thiết phải được chuyển đổi để duy trì cấu trúc cho 28, 35 cây, đây là lý do tại sao phải có số node con nhiều hơn 1 so với các mục dữ liệu trong một nút. Việc thêm vào cây 2-3-4 trong bất cứ trường hợp nào thì quá trình 11 Thªm vµo 18 42 74 cũng bắt đầu bằng cách tìm kiếm node lá phù hợp. Nếu không có node đầy nào (node có đủ 3 mục dữ liệu) được bắt gặp trong quá trình tìm kiếm, việc chèn vào khá là dễ dàng. Khi 5, 9 13,18, 23 30 44, 47 63, 67, 72 97 node lá phù hợp được tìm thấy, mục dữ liệu mới đơn giản là thêm vào nó. Hình 4.3 trình bày một mục dữ liệu với khoá 18 được thêm (ii) vào cây 2-3-4. Việc chèn vào có thể dẫn đến phải di chuyển một hoặc hai mục dữ Hình 4.3 Chèn vào không làm tách cây liệu trong node vì thế các khoá sẽ nằm với trật tự đúng sau khi mục dữ liệu mới được thêm vào. Trong ví dụ này số 23 phải được đẩy i) trước khi chèn vào sang phải để nhường chỗ cho 18. ii) sau khi chèn vào  Tách nút Việc thêm vào sẽ trở nên phức tạp hơn nếu gặp phải một node đầy (node có số mục dữ liệu đầy đủ) trên nhánh dẫn đến điểm thêm vào. Khi điều này xảy ra, node này cần thiết phải được tách ra. Quá trình tách nhằm giữ cho cây cân bằng. Loại cây 2-3-4 mà chúng ta đề cập 159 160
ở đây thường được gọi là cây 2-3-4 top-down bởi vì các node được 62 tách ra theo hướng đi xuống điểm chèn. Tách node Giả sử ta đặt tên các mục dữ liệu trên node bị phân chia là A, B và C. Sau đây là tiến trình tách (chúng ta giả sử rằng node bị tách 29 83, 92, 104 không phải là node gốc; chúng ta sẽ kiểm tra việc tách node gốc sau này): A B C - Một node mới và rỗng được tạo. Nó là anh em với node sẽ được 15, 21 47 74 87, 89 97 112 tách và được đưa vào bên phải của nó. - Mục dữ liệu C được chuyển vào node mới. (i) Trước khi chèn - Mục dữ liệu B được chuyển vào node cha của node được tách. - Mục dữ liệu A không thay đổi. 62, 92 Đưa 92 lên - Hai node con bên phải nhất bị hủy kết nối từ node được tách và B Node míi kết nối đến node mới. §-a 104 qua ph¶i Một ví dụ về việc tách node trình bày trên hình 4.4. Một cách khác 29 83 104 để mô tả sự tách node là một 4-node được chuyển đổi sang hai 2- A C nút. Chú ý rằng ảnh hưởng của sự tách node là dịch chuyển dữ liệu đi 15, 21 47 74 87, 89 97, 99 112 lên về bên phải. Sự sắp xếp lại này nhằm mục đích giữ cho cây cân bằng. (ii) Sau khi chÌn 99 ®-îc thªm vµo Hình 4.4: Tách một nút  Tách node gốc Khi gặp phải node gốc đầy tại thời điểm bắt đầu tìm kiếm điểm chèn, kết quả của việc tách thực hiện như sau: - Node mới được tạo ra để trở thành gốc mới và là cha của node được tách. - Node mới thứ hai được tạo ra để trở thành anh em với node được tách. - Mục dữ liệu C được dịch chuyển sang node anh em mới. 161 162