Bài giảng Cấu trúc dữ liệu và giải thuật: Cây đỏ-đen và cây AA có nội dung trình bày về độ cao của cây nhị phân tìm kiếm (BST) cân bằng có N nodes là O(log2N), cây cân bằng có chi phí thấp, có nhiều cách xây dựng cây nhị phân tìm kiếm cân bằng, . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | Cấu trúc dữ liệu amp Giải thuật Data structures amp Algorithms Cây đỏ-đen và cây AA Advanced data structures Review Giới thiệu Cây Đỏ Đen Red Black Tree AA Tree 09 2013 Data Structures amp Algorithms - Red Black AA tree - Nguyen Tri Tuan 2 Review Độ cao của cây nhị phân tìm kiếm BST cân bằng có N nodes là O log2N Cây cân bằng có chi phí thấp Có nhiều cách xây dựng cây nhị phân tìm kiếm cân bằng AVL tree Red-Black tree AA tree Splay tree 09 2013 Data Structures amp Algorithms - Red Black AA tree - Nguyen Tri Tuan 3 Giới thiệu Các thuật ngữ thường dùng BST AVL tree Red Black tree AA tree Splay tree Top-down splay tree 09 2013 Data Structures amp Algorithms - Red Black AA tree - Nguyen Tri Tuan 4 Cây cân bằng Red Black và AA Review Giới thiệu Cây Đỏ Đen Red Black Tree AA Tree 09 2013 Data Structures amp Algorithms - Red Black AA tree - Nguyen Tri Tuan 5 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á 09 2013 Data Structures amp Algorithms - Red Black AA tree - Nguyen Tri Tuan 6 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 09 2013 Data Structures amp Algorithms - Red Black AA tree - Nguyen Tri Tuan 7 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 09 2013 Data Structures amp Algorithms - Red Black AA tree - Nguyen Tri Tuan 8 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 đỏ-đỏ 09 2013 .
