Bài giảng "Phân tích thiết kế và giải thuật - Chương 6: Cây đỏ đen" cung cấp cho người học các kiến thức: Giới thiệu, định nghĩa và tính chất cây đỏ đen, phép quay, cân bằng lại theo kiểu bottom-up, thêm nút mới, loại bỏ nút, tính hiệu quả của cây đỏ đen | Bài giảng Phân tích thiết kế và giải thuật - Chương 6 Cây đỏ đen CÂY ĐỎ ĐEN 1 1 Nội dung Giới thiệu Định nghĩa và tính chất cây đỏ đen Phép quay cân bằng lại theo kiểu bottom-up Thêm nút mới Loại bỏ nút Tính hiệu quả của cây đỏ đen Cài đặt 2 Cây tìm kiếm nhị phân binary search tree Cây tìm kiếm nhị phân TKNP là cây nhị phân mà khoá tại mỗi nút lớn hơn khoá của tất cả các nút thuộc cây con bên trái và nhỏ hơn khoá của tất cả các nút thuộc cây con bên phải. 20 10 35 5 17 22 42 15 37 3 Giới thiệu Cây tìm kiếm nhị phân 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ử. cây TKNP là một CTDL tốt. Hạn chế 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ây nhị phân trở nên không cân bằng. Lệch về bên trái hoặc bên phải . Khi cây không cân bằng khả năng tìm kiếm nhanh hoặc chèn hoặc xóa một phần tử đã cho hạn chế Cây không cân bằng gt giải quyết đó là cây đỏ đen là cây tìm kiếm nhị phân có thêm một vài đặc điểm. 4 Giới thiệu Các node được chèn theo thứ tự tăng dần 5 Định nghĩa Cây đỏ đen red-black trees Cây đỏ đen là một cây nhị phân tìm kiếm BST với các thuộc tính 1. Mọi node đều được tô màu đỏ hoặc màu đ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 là đen. Trên mọi đường dẫn từ gốc đến nút lá không có 2 node đỏ liên tiếp 4. Mọi đường dẫn từ gốc đến một lá phải có cùng số lượng node đen. 6 Định nghĩa cây đỏ đen Số lượng node đen trên một đường dẫn từ gốc đến lá được gọi là chiều cao đen black height . Ta có thể phát biểu quy tắc 4 theo một cách khác là mọi đường dẫn từ gốc đến lá phải có cùng chiều cao đen. 11 2 14 1 7 15 5 8 7 Mỗi nút là đỏ hoặc đen 8 Nút gốc và các nút lá NIL có màu đen 9 Nếu một nút đen các con của nó có màu đỏ. 10 Phép quay rotations Để cân bằng cây 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 di chuyển một vài node qua bên phải. Điều này làm được nhờ các phép quay. Phép quay
