Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tham khảo tài liệu 'cẩm nang thuật toán tập 1 part 7', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | CÁC CÂY 2-3-4 lừ TRÊN XUỐNG 251 Hình 15.3 Xổy dựng một 2-3-4 cây Để chèn một nút mới vào một 2-3-4 cây chúng ta thực hiện một quá trình tìm kiếm không thành công và sau dó móc nút mới vào. Nếu kết thúc quá trình tìm kiếm ở một 2-nút thì chỉ càn sửa nó thành 3-nút. Ví dụ X có thể được thèm vào cây trong Hĩnh 15.1 băng cách thêm nó và một liên kết khác vào nút chứa s. Tương tự một 3-nút có thể dễ dàng sửa thành 4-nút. Nhưng chúng ta sẽ làm gì để chèn một nút mới vào một 4-nút Ví dụ làm thế nào để chfen G vào cây trong Hình 15.1 Một khả năng là treo nó vào như một con mói bên phải nhất của 4-nút chứa H I và N nhưng một cách giải quyết tốt hơn được cho trong Hình 15.2 trươc tiên phàn rã 4-nút thành hai 2-nút và chuyển một trong các khóa của nó lèn cha nó 4-nút chứa H I N được tách thành hai 2-nút một chứa H một chứa N khóa giđa I được đẩy lên 3-nút chứa E và R để đổi nó thành 4-nút. Kế đến là nơi ở của G là 2-nút chứa H. 252 CÂY CẦN BẰNG Hình 15.4 Tách các 4-nút Nhưng nếu chúng ta tách một 4-nút mà cha của nó cũng là 4-nút thì sao Một phương pháp là cũng sẽ tách cha nó nhưng chúng ta có thể làm mãi điêu này cho đến gốc của cây. Một giải pháp dễ hơn là luôn bảo đảm cha của bất kỳ nút nào đêu không là 4-nút tòng cách tách hết mọi 4-nút của cây từ trên xuống. Hình 15.3 xây dựng một 2-3-4 cây cho tập hợp các khóa ASE AR c H INGEXAMPLE. Trên dòng đàu tièn chúng ta thấy nút gốc được tách trong suốt quá trình chèn vào của nút thứ hai E các trương hợp tách khác xuất hiện phần tử A thứ hai phân tử L và phân tử E thứ 3 được chèn vào Ví dụ trên cho thấy chúng ta có thể dễ dàng chèn các nút mới vào các 2-3-4 cây bằng cách thực hiện quá trình tìm kiếm và tách các 4-nút của cây từ trên xuống. Cụ thể như trong Hình 15.4 mỗi khi chúng ta gặp một 2-nút được nối với một 4-nút chúng ta sẽ chuyển đổi nó thành một 3-nút được nối với hai 2-nút và mỗi khi chúng ta chạm phải một 3-nút được nối vối một 4-nút chúng ta nên chuyển nó thành một 4-nút được nối với hai 2-nút. Thao tác tách hầy làm .
