tailieunhanh - Cấu trúc dữ liệu : CÂY ĐỎ ĐEN part 1

BÀI 6: CÂY ĐỎ ĐEN 1. 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. | BÀI 6 CÂY ĐỎ ĐEN 1. 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 . 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 1. Các node được chèn theo thứ tự tăng dần 1 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 của nút trước đó. Khi ấy cây bị mất cân bằng hoàn toàn. Độ 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 log2N đối với cây cân bằng. Để bảo đảm thời gian truy xuất nhanh 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. 2. ĐỊNH NGHĨA CÂY ĐỎ ĐEN Cây đỏ đen là một cây nhị phân tìm kiếm BST tuân thủ các quy tắc sau hình 2 1 Mọi node phải là đỏ hoặc đen. 2 Node gốc và các node lá NIL phải luôn luôn đen. 3 Nếu một node là đỏ những node con của nó phải đen. 4 Mọi đường dẫn từ gốc đến một lá phải có cùng số lượng node đen. Khi chèn hay xóa một node mới cần phải tuân .