TAILIEUCHUNG - Bài giảng Phân tích thiết kế và giải thuật - Chương 6: 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" 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

• Kỹ thuật lập trình
• Bài giảng Phân tích thiết kế
• Phân tích thiết kế dữ liệu
• Thiết kế giải thuật
• Cây đỏ đen
• Tính chất cây đỏ đen
• Cân bằng lại theo kiểu bottom up
• phân tích thiết kế hệ thống
• giáo trình phân tích thiết kế hệ thống
• bài giảng phân tích thiết kế hệ thống
• bài tập phân tích thiết kế hệ thốn
• tài liệu phân tích thiết kế hệ thốngg
• Phân tích thiết kế giải thuật
• Kỹ thuật thiết kế giải thuật
• Bài giảng thiết kế giải thuật
• Kỹ thuật phân tích thiết kế giải thuật
• Bài giảng phân tích thiết kế giải thuật
• Thiết kế hệ thống
• Thiết kế cơ sở dữ liệu
• Phân tích cơ sở dữ liệu
• Cơ sở dữ liệu
• Thiết kế CSDL logic
• Bài giảng Phân tích thiết kế hệ thống TMĐT
• Phân tích thiết kế hệ thống thương mại điện tử
• Phân tích hệ thống thương mại điện tử
• Thiết kế tổng thể hệ thống thương mại điện tử
• Thiết kế chi tiết hệ thống thương mại điện tử
• Thiết kế phân đoạn trình diễn
• Thiết kế tổng thể hệ thống
• Kiểm tra thiết kế tổng thể
• Mục đích thiết kế hệ thống thông tin
• Thiết kế giao diện
• Thiết kế các tài liệu ra
• Thiết kế mẫu thu thập thông tin
• Phân tích thiết kế thuật toán
• Phân tích thuật toán
• Thiết kế thuật toán
• Bài giảng Phân tích thiết kế thuật toán
• Bài giảng Phân tích thiết kế hướng đối tượng
• Phân tích thiết kế hướng đối tượng
• Thiết kế hướng đối tượng
• Phân tích và thiết kế hệ thống ở trạng thái tĩnh
• Thiết kế hệ thống ở trạng thái tĩnh
• Phân tích và thiết kế hệ thống ở trạng thái động
• Thiết kế hệ thống ở trạng thái động
• Phương pháp phân tích thuật toán
• Vai trò của phân tích thuật toán
• Quá trình phân tích thuật toán
• Thiết kế bài giảng Giải tích 12
• Thiết kế bài giảng Giải tích
• Bài giảng Giải tích
• Thiết kế bài giảng
• Bài giảng Nguyên hàm
• Bài giảng Tích phân
• Thiết kế chương trình
• Thiết kế cấu trúc
• Lập lược đồ chương trình
• tài liệu phân tích thiết kế hệ thống
• Phân tích chức năng của hệ thống
• Mô hình khung cảnh
• Mô hình dòng dữ liệu
• Mô hình phân rã chức năng