Cấu trúc dữ liệu - Chương 3: Cây đỏ đen

Y; parent = current; current = compLT(key, current->key) ? current->left : current->right; } /* Thiết lập node mới */ if ((x = malloc (sizeof(*x))) == 0) return STATUS_MEM_EXHAUSTED; x->parent = parent; x->left = NIL; x->right = NIL; x->color = RED; x->key = key; x->rec = *rec; /* Thêm node */ if(parent) { if(compLT(key, parent->key)) parent->left = x; else parent->right = x; } else { root = x; } insertFixup(x); return STATUS_OK; } /************************************* * Chương trình chính loại bỏ node x * *************************************/ void deleteFixup(NodeType *x) { while (x != root && x->color == BLACK) { if (x == x->parent->left) { NodeType *w = x->parent->right; if (w->color == RED) { w->color = BLACK; x->parent->color = RED; rotateLeft (x->parent); w = x->parent->right; } if (w->left->color == BLACK && w->right->color == BLACK) { w->color = RED; x = x->parent; } else { if (w->right->color == BLACK) { w->left->color = BLACK; w->color = RED; rotateRight (w); w = x->parent->right; } w->color = x->parent->color; Trương Hải Bằng – Cấu trúc dữ liệu 2 Chương 3: Cây đỏ đen Trang 13 x->parent->color = BLACK; w->right->color = BLACK; rotateLeft (x->parent); x = root; } } else { NodeType *w = x->parent->left; if (w->color == RED) { w->color = BLACK; x->parent->color = RED; rotateRight (x->parent); w = x->parent->left; } if (w->right->color == BLACK && w->left->color == BLACK) { w->color = RED; x = x->parent; } else { if (w->left->color == BLACK) { w->right->color = BLACK; w->color = RED; rotateLeft (w); w = x->parent->left; } w->color = x->parent->color; x->parent->color = BLACK; w->left->color = BLACK; rotateRight (x->parent); x = root; } } } x->color = BLACK; } StatusEnum erase(iterator z) { NodeType *x, *y; if (z->left == NIL || z->right == NIL) { /* y có một node con là NIL */ y = z; } else { /* Tìm cây thay thế với node con NIL */ y = z->right; while (y->left != NIL) y = y->left; } /* y chỉ có một con */ if (y->left != NIL) x = y->left; else x = y->right; /* Xoá y */ x->parent = y->parent; if (y->parent) if (y == y->parent->left) y->parent->left = x; else y->parent->right = x; else Trương Hải Bằng – Cấu trúc dữ liệu 2 Chương 3: Cây đỏ đen Trang 14 root = x; if (y != z) { z->key = y->key; z->rec = y->rec; } if (y->color == BLACK) deleteFixup (x); free (y); return STATUS_OK; } StatusEnum eraseKey(KeyType key) { NodeType *z; /* Tìm node */ z = root; while(z != NIL) { if(compEQ(key, z->key)) break; else z = compLT(key, z->key) ? z->left : z->right; } if (z == NIL) return STATUS_KEY_NOT_FOUND; return erase(z); } iterator next(iterator i) { if (i->right != NIL) { for (i = i->right; i->left != NIL; i = i->left); } else { iterator p = i->parent; while (p && i == p->right) { i = p; p = p->parent; } /* trả về node "inorder" */ i = p; } return i; } iterator begin() { /* Trả về con trỏ đến giá trị đầu tiên */ iterator i; for (i = root; i->left != NIL; i = i->left); return i; } iterator end() { /* Trả về con trỏ đến giá trị cuối cùng */ return NULL; } RecType value(iterator i) { return i->rec; } StatusEnum find(KeyType key, iterator *iter) { NodeType *current; current = root; while(current != NIL) { if(compEQ(key, current->key)) { Trương Hải Bằng – Cấu trúc dữ liệu 2 Chương 3: Cây đỏ đen Trang 15 *iter = current; return STATUS_OK; } else { current = compLT (key, current->key) ? current->left : current->right; } } return STATUS_KEY_NOT_FOUND; } int main(int argc, char **argv) { int maxnum, ct, n; RecType rec; KeyType key; StatusEnum status; /* Chạy bằng dòng lệnh: * * rbt maxnum * * rbt 2000 * Xữ lý 2000 records * */ iterator iter; maxnum = atoi(argv[1]); printf("maxnum = %d\n", maxnum); for (ct = maxnum; ct; ct--) { key = rand() % 90 + 1; if ((status = find(key, &iter)) == STATUS_OK) { rec = value(iter); if (rec.stuff != key) printf("fail rec\n"); status = erase(iter); if (status) printf("fail: status = %d\n", status); } else { rec.stuff = key; status = insert(key, &rec); if (status) printf("fail: status = %d\n", status); } /* Hiễn thị các node */ { iterator i; for (i = begin(); i != end(); i = next(i)) { RecType rec; rec = value(i); printf("%d\n", rec.stuff); } } return 0; } Trương Hải Bằng – Cấu trúc dữ liệu 2 Chương 3: Cây đỏ đen Trang 16 THẢO LUẬN VỀ CÂY CÂN BẰNG Cây AVL là cây cân bằng xuất hiện sớm nhất. Nó được đặt tên theo nhà phát minh Adelson Velskii và Landis. Trong cây AVL mỗi node 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 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 với chiều cao của cây con bên phải. 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à node mới cần được chèn vào. Nếu chiều cao của nhũng node con khác nhau hơn 1, cần phải tiến hành một phép quay đơn hay quay 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 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 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 (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 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 con của nó. 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 trong trường hợp xấu nhất (worst-case performance) khi dữ liệu đã được sắp xếp.