Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 12 kết quả

Đề tài: mình cần tối ưu thuật toán về dạng O(log n). Ai có thể giúp mình vs

  1. #1
    Ngày gia nhập
    11 2016
    Bài viết
    14

    Mặc định mình cần tối ưu thuật toán về dạng O(log n). Ai có thể giúp mình vs

    #include <iostream>
    #include <vector>
    #include <cstdlib>


    using namespace std;

    // An AVL tree node // tao cay avl
    struct Node
    {
    int key;
    struct Node *left;
    struct Node *right;
    int height; // do cao cua cay
    };

    // A utility function to get maximum of two integers
    int max(int a, int b);

    int max(int a, int b)
    {
    return (a > b) ? a : b;
    }
    // A utility function to get height of the tree
    int height(Node *N)
    {
    if (N == 0)
    return 0;
    return N->height;
    }

    // A utility function to get maximum of two integers


    // creat new node // tao nut moi
    Node* newNode(int key)
    {
    Node* node = new Node;
    node->key = key;
    node->left = 0;
    node->right = 0;
    node->height = 1; // new node is initially added at leaf
    return(node);
    }



    Node *rightRotate(Node *y)
    {
    Node *x = y->left;
    Node *T2 = x->right;

    // Perform rotation // quay
    x->right = y;
    y->left = T2;

    // Update heights // ghi nho chieu cao
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    // Return new root
    return x;
    }

    Node *leftRotate(Node *x)
    {
    Node *y = x->right;
    Node *T2 = y->left;

    // Perform rotation
    y->left = x;
    x->right = T2;

    // Update heights
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    // Return new root
    return y;
    }

    // Get Balance factor of node N // tinh balance
    int getBalance(Node *N)
    {
    if (N == 0)
    return 0;
    return height(N->left) - height(N->right);
    }


    Node* insert(Node* node, int key)
    {
    // like binary search tree common // giong nhu trong cay nhi phan thong thuong
    if (node == 0)
    return(newNode(key));

    //Проходим по пути поиска, пока не убедимся, что ключа в дереве нет.
    if (key < node->key)
    node->left = insert(node->left, key);
    else if (key > node->key)
    node->right = insert(node->right, key);
    else
    return node;

    // Update height of this ancestor node // ghi nho chieu cao
    /*"Отступаем" назад от добавленной вершины к корню. Проверяем в
    каждой вершине сбалансированность. Если разность высот поддеревьев
    равна 2 – выполняем нужное вращение.
    */
    node->height = 1 + max(height(node->left),
    height(node->right));

    // get balance
    int balance = getBalance(node);

    // if balance >= 2 || <= -2 use necessary command // neu balance >= 2, <= -2 su dung lenh phu hop
    if (balance > 1 && key < node->left->key)
    return rightRotate(node);

    if (balance < -1 && key > node->right->key)
    return leftRotate(node);

    if (balance > 1 && key > node->left->key)
    {
    node->left = leftRotate(node->left);
    return rightRotate(node);
    }

    if (balance < -1 && key < node->right->key)
    {
    node->right = rightRotate(node->right);
    return leftRotate(node);
    }

    return node;
    }

    // find minimum

    Node * minValueNode(Node* node)
    {
    Node* current = node;
    while (current->left != 0)
    current = current->left;

    return current;
    }

    // delete node with key
    Node* deleteNode(Node* root, int key)
    {

    // like binary search tree common // giong nhu trong cay nhi phan thong thuong
    // Ищем вершину D, которую требуется удалить.
    if (root == 0)
    return root;

    if (key < root->key)
    root->left = deleteNode(root->left, key);

    else if (key > root->key)
    root->right = deleteNode(root->right, key);

    else
    {
    // node with only one child or no child
    //Если D – лист или D имеет одно поддерево, то удаляем D
    if ((root->left == 0) || (root->right == 0))
    {
    struct Node *temp = root->left ? root->left :
    root->right;

    // No child case
    if (temp == 0)
    {
    temp = root;
    root = 0;
    }
    else // One child case
    *root = *temp; // Copy the contents of the non-empty child
    free(temp);
    }
    else
    {
    /*Если D имеет два поддерева, то ищем вершину M, следующую по
    значению после D. Как в стандартном алгоритме удаления из
    дерева поиска. Переносим значение из M в D. Удаляем M.*/

    Node* temp = minValueNode(root->right);

    // Copy the inorder successor's data to this node
    root->key = temp->key;

    // Delete the inorder successor
    root->right = deleteNode(root->right, temp->key);
    }
    }

    // If the tree had only one node then return
    if (root == 0)
    return root;

    // find height
    root->height = 1 + max(height(root->left),
    height(root->right));

    //find balance
    int balance = getBalance(root);

    // if balance >= 2 || <= -2 use necessary command // neu balance >= 2, <= -2 su dung lenh phu hop

    if (balance > 1 && getBalance(root->left) >= 0)
    return rightRotate(root);

    if (balance > 1 && getBalance(root->left) < 0)
    {
    root->left = leftRotate(root->left);
    return rightRotate(root);
    }

    if (balance < -1 && getBalance(root->right) <= 0)
    return leftRotate(root);

    if (balance < -1 && getBalance(root->right) > 0)
    {
    root->right = rightRotate(root->right);
    return leftRotate(root);
    }

    return root;
    }




    int k(0);
    int m(0);
    void RNL(Node* node, int key)
    {
    if (node != 0)
    {
    RNL(node->right, key);
    if (key == node->key)
    {
    cout << k << " ";
    return;
    }
    k++;
    RNL(node->left, key);
    }
    }

    //find node->key, node in key-th
    void RNL1(Node* node, int key)
    {
    if (node != 0)
    {
    if (m != 0)
    return;
    RNL1(node->right, key);
    if (k == key)
    {
    m = node->key;
    }
    k++;

    cout << "so k = " << k << endl;
    RNL1(node->left, key);
    }
    }

    void RNL0(Node* node)
    {
    if (node != 0)
    {
    RNL0(node->right);
    cout << node->key << " ";
    RNL0(node->left);
    }
    }


    int main()
    {
    Node *root = 0;
    int N(0);
    cin >> N;
    int command(0);
    int key(0);

    for (int i = 0; i < N; i++)
    {
    cin >> command >> key;
    switch (command)
    {
    case 1:
    root = insert(root, key);
    RNL(root, key);
    cout << endl;
    RNL0(root);
    cout << endl;
    k = 0;
    break;
    case 2:
    RNL1(root, key);
    cout << endl << m << endl;
    root = deleteNode(root, m);
    RNL0(root);
    k = 0;
    m = 0;
    break;
    default:
    break;
    }
    }

    system("pause");
    return 0;
    }
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

  2. #2
    Ngày gia nhập
    01 2013
    Nơi ở
    Học viện Kỹ thuật Quân Sự
    Bài viết
    247

    Cây AVL là cậy nhị phân + Nó tự cân bằng.
    Việc tìm kiếm trên AVL chỉ mất O(lg n) ??
    Tôi vẫn chưa hỏi câu hỏi của bạn !
    Nếu cần giúp đỡ, hỗ trợ:
    Bài Tập. Đồ Án. Tools. Phần mềm. Liên hệ:
    Facebook: http://www.facebook.com/thuecodedoan
    Website: https://thuecodedoan.wordpress.com
    Email: thuecodedoan@gmail.com
    Sđt: 094.76.76.854

  3. #3
    Ngày gia nhập
    11 2016
    Bài viết
    9

    Của bọn nga ngố viết.

  4. #4
    Ngày gia nhập
    11 2016
    Bài viết
    14

    Vấn đề là không chỉ tìm kiêm mà còn thêm và xóa nữa nên độ phức tạp lớn hơn

    - - - Nội dung đã được cập nhật ngày 29-11-2016 lúc 10:44 PM - - -

    Mình đang học ở nga nên có chữ tiếng nga thôi )

  5. #5
    Ngày gia nhập
    11 2016
    Bài viết
    9

    Bạn đang học trường nào vậy? @nguyenhanh

    - - - Nội dung đã được cập nhật ngày 30-11-2016 lúc 02:15 AM - - -

    mình cũng đang du học nga ngố nè.

  6. #6
    Ngày gia nhập
    11 2016
    Bài viết
    14

    Mặc định mình cần tối ưu thuật toán về dạng O(log n). Ai có thể giúp mình vs

    mình học trường vật lý kỹ thuật . thế còn c

    - - - Nội dung đã được cập nhật ngày 30-11-2016 lúc 12:19 AM - - -

    Vấn đề là không chỉ tìm kiêm mà còn thêm và xóa nữa nên độ phức tạp lớn hơn. t cũng từng ở học viện 1 năm )))

  7. #7
    Ngày gia nhập
    11 2016
    Bài viết
    9

    Bauman.:V
    Quá kinh khủng, muốn thắt cổ.
    Học viện kĩ thuật mật mã hay quân sự?
    T đang học tại trường ITMO.
    Biết tourist 2014 k?.

  8. #8
    Ngày gia nhập
    11 2016
    Bài viết
    14

    chị học vật lý kỹ thuật moscow. ITMO ở Xanh nhỉ(chị 95)
    c mới vào nhóm chưa biết ai hết)

  9. #9
    Ngày gia nhập
    11 2016
    Bài viết
    9

    đúng rồi c.hihi
    youtube phát.
    Đã được chỉnh sửa lần cuối bởi star97 : 30-11-2016 lúc 05:40 AM.

  10. #10
    Ngày gia nhập
    11 2016
    Bài viết
    14

    cho c xin nickfacebook.trao đổi bài cho dễ)))
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

Tags của đề tài này

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn