Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Cây cân bằng Red Black và AA - Nguyễn Tri Tuấn

Bài giảng "Cấu trúc dữ liệu và giải thuật: Cây cân bằng Red Black và AA" cung cấp cho người đọc các định nghĩa về cây cân bằng Red Black, cấu trúc lưu trữ, các tính chất cây cân bằng Red Black, các thao tác cơ bản. Mời các bạn cùng tham khảo. | Cây cân bằng Red Black và AA Review Giới thiệu Cây Đỏ Đen Red Black Tree AA Tree Winter 2011 Data Structures amp Algorithms - Red Black AA tree - Nguyen Tri Tuan DH.KHTN Tp.HCM 5 CuuDuongThanCong.com https fb.com tailieudientucntt Red Black Tree Định nghĩa Cấu trúc lưu trữ Các tính chất Các thao tác cơ bản Đánh giá Winter 2011 Data Structures amp Algorithms - Red Black AA tree - Nguyen Tri Tuan DH.KHTN Tp.HCM 6 CuuDuongThanCong.com https fb.com tailieudientucntt Red Black Tree tt Định nghĩa Red-Black tree là một cây nhị phân tìm kiếm BST tuân thủ các quy tắc sau 1 Mọi node phải là đỏ hoặc đen 2 Node gốc là đen 3 Các node ngoài external node NULL node mặc định là những node đen 4 Nếu một node là đỏ những node con của nó phải là đen 5 Mọi đường dẫn từ gốc đến node ngoài phải có cùng số lượng node đen Winter 2011 Data Structures amp Algorithms - Red Black AA tree - Nguyen Tri Tuan DH.KHTN Tp.HCM 7 CuuDuongThanCong.com https fb.com tailieudientucntt Red Black Tree tt H 4 H 3 Hb 2 Hb 2 H 3 Hb 2 H 2 H 1 H 2 Hb 1 Hb 1 Hb 1 H 1 Hb 1 Minh họa Red-Black tree Winter 2011 Data Structures amp Algorithms - Red Black AA tree - Nguyen Tri Tuan DH.KHTN Tp.HCM 8 CuuDuongThanCong.com https fb.com tailieudientucntt Red Black Tree tt Chiều cao đen black height hb x là số node đen trên đường đi từ node x đến node ngoài không bao gồm x Từ quy tắc 4 không thể tồn tại node cha và node con cùng đỏ. Khi cây đỏ đen vi phạm qui tắc này gọi là hiện tượng xung đột đỏ-đỏ Winter 2011 Data Structures amp Algorithms - Red Black AA tree - Nguyen Tri Tuan DH.KHTN Tp.HCM 9 CuuDuongThanCong.com https fb.com tailieudientucntt Red Black Tree tt Cấu trúc lưu trữ Thông tin lưu trữ tại Node key Địa chỉ node gốc của cây con bên trái pLeft Địa chỉ node gốc của cây con bên phải pRight Địa chỉ của node cha pParent Thuộc tính màu của node color Winter 2011 Data Structures amp Algorithms - Red Black AA tree - Nguyen Tri Tuan DH.KHTN Tp.HCM 10 CuuDuongThanCong.com https fb.com tailieudientucntt Red Black Tree tt .