Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    moclan1209

    moclan1209
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Em đang làm môn CTDL nâng cao. Em chưa hiểu phần xoá trong cây đỏ đen và cây 2-3-4. Ở cây đỏ đen, em chưa hiểu phần khi xoá thì ra V+. Các anh, các chị, các bạn đã hiểu rõ phần này rồi có thể giải thích rõ cho em và các bạn hiểu hơn. Em cám ơn rất nhiều.

    HaiYen

    HaiYen
    Thành viên cao cấp
    Thành viên cao cấp
    Thực ra đưa ra V+ cho người ta dễ hiểu hơn thôi, nhưng nếu chị cảm thấy khó hiểu hơn thì quả là... phản tác dụng.
    Theo em hiểu vấn đề là như thế này, nó liên quan đến một tính chất của cây đỏ đen là "Độ cao đen của 1 nút tới mọi nút lá qua nó luôn bằng nhau". Nghĩa là gì? Nghĩa là nếu xét 1 nút x thì tính từ nút x xuống tới 1 nút lá bất kỳ (bên dưới nó) phải có số nút đen bằng nhau. Điều này có nghĩa là khi chị xoá bỏ 1 nút đen, chị phải đảm bảo tính chất đó vẫn còn đối với kết quả còn lại.

    Để dễ hiểu, bây giờ lại xét một nút X đen nhé. Ta sẽ chưa quan tâm đến cha con gì cho nó rối. Chị có thấy là tại nút đó, nó đang là đỉnh của 2 nhánh con của nó không? Đương nhiên, nếu chị xoá nó, xoá cái nút X ý, thì phải kéo 1 nút con lên thay thế. Nếu nút con là nút đỏ, thì cả 2 nhánh con của X đều mất đi 1 đơn vị đen trong chiều cao đen qua nút X đúng không? Điều đó có nghĩa là chỉ việc đổi nút thay thế (đỏ) thành nút đen là được nó sẽ bù đủ nút đen cho cả 2 nhánh, vì nó ở vị trí giao mà.

    Bây giờ ta lại xét, nếu như nút thay thế nó đã đen rồi -- > Nghĩa là còn thiếu 1 đơn vị đen nữa mới đủ độ cao đen của nhánh qua nút X → Bắt buộc phải đổi màu nút màu đỏ ở bên trên nút X (Chị thừa biết, nếu đổi màu nhánh con của nút X thì chị phải đổi màu 2 nhánh đúng không, chẳng đứa nào dở hơi mà đổi màu 2 nhánh vì nếu ở nhánh kế nó vẫn đen chị phải đi xuống dưới thì không những đổi màu cả 4 nhánh con... đấy là em ví dụ là nút cần đổi nó ở gần... Nếu như nó ở tít tận đáy... thậm chí chị phải đổi màu đến 2n nhánh... như vậy có dở hơi không, cho nên người ta phải chọn lên phía trên để đổi màu, nhé.) Thế nên đổi màu nút cha để đủ đen thì ta lại bị ảnh hưởng của nhánh qua nút anh em của X sẽ bị thay đổi số lượng độ cao đen, -→ cần đổi màu. Nếu đổi màu nút ông, tức là ta lại phải đổi lại màu cho nút chú vì độ cao đen qua nút ông thay đổi thì ảnh hưởng tốt đến nhánh qua nút X thì cũng ảnh hưởng nhánh qua nút chú của X.
    Còn việc xoá và cân bằng lại nút đen là người ta đã tính toán rồi. Nếu chị không nhớ, chị cứ suy ngược lên trên sẽ tự biết là nút nào phải đổi màu thôi.

    moclan1209

    moclan1209
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Cám ơn Hải Yến nhé. Bây giờ chị đã hiểu thấu đáo về cách xoá trong cây đỏ đen. ~)

    HaiYen

    HaiYen
    Thành viên cao cấp
    Thành viên cao cấp
    Việc xoá trên cây 2 - 3 - 4 là trường hợp đặc biệt của B Tree, vì như mọi người đã biết là tất cả các nút lá của cây dạng này là ở cùng 1 mức. Nhưng có 1 tính chất nữa rất quan trọng có tính bắt buộc mà các tài liệu kể cả của thầy chỉ nói sơ sơ gọi là tính chất sl, đó là với 1 nút có n khoá, thì số nhánh bắt buộc phải là n + 1 (Đây là em nói chung đối với Btree, trường hợp cây 2-3-4 là trường hợp con thôi). Nên trên đường đi từ gốc xuống lá để xoá cứ gặp nút nào là nút đơn thì gộp nó lại, để làm gì nhỉ? A, để cho đỡ phải quay lại nữa. Nếu không gộp lại, mà xoá thì anh chị sẽ vi phạm tính chất sl đã nói ở trên, và sẽ lại phải quay lại để gộp (Cứ thử khắc biết), như vậy thời gian sẽ lâu hơn. Đã gộp rồi thì xoá vô tư. Vì trong 1 nút có nhiều khoá, giết 1 thằng thì nút đó vẫn tồn tại. Còn nếu để nó chỉ có 1 khoá thì khi giết khoá đó, nút đó sẽ mất → nhánh đó sẽ mất → vi phạm tính chất sl lạ phải cân bằng lại tốn nhiều thời gian hơn. Thế thôi, cho dù không sai nhưng thầy bảo mình không biết lường trước mọi sự vụ → Thế đấy.

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of https://khmt.123.st

    Free forum | ©phpBB | Free forum support | Báo cáo lạm dụng | Thảo luận mới nhất