Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen trình bày định nghĩa cây đỏ đen, cấu trúc dữ liệu cho nút cây đỏ đen, các phép biến đổi cây đỏ đen cân bằng, các tình huống xảy ra khi duyệt ngược, . Mời các bạn cùng tham khảo. | CẤU TRÚC DỮ LIỆU CÂY ĐỎ ĐEN Bùi Tiến Lên 01 01 2017 https tailieudientucntt Cây đỏ đen Định nghĩa 1 Cây đỏ đen red black tree được Rudolf Bayer phát minh và là một cây nhị phân tìm kiếm có các đặc điểm sau 1. Mọi nút phải là nút đỏ hoặc nút đen 2. Nút gốc là nút đen 3. Nếu một nút là nút đỏ thì con của nó phải nút đen 4. Tất cả các đường đi từ nút gốc đến nút-0 không có con hoặc nút-1 có 1 con phải có cùng số lượng nút đen điều kiện cân bằng Nhận xét Cây đỏ đen là cây tổng quát của cây AVL Spring 2017 Data structure amp Algorithm https tailieudientucntt 2 Cây đỏ đen cont. 13 8 17 1 11 15 25 6 22 27 Hình 1 Cây đỏ đen Spring 2017 Data structure amp Algorithm https tailieudientucntt 3 Cấu trúc dữ liệu cho nút cây đỏ đen Cấu trúc dữ liệu để lưu trữ cho nút cây đỏ đen 1 template 2 struct RBNode 3 4 T data 5 int key 6 NodeColor color 7 RBNode pLeft 8 RBNode pRight 9 RBNode pParent 10 Spring 2017 Data structure amp Algorithm https tailieudientucntt 4 Tìm kiếm và duyệt I Vì cây đỏ đen là một cây nhị phân tìm kiếm do đó tìm kiếm và duyệt cây trên cây đỏ đen tương tự như trên cây nhị phân tìm kiếm Spring 2017 Data structure amp Algorithm https tailieudientucntt 5 Các phép biến đổi cây đỏ đen cân bằng Có ba phép biển đổi dùng để điều chỉnh cho cây đỏ đen cân bằng I Thay đổi màu change color I Thực hiện xoay trái left rotation I Thực hiện xoay phải right rotation Spring 2017 Data structure amp Algorithm https tailieudientucntt 6 Các phép biến đổi cây đỏ đen cân bằng cont. Thực hiện xoay trái giữa hai nút P và N trong đó N là nút con phải của P P N T1 N P T3 T2 T3 T1 T2 a trước khi xoay b sau khi xoay Hình 2 Thao tác xoay trái Spring 2017 Data structure amp Algorithm https tailieudientucntt 7 Các phép biến đổi cây đỏ đen cân bằng cont. Thực hiện xoay phải giữa hai nút P và N trong đó