Đạ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]

    1 [Kinh nghiệm]Cây nhị phân tìm kiếm on Mon Jun 27, 2011 9:21 pm

    HaiYen


    Thành viên cao cấp
    Thành viên cao cấp
    Cây Nhị Phân Tìm Kiếm



    1. CÂY NHỊ PHÂN TÌM KIẾM

    Cây nhị phân tìm kiếm (CNPTK) là cây nhị phân trong đó tại mỗi nút, khóa của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khóa của tất cả các nút thuộc cây con phải.

    Spoiler:


    Dưới đây là một ví dụ về cây nhị phân tìm kiếm:
    [You must be registered and logged in to see this image.]


    Nhờ ràng buộc về khóa trên CNPTK, việc tìm kiếm trở nên có định hướng. Hơn nữa, do cấu trúc cây việc tìm kiếm trở nên nhanh đáng kể. Nếu số nút trên cây là N thì chi phí tìm kiếm trung bình chỉ khoảng log2N.
    Trong thực tế, khi xét đến cây nhị phân chủ yếu người ta xét CNPTK.

    2. CÁC THAO TÁC TRÊN CÂY NHỊ PHÂN TÌM KIẾM
    2.1. Duyệt cây

    Thao tác duyệt cây trên cây nhị phân tìm kiếm hoàn toàn giống như trên cây nhị phân. Chỉ có một lưu ý nhỏ là khi duyệt theo thứ tự giữa, trình tự các nút duyệt qua sẽ cho ta một dãy các nút theo thứ tự tăng dần của khóa.

    2.2. Tìm một phần tử x trong cây
    Spoiler:
    LPNODE searchNode(TREE T, Data X)
    {
    if ( T != NULL )
    {
    if(T->Key == X)
    return T;
    else if(T->Key > X)
    return searchNode(T->pLeft, X);
    else
    return searchNode(T->pRight, X);
    }

    return NULL;
    }

    //Ta có thể xây dựng một hàm tìm kiếm tương đương không đệ qui như sau:
    Spoiler:
    LPTNODE searchNode(TREE Root, Data x)
    {
    LPNODE p = Root;
    while (p != NULL)
    {
    if(x == p->Key)
    return p;
    else if(x < p->Key)
    p = p->pLeft;
    else //if(x > p->Key)
    p = p->pRight;
    }
    return NULL;
    }


    Dễ dàng thấy rằng số lần so sánh tối đa phải thực hiện để tìm phần tử X là h, với h là chiều cao của cây. Như vậy thao tác tìm kiếm trên CNPTK có n nút tốn chi phí trung bình khoảng O(log2n) .

    Ví dụ: Tìm phần tử 55
    [You must be registered and logged in to see this image.]


    2.3. Thêm một phần tử x vào cây
    Việc thêm một phần tử X vào cây phải bảo đảm điều kiện ràng buộc của CNPTK. Ta có thể thêm vào nhiều chỗ khác nhau trên cây, nhưng nếu thêm vào một nút lá sẽ là tiện lợi nhất do ta có thể thực hiên quá trình tương tự thao tác tìm kiếm. Khi chấm dứt quá trình tìm kiếm cũng chính là lúc tìm được chỗ cần thêm.
    Hàm insert trả về giá trị –1, 0, 1 khi không đủ bộ nhớ, gặp nút cũ hay thành công:
    Spoiler:
    int insertNode(TREE &T, Data X)
    {
    if ( T != NULL )
    {
    if (T->Key == X)
    return 0; //đã có
    else if (T->Key > X)
    return insertNode(T->pLeft, X);
    else
    return insertNode(T->pRight, X);
    }

    T = new TNode;
    if (T == NULL)
    return -1; //thiếu bộ nhớ
    T->Key = X;
    T->pLeft = NULL;
    T->pRight = NULL;

    return 1; //thêm vào thành công
    }


    Ví dụ: Thêm phần tử 50
    [You must be registered and logged in to see this image.]


    2.4. Hủy một phần tử có khóa X

    Việc hủy một phần tử X ra khỏi cây phải bảo đảm điều kiện ràng buộc của CNPTK.
    Có 3 trường hợp khi hủy nút X có thể xảy ra:

    [You must be registered and logged in to see this image.]X là nút lá.
    [You must be registered and logged in to see this image.]X chỉ có 1 con (trái hoặc phải).
    [You must be registered and logged in to see this image.]X có đủ cả 2 con

    [You must be registered and logged in to see this image.]Trường hợp thứ nhất: chỉ đơn giản hủy X vì nó không móc nối đến phần tử nào khác.
    [You must be registered and logged in to see this image.]
    [You must be registered and logged in to see this image.]Trường hợp thứ hai: trước khi hủy X ta móc nối cha của X với con duy nhất của nó.
    [You must be registered and logged in to see this image.]


    [You must be registered and logged in to see this image.]Trường hợp cuối cùng: ta không thể hủy trực tiếp do X có đủ 2 con Þ Ta sẽ hủy gián tiếp. Thay vì hủy X, ta sẽ tìm một phần tử thế mạng Y. Phần tử này có tối đa một con. Thông tin lưu tại Y sẽ được chuyển lên lưu tại X. Sau đó, nút bị hủy thật sự sẽ là Y giống như 2 trường hợp đầu.
    Vấn đề là phải chọn Y sao cho khi lưu Y vào vị trí của X, cây vẫn là CNPTK.

    Có 2 phần tử thỏa mãn yêu cầu:
    + Phần tử nhỏ nhất (trái nhất) trên cây con phải.
    + Phần tử lớn nhất (phải nhất) trên cây con trái.

    Việc chọn lựa phần tử nào là phần tử thế mạng hoàn toàn phụ thuộc vào ý thích của người lập trình. Ở đây, cháng tôi sẽ chọn phần tử (phải nhất trên cây con trái làm phân tử thế mạng.

    Hãy xem ví dụ dưới đây để hiểu rõ hơn:
    [You must be registered and logged in to see this image.]
    Sau khi hủy phần tử X=18 ra khỏi cây tình trạng của cây sẽ như trong hình (phần tử 23 là phần tử thế mạng)


    Hàm deleteNode trả về giá trị 1, 0 khi hủy thành công hoặc không có X trong cây:
    Spoiler:
    int deleteNode(TREE &T, Data X)
    {
    if (T == NULL)
    return 0;
    else if (T->Key > X)
    return deleteNode (T->pLeft, X);
    else if(T->Key < X)
    return deleteNode (T->pRight, X);
    else //T->Key == X
    {
    LPNODE p = T;
    if (T->pLeft == NULL)
    T = T->pRight;
    else if (T->pRight == NULL)
    T = T->pLeft;
    else //T có cả 2 con
    {
    LPNODE q = T->pRight;
    searchStandFor(p, q);
    }
    delete p;
    }
    }

    Trong đó, hàm searchStandFor được viết như sau:
    //Tìm phần tử thế mạng cho nút p
    Spoiler:
    void searchStandFor(TREE &p, TREE &q)
    {
    if (q->pLeft)
    searchStandFor(p, q->pLeft);
    else
    {
    p->Key = q->Key;
    p = q;
    q = q->pRight;
    }
    }

    2.5. Tạo một cây CNPTK
    Ta có thể tạo một cây nhị phân tìm kiếm bằng cách lặp lại quá trình thêm 1 phần tử vào một cây rỗng.


    2.6. Hủy toàn bộ CNPTK
    Việc toàn bộ cây có thể được thực hiện thông qua thao tác duyệt cây theo thứ tự sau. Nghĩa là ta sẽ hủy cây con trái, cây con phải rồi mới hủy nút gốc.
    Spoiler:
    void removeTree(TREE &T)
    {
    if ( T != NULL )
    {
    removeTree(T->pLeft);
    removeTree(T->pRight);
    delete T;
    }
    }


    3. ĐÁNH GIÁ
    Tất cả các thao tác searchNode, insertNode, deleteNode trên CNPTK đều có độ phức tạp trung bình O(h), với h là chiều cao của cây. Trong trong trường hợp tốt nhất, CNPTK có n nút sẽ có độ cao h = log2(n). Chi phí tìm kiếm khi đó sẽ tương đương tìm kiếm nhị phân trên mảng có thứ tự. Tuy nhiên, trong trường hợp xấu nhất, cây có thể bị suy biến thành 1 DSLK (khi mà mỗi nút đều chỉ có 1 con trừ nút lá). Lúc đó các thao tác trên sẽ có độ phức tạp O(n). Vì vậy cần có cải tiến cấu trúc của CNPTK để đạt được chi phí cho các thao tác là log2(n).


    ================
    Nhà em cách 4 quả đồi
    Cách 3 con suối, cách đôi cánh rừng
    Nhà em xa cách quá chừng
    Em van anh đấy, anh đừng yêu em!...

    FaceBook của em

    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 http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | Sosblogs