Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: Code red black tree trong c++ chạy không đúng?

  1. #1
    Ngày gia nhập
    03 2011
    Bài viết
    2

    Mặc định Code red black tree trong c++ chạy không đúng?

    Mình có viết 1 bài cài đặt cây đỏ đen như thế này.
    Code:
    #include <cstdio>
    #include <algorithm>
    #include <string>
    enum rbt_color { RED, BLACK };
    struct rbt_node
    {
        int key;//khoa
        //int sub_tree;
        rbt_node *left;
        rbt_node *right;
        rbt_node *parent;
        rbt_color color;
    };
    //ktra do
    int is_RED(rbt_node *root)
    {
        return root != NULL && root->color == RED;
    }
    //ktra den
    int is_BLACK(rbt_node *root)
    {
        return root != NULL && root->color == BLACK;
    }
    //tao 1 node voi cac gia tri ban dau
    rbt_node *make_node(int key)
    {
        rbt_node *new_node = new rbt_node; 
        new_node->key = key;
        new_node->color = RED;
        new_node->left = NULL;
        new_node->right = NULL;
        //new_node->sub_tree = 1;
        return new_node;
    }
    // them 1 node moi nhung chua ktra mau
    //tree-luu cay, node-luu node can them, parent-node cha
    void add_node(rbt_node *&root, rbt_node *node, rbt_node *parent)
    {
            if(root == NULL)
            {
                node->parent = parent;
                root = node;
            }
            else if(node->key < root->key)
            {
                //root->sub_tree += 1;
                add_node(root->left, node, root);
            }
            else if(node->key > root->key)
            {
                //root->sub_tree += 1;
                add_node(root->right, node, root);
            }
    }
    //quay trai
    void left_rotate(rbt_node *&root, rbt_node *&node)
    {
        rbt_node *new_node = node->right;
        if(new_node != NULL)
        {
            node->right = new_node->left;
            if(new_node->left != NULL)
                new_node->left->parent = node;
            if(node->parent == NULL)
                root = new_node;
            else if(node == node->parent->left)
                node->parent->left = new_node;
            else
                node->parent->right = new_node;
    
            new_node->left = node;
            new_node->parent = node->parent;
            new_node->left->parent = new_node;
        }
    }
    //quay phai
    void right_rotate(rbt_node *&root, rbt_node *&node)
    {
    
        rbt_node *new_node = node->left;
        if(new_node != NULL)
        {
            node->left = new_node->right;
            if(new_node->right != NULL)
                new_node->right->parent = node;
            if(node->parent == NULL)
                root = new_node;
            else if(node == node->parent->right)
                node->parent->right = new_node;
            else
                node->parent->left = new_node;
    
            new_node->right = node;
            new_node->parent = node->parent;
            new_node->right->parent = new_node;
        }
    }
    //them node va chinh mau
    void add_rbt_node(rbt_node *&root, int key, rbt_node *parent)
    {
        rbt_node *n = make_node(key);
        add_node(root, n, parent);
        while(n != root && n->parent->color == RED)//ko phai goc va cha la RED
        {
            if(n->parent == n->parent->parent->left)
            {
                rbt_node *uncle = n->parent->parent->right;//node chu
                if(uncle != NULL && uncle->color == RED)//ktra chu, neu la RED -> TH3
                {
                    n->parent->color == BLACK;
                    uncle->color = BLACK;
                    n->parent->parent->color = RED;
                    n = n->parent->parent;
                }
                else//TH4
                {
                    if(n == n->parent->right)
                    {
                        n = n->parent;
                        left_rotate(root, n);
                    }
                    n->parent->color = BLACK;
                    n->parent->parent->color = RED;
                    right_rotate(root, n->parent->parent);
                }
            }
            else
            {
                rbt_node *uncle = n->parent->parent->left;
                if(uncle != NULL && uncle->color == RED)//ktra chu, neu la RED -> TH3
                {
                    n->parent->color = BLACK;
                    uncle->color = BLACK;
                    n->parent->parent->color = RED;
                    n = n->parent->parent;
                }
                else//TH4
                {
                    if(n == n->parent->left)
                    {
                        n = n->parent;
                        right_rotate(root, n);
                    }
                    n->parent->color = BLACK;
                    n->parent->parent->color = RED;
                    left_rotate(root, n->parent->parent);
                }
            }
        }
        root->color = BLACK;//cho node goc BLACK tranh bi thay doi thanh RED trong qua trinh Fix
    }
    //tim kiem
    rbt_node *search_key(rbt_node *root, int key)
    {
        if(root == NULL)//cho con trong
            return NULL;//ko tim thay
        else if(root->key == key)//da co key do
            return root;//tim thay
        else if(root->key < key)
            search_key(root->right, key);
        else if(root->key > key)
            search_key(root->left, key);
    }
    // node anh em
    rbt_node *sibling(rbt_node *n) 
    {
         if (n == n->parent->left)
             return n->parent->right;
         else
             return n->parent->left;
    }
    // kiem tra node co phai node la ko
    bool is_leaf(rbt_node *n)
    {
         if(n->left == NULL && n->right == NULL)
                    return true;
         return false;
    }
    //du node con vao node can xoa
    void replace_node(rbt_node *&n, rbt_node *&child)
    {
         child->parent = n->parent;
    }
    // duyet cay
    void print_out(rbt_node *root)
    {
        if(root != NULL)
        {
            print_out(root->left);
            
            printf("key:%d\t", root->key);
            if(root->color == BLACK)
                printf("color:black\t");
            else
                printf("color:red\t");
            if(root->parent != NULL)
                printf("parent:%d\t",root->parent->key);
            else
                printf("parent:-\t");
            if(root->left != NULL)
                printf("left:%d\t",root->left->key);
            else
                printf("left:-\t");
            if(root->right != NULL)
                printf("right:%d\t",root->right->key);
            else
                printf("right:-\t");
            printf("\n");
    
            print_out(root->right);
        }
    }
    
    int main()
    {
        int key;
        rbt_node *root = NULL;
        int option=0;
        while(option!=5) 
        {
            printf("=====Lua chon=====\n-Them node(1)\n-Xoa node(2)\n-Tim node(3)\n-Hien thi (4)\n-Thoat(5)\n");
            do option=fgetc(stdin); while(-1 != option && isspace(option));
            option-='0';
            switch(option)
            {
                          case 1:
                               printf("Nhap node can chen: ");
                               scanf("%d",&key);
                               if(search_key(root,key) != NULL)
                               {
                                   printf("Node mang gia tri %d da co!\n", key);
                               }
                               else
                               {
                                   add_rbt_node(root,key,NULL);
                               }
                               break;
                          case 2:
                               printf("Nhap node can xoa: ");
                               scanf("%d",&key);
                               if(search_key(root,key) == NULL)
                               {
                                   printf("Node mang gia tri %d khong co!\n", key);
                               }
                               else
                               {
                                   //delete_rbt_node(root,key);
                               }
                               break;
                          case 3:
                               printf("Nhap key can tim: ");
                               scanf("%d",&key);
                               if(search_key(root,key) != NULL)
                                   printf("Cay co chua khoa: %d\n", key);
                               else
                                   printf("Cay khong chua khoa: %d\n", key);
                               break;
                          case 4:
                               printf("*****HIEN THI*****\n");
                               print_out(root);
                               break;
                          case 5: break;
                          default:
                                  printf("Loi nhap. Thu lai.\n");
            }
        }
        system("PAUSE");
        return 0;
    }
    khi chạy nó như thế này:


    thế là mình sai ở hàm search_key mà chưa hiểu sao, mong mọi người giúp đỡ.

  2. #2
    Ngày gia nhập
    01 2013
    Bài viết
    4

    Mặc định hàm sercg_key thiếu return

    hàm sercg_key thiếu return

  3. #3
    Ngày gia nhập
    01 2013
    Bài viết
    4

    hàm searrch_key thiếu return

  4. #4
    Ngày gia nhập
    09 2012
    Bài viết
    1

    Code:
    //du node con vao node can xoa
    void replace_node(rbt_node *&n, rbt_node *&child)
    {
         child->parent = n->parent;
    }
    hàm nay có đúng ko vậy bạn???

Các đề tài tương tự

  1. compiler Warning: Unreachable code và chạy sai trong khi code đúng. Vì sao?
    Gửi bởi lovemoney trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 19
    Bài viết cuối: 19-01-2012, 10:02 PM
  2. Cấu trúc dữ liệu so sánh giữa Red-Black tree và AVL tree. Ưu khuyết điểm như thế nào?
    Gửi bởi j3amboo trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 20-10-2011, 05:12 PM
  3. Đoạn code tìm hàng có tổng max trong ma trận chạy không đúng, sửa thế nào??
    Gửi bởi zodjac1990 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 10
    Bài viết cuối: 23-07-2011, 12:35 AM
  4. Red Black Tree! Help convert code C/C++ to C#
    Gửi bởi chicken_hamhoc trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 30-06-2009, 11:15 PM
  5. Code kiểm tra dãy cấp số cộng bằng C. Kiểm tra giúp mình xem chạy đúng không?
    Gửi bởi rong3sao trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 7
    Bài viết cuối: 11-04-2009, 09:25 AM

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