Announcement

Collapse
No announcement yet.

Thắc mắc về cân bằng lại trên cây AVL

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

  • Thắc mắc về cân bằng lại trên cây AVL

    Chào mọi người, mình có bài tập mong được mọi người giúp đỡ.
    Thêm 1 nút trong cây AVL đòi hỏi phải cân bằng lại, mình đã làm thử bằng tay nhưng kết quả lại không ra cây AVL. Cây AVL có 4 nút: 3 6 8 9, thêm 1 nút là: 4, sau đó ta cân bằng lại. Mong mọi người góp ý, nếu ai có hướng dẫn cụ thể bằng hình (hoặc lời) thì tốt quá.
    hình0252.jpg
    P/s: Post bài nhầm box, mong MOD, AD move bài giùm. Em xin cảm ơn.
    I don't know the secret to success, but the secret to failure is trying to please everyone

  • #2
    Như bạn bên dưới:
    PHP Code:
    8
    | \
    6  9
    |
    3
    |
    4

    =>
    6
    | \
    3  8
    |  |
    4  9 
    Last edited by 11520246; 11-06-2014, 00:06.
    Thân Lãng Tử Phiêu Du Theo Ngàn Gió,
    Chốn Phiêu Hồng Buông Kiếm Tựa Hồng Nhan

    Đời Đạo Gian

    Comment


    • #3
      theo mình thì cân bằng lại như sau (sr do lười post hình )
      node gốc là 6; mức 1 có 3 và 8 (con của 6)
      mức 2 có 4 (con của 3) và 9 (con của 8)

      cái này chỉ là cân bằng left-left thôi mà bạn, cứ ghép code vào là quay được thôi
      Đừng bán rẻ mình...
      Mà phải BÁN ĐÚNG GIÁ!!!

      Comment


      • #4
        xem thử cái này thử:

        Comment


        • #5
          Originally posted by 13520747 View Post
          theo mình thì cân bằng lại như sau (sr do lười post hình )
          node gốc là 6; mức 1 có 3 và 8 (con của 6)
          mức 2 có 4 (con của 3) và 9 (con của 8)
          cái này chỉ là cân bằng left-left thôi mà bạn, cứ ghép code vào là quay được thôi
          -- Tớ làm cái này để hiểu code nên từ đầu đến giờ tớ vẫn luôn làm theo đoạn code, lúc đầu tớ cũng làm như cậu, nhưng giờ thấy có vẻ sai.
          -- Theo cái cậu nói thì 8 lúc đầu là cha của 6, sau này thì 6 là cha của 8, cái này tớ nghĩ là sai, nút 8 có con trỏ Left đến 6, nhưng 6 không có con trỏ Right trỏ đến 8, cậu dùng dấu mũi tên sẽ thấy.
          -- Tại nút 6 tớ thấy nó quay kiểu Left-Right chứ không phải Left-Left, vì lúc đầu nút 3 là EH, sau này nó cập nhật lại là RH.
          Cậu xem thử tớ nói có đúng không, mong cậu góp ý.
          I don't know the secret to success, but the secret to failure is trying to please everyone

          Comment


          • #6
            Originally posted by tara95 View Post
            -- Tớ làm cái này để hiểu code nên từ đầu đến giờ tớ vẫn luôn làm theo đoạn code, lúc đầu tớ cũng làm như cậu, nhưng giờ thấy có vẻ sai.
            -- Theo cái cậu nói thì 8 lúc đầu là cha của 6, sau này thì 6 là cha của 8, cái này tớ nghĩ là sai, nút 8 có con trỏ Left đến 6, nhưng 6 không có con trỏ Right trỏ đến 8, cậu dùng dấu mũi tên sẽ thấy.
            -- Tại nút 6 tớ thấy nó quay kiểu Left-Right chứ không phải Left-Left, vì lúc đầu nút 3 là EH, sau này nó cập nhật lại là RH.
            Cậu xem thử tớ nói có đúng không, mong cậu góp ý.
            Thứ nhất: trường hợp này là mất cân bằng left-left
            bạn để ý sẽ thấy, tại node gốc, cây mất cân bằng trái; tại cây con bên trái, cây cũng mất cân bằng trái
            với lại tái cân bằng cây AVL thì mình chỉ xét ở gốc thôi, vì bản thân cây trước khi thêm node vào thì nó đã cân bằng

            Thứ hai: Node 6 vẫn có con trỏ right, chỉ là bằng NULL thôi, tức là ta có thể gán Node 6->right = Node 8 được
            và trong đoạn code có 1 dòng là
            Code:
            T->left = T1->right
            với T là Node gốc, T1 = T->left, cụ thể thì T là 8, còn T1 là 6
            dòng này nếu áp dụng vào bài của bạn thì có nghĩa là cắt liên kết left của Node 8 (gán = NULL)
            Đừng bán rẻ mình...
            Mà phải BÁN ĐÚNG GIÁ!!!

            Comment


            • #7
              Sau khi thêm xong, nếu chiều cao của cây thay đổi, từ vị trí thêm vào, ta phải lần ngược lên gốc để kiểm tra xem có nút nào bị mất cân bằng hay không. Cái cậu đang kiểm tra là ở nút gốc. Ở đây thêm vào nút 4, sau khi thêm xong, mình phải lần ngược từ dưới lên, nút 4 và 3 không mất cân bằng, và mất cân bằng tại nút 6, ta phải cân bằng lại ở nút 6 (đóng vai trò là nút gốc trong khi cân bằng lại). Cái cậu cân bằng là ở ngay tại nút gốc luôn rồi, sau khi kiểm tra 6 xong mới xem có cần thiết phải cân bằng lại nút gốc hay không?
              P/s: Không biết hiểu ý cậu hay không?
              I don't know the secret to success, but the secret to failure is trying to please everyone

              Comment


              • #8
                6
                | \
                4 8
                | |
                3 9

                Comment


                • #9
                  #tara95: Cảm ơn bạn. Mình vừa xem lại lý thuyết và đúng là mình đã nhầm lẫn ở chỗ này.
                  Vậy có nghĩa là bạn đã cân bằng được Mình ghi ra xem có đúng không nhé ^^

                  Code:
                           8
                        /    \
                      4       9
                     / \
                   3    6
                  Đừng bán rẻ mình...
                  Mà phải BÁN ĐÚNG GIÁ!!!

                  Comment


                  • #10
                    Originally posted by 13520747 View Post
                    #tara95: Cảm ơn bạn. Mình vừa xem lại lý thuyết và đúng là mình đã nhầm lẫn ở chỗ này.
                    Vậy có nghĩa là bạn đã cân bằng được Mình ghi ra xem có đúng không nhé ^^

                    Code:
                             8
                          /    \
                        4       9
                       / \
                     3    6
                    Tớ vẫn chưa nhìn ra được.
                    Tớ nói, cậu thấy sai thì bảo tớ với: Cân bằng tại nút 6, nút con bao gồm 3 (lúc đầu là EH, hiện tại là RH), nút 4 (EH), lệch về bên trái nên cân bằng lại theo bên trái. Tiếp theo vào hàm cân bằng, 6 là T, 3 là T1, T1 là RH nên xoay Left-Right. Vào hàm xoay Left-Right thì 6 là T, 3 là T1 và 4 là T2. Làm 1 tí thì ra hình zíc zắc.
                    :cry:
                    I don't know the secret to success, but the secret to failure is trying to please everyone

                    Comment


                    • #11
                      bạn xác định T, T1 và T2 đúng rồi
                      cơ mà mình không hiểu lắm câu này của bạn
                      lệch về bên trái nên cân bằng lại theo bên trái
                      bạn đã xác định được chỗ node 6 này lệch theo trường hợp left-right nên cứ áp dụng code vào thôi

                      gửi bạn hàm cân bằng cho trường hợp left-right của thầy Ngô Quốc Hưng
                      Code:
                      void rotateLR(AVLTree &T)
                      { 
                                  AVLNode * T1 = T-> pLeft ; 
                                  AVLNode * T2 = T1-> pRight ; 
                                  T-> pLeft      = T2-> pRight ; 
                                  T2-> pRight = T; 
                                  T1-> pRight = T2-> pLeft ; 
                                  T2-> pLeft     = T1; 
                                  switch (T2-> balFactor ) 
                                  { 
                                               case LH: T-> balFactor = RH; 
                                                            T1-> balFactor = EH; 
                                                            break ; 
                                               case EH: T-> balFactor = EH; 
                                                            T1-> balFactor = EH; 
                                                            break ; 
                                               case RH: T-> balFactor = EH; 
                                                            T1-> balFactor = LH; 
                                                            break ; 
                                  } 
                       
                                  T2-> balFactor = EH; 
                                  T = T2; 
                      }
                      Đừng bán rẻ mình...
                      Mà phải BÁN ĐÚNG GIÁ!!!

                      Comment


                      • #12
                        Originally posted by 13520747 View Post
                        bạn xác định T, T1 và T2 đúng rồi
                        cơ mà mình không hiểu lắm câu này của bạn

                        bạn đã xác định được chỗ node 6 này lệch theo trường hợp left-right nên cứ áp dụng code vào thôi

                        gửi bạn hàm cân bằng cho trường hợp left-right của thầy Ngô Quốc Hưng
                        Cảm ơn cậu rất nhiều, mình đoảng quá.
                        Ngay từ đầu tớ làm không sai, code cũng không sai, chỉ quên chạy mất dòng cuối đoạn code cậu nêu
                        I don't know the secret to success, but the secret to failure is trying to please everyone

                        Comment


                        • #13
                          Code:
                                   8
                                /    \
                              4       9
                             / \
                           3    6
                          Đáp án cuối cùng là đây.
                          I don't know the secret to success, but the secret to failure is trying to please everyone

                          Comment

                          LHQC

                          Collapse
                          Working...
                          X