Announcement

Collapse
No announcement yet.

Sort trong cây nhị phân

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • [C++] Sort trong cây nhị phân

    Có 1 cây nhị phân vs phần data là tổ hợp 1 số thuộc tính .v.v và việc xây dựng cây chỉ dựa trên 1 thuộc tính A nào đó thì bây h nếu có yêu cầu in ra 1 cách thứ tự của 1 thuộc tính B khác A của tree này thì có thuật toán hay giải pháp nào làm cho quá trình sort này nhanh hơn là sẽ duỗi thẳng cây ra thành dạng dãy hay list để sort rùi show kq?
    vd: 1 cây vs data: mssv (ko trùng nhau) / điểm / tên /....blah vs việc xây dựng lấy mssv .thì sort theo điểm in ra full 1 sv thì làm sao cho lợi ?

  • #2
    theo tui nghĩ thì ko thể.
    vì cây nhị phân sắp xếp theo MSSV rồi thì thuộc tính điểm nó tùm lum ngẫu nhiên trong cây rồi, ko biến cây thành ds để sắp xếp sao được.
    Tui có ý tưởng là, duyệt cây sắp xếp theo MSSV, lấy giá trị điểm của từng cái tạo thành 1 cây mới sắp xếp theo điểm. Tại 1 nút điểm có 2 người trùng điểm thì tại đó tạo thành 1 dslk chứa những người trùng điểm. Hoặc tạo 1 cây sắp xếp theo MSSV hoặc thuộc tính khác tại nút đó
    3422A Trịnh Quang Nghị, F7, Q8
    0938952106 - 0963952106
    Page bán phụ kiện điện thoại, pc giá rẻ

    Comment


    • #3
      nói vậy thì cũng phải tốn thêm bộ nhớ thôi.duỗi thẳng em nó ra nghĩa là dựng thằng khác rồi chép qua thôi.làm như ông anh thì có vẻ phù du rắc rối hơn

      Comment


      • #4
        Duỗi thẳng cây ra là chuyện dĩ nhiên phải làm. Còn việc sort lại thì phải chọn thuật toán có khả năng sắp xếp ngay khi duỗi chứ không phải duỗi hết rồi mới sắp, những thuật toán như vậy gọi chung là online algorithm, insertion sort và merge sort là những ví dụ tốt.

        Comment


        • #5
          Originally posted by truonganpn View Post
          Duỗi thẳng cây ra là chuyện dĩ nhiên phải làm. Còn việc sort lại thì phải chọn thuật toán có khả năng sắp xếp ngay khi duỗi chứ không phải duỗi hết rồi mới sắp, những thuật toán như vậy gọi chung là online algorithm, insertion sort và merge sort là những ví dụ tốt.
          thế ko duỗi ko được hả thầy.vậy thì tốn kém loài

          Comment


          • #6
            Originally posted by 13520797 View Post
            thế ko duỗi ko được hả thầy.vậy thì tốn kém loài
            Ko hẳn gọi là duỗi...cứ duyệt cây như bình thường....rồi với từng nút duyệt được thì thực hiện chèn vào mảng rồi sort trực tiếp bằng insertion hoặc merge sort. Như thế khi vừa duyệt hết cây thì mảng kết quả cũng đã sort xong.
            Tiết kiệm hơn so với duỗi ra mảng rồi sort mảng đó

            Comment


            • #7
              Originally posted by 13520797 View Post
              nói vậy thì cũng phải tốn thêm bộ nhớ thôi.duỗi thẳng em nó ra nghĩa là dựng thằng khác rồi chép qua thôi.làm như ông anh thì có vẻ phù du rắc rối hơn
              sao lại rắc rối, nếu tạo 1 cây mới thì giá trị điểm trùng nhau thì s sắp xếp lên cây nhị phân?
              không thì cứ sort theo a ở trên
              Last edited by 13520336; 09-06-2014, 08:22.
              3422A Trịnh Quang Nghị, F7, Q8
              0938952106 - 0963952106
              Page bán phụ kiện điện thoại, pc giá rẻ

              Comment


              • #8
                Originally posted by 09520200 View Post
                Ko hẳn gọi là duỗi...cứ duyệt cây như bình thường....rồi với từng nút duyệt được thì thực hiện chèn vào mảng rồi sort trực tiếp bằng insertion hoặc merge sort. Như thế khi vừa duyệt hết cây thì mảng kết quả cũng đã sort xong.
                Tiết kiệm hơn so với duỗi ra mảng rồi sort mảng đó
                Quá chuẩn ông anh! Rõ ràng duỗi ra rồi sắp xếp là trường hợp xấu nhất!

                Comment

                LHQC

                Collapse
                Working...
                X