Cấu trúc dữ liệu cây
Cấu trúc dữ liệu cây là gì ? Cấu trúc dữ liệu cây biểu diễn các nút (node) được kết nối bởi các cạnh. Chúng ta sẽ tìm hiểu về Cây nhị phân (Binary Tree) và Cây tìm kiếm nhị phân (Binary Search Tree) trong phần này. Cây nhị phân là một cấu trúc dữ liệu đặc biệt được sử dụng cho mục đích ...
Cấu trúc dữ liệu cây là gì ?
Cấu trúc dữ liệu cây biểu diễn các nút (node) được kết nối bởi các cạnh. Chúng ta sẽ tìm hiểu về Cây nhị phân (Binary Tree) và Cây tìm kiếm nhị phân (Binary Search Tree) trong phần này.
Cây nhị phân là một cấu trúc dữ liệu đặc biệt được sử dụng cho mục đích lưu trữ dữ liệu. Một cây nhị phân có một điều kiện đặc biệt là mỗi nút có thể có tối đa hai nút con. Một cây nhị phân tận dụng lợi thế của hai kiểu cấu trúc dữ liệu: một mảng đã sắp thứ tự và một danh sách liên kết (Linked List), do đó việc tìm kiếm sẽ nhanh như trong mảng đã sắp thứ tự và các thao tác chèn và xóa cũng sẽ nhanh bằng trong Linked List.
Các khái niệm cơ bản về cây nhị phân
Dưới đây là một số khái niệm quan trọng liên quan tới cây nhị phân:
Biểu diễn cây tìm kiếm nhị phân
Cây tìm kiếm nhị phân biểu diễn một hành vi đặc biệt. Con bên trái của một nút phải có giá trị nhỏ hơn giá trị của nút cha (của nút con này) và con bên phải của nút phải có giá trị lớn hơn giá trị của nút cha (của nút con này). Hình minh họa:
Chúng ta đang triển khai cây bởi sử dụng đối tượng nút và kết nối chúng thông qua các tham chiếu.
Nút (Node) trong cây tìm kiếm nhị phân
Một nút sẽ có cấu trúc như dưới đây. Nút có phần dữ liệu và phần tham chiếu tới các nút con bên trái và nút con bên phải.
struct node { int data; struct node *leftChild; struct node *rightChild; };
Trong một cây, tất cả các nút chia sẻ cùng một cấu trúc.
Hoạt động cơ bản trên cây tìm kiếm nhị phân
Dưới đây liệt kê các hoạt động cơ bản có thể được thực hiện trên cấu trúc dữ liệu cây tìm kiếm nhị phân:
Trong chương này, chúng ta sẽ tìm hiểu chi tiết cách tạo (chèn) cấu trúc cây và cách tìm kiếm một phần tử dữ liệu trên một cây. Chương sau chúng ta sẽ tìm hiểu chi tiết về các cách duyệt cây.
Hoạt động chèn trong cây tìm kiếm nhị phân
Bước chèn đầu tiên sẽ tạo thành cây. Tiếp đó là sẽ chèn từng phần tử vào trong cây. Đầu tiên chúng ta cần xác định vị trí chính xác của nó. Bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu là nhỏ hơn giá trị khóa, thì tìm kiếm vị trí rỗng trong cây con bên trái và chèn dữ liệu. Nếu không nhỏ hơn, tìm vị trí rỗng trong cây con bên phải và chèn dữ liệu. (Nếu bạn chưa hiểu, bạn có thể đọc lại phần Biểu diễn cây tìm kiếm nhị phân ở trên để biết tại sao lại chèn như vậy và xem hình minh họa)
Giải thuật cho hoạt động chèn
If root là NULL thì tạo nút gốc (root node) return If root đã tồn tại thì sau đó so sánh dữ liệu với node.data while tới vị trí chèn đã xác định If dữ liệu là lớn hơn node.data tới cây con bên phải else tới cây con bên trái kết thúc while chèn dữ liệu Kết thúc If
Giải thuật mẫu cho hoạt động chèn
Từ trên ta có thể suy ra giải thuật mẫu cho hoạt động chèn trong cây tìm kiếm nhị phân như sau:
void insert(int data) { struct node *tempNode = (struct node*) malloc(sizeof(struct node)); struct node *current; struct node *parent; tempNode->data = data; tempNode->leftChild = NULL; tempNode->rightChild = NULL; //Nếu cây là trống, chúng ta tạo root node if(root == NULL) { root = tempNode; }else { current = root; parent = NULL; while(1) { parent = current; //tới cây con bên trái if(data < parent->data) { current = current->leftChild; //chèn dữ liệu vào bên trái if(current == NULL) { parent->leftChild = tempNode; return; } } //tới cây con bên phải else { current = current->rightChild; //chèn dữ liệu vào bên phải if(current == NULL) { parent->rightChild = tempNode; return; } } } } }
Để tìm hiểu code đầy đủ của cấu trúc dữ liệu cây trong ngôn ngữ C, mời bạn click chuột vào chương: Duyệt cây trong C.
Hoạt động tìm kiếm trong cây nhị phân
Mỗi khi một phần tử cần tìm kiếm: bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu là nhỏ hơn giá trị khóa, thì tìm kiếm phần tử trong cây con bên trái; nếu không nhỏ hơn thì tìm kiếm phần tử trong cây con bên phải. (Nếu bạn chưa hiểu, bạn có thể đọc lại phần Biểu diễn cây tìm kiếm nhị phân ở trên để biết tại sao lại tìm kiếm như vậy và xem hình minh họa)
Giải thuật cho hoạt động tìm kiếm
If root.data là bằng với search.data return root else while không tìm thấy dữ liệu If data là lớn hơn node.data tới cây con bên phải else tới cây con bên trái If data được tìm thấy return node kết thúc while return không tìm thấy data Kết thúc if
Giải thuật mẫu cho hoạt động tìm kiếm
Từ trên ta có thể suy ra giải thuật mẫu cho hoạt động tìm kiếm trong cây tìm kiếm nhị phân như sau:
struct node* search(int data) { struct node *current = root; printf("Truy cap phan tu: "); while(current->data != data) { if(current != NULL) printf("%d ",current->data); //tới cây con bên trái if(current->data > data) { current = current->leftChild; } //else tới cây con bên phải else { current = current->rightChild; } //không tìm thấy if(current == NULL) { return NULL; } return current; } }
Để tìm hiểu code đầy đủ của cấu trúc dữ liệu cây trong ngôn ngữ C, mời bạn click chuột vào chương: Duyệt cây trong C.
Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.
Bài học Cấu trúc dữ liệu và giải thuật phổ biến tại code24h.com: