Cây nhị phân cân bằng là gì
Cây nhị phân là một cấu trúc dữ liệu quan trọng mà trong môn Cấu trúc dữ liệu và giải thuật các bạn sẽ được học, nó được sử dụng rất rộng rãi trong lập trình vì các ứng dụng của nó. Trong bài viết này, mình sẽ giới thiệu đến các bạn về cây nhị phân và một phiên bản đặc biệt của nó là cây nhị phân tìm kiếm. Trước tiên, ta cần biết được cây là gì? Show 1001 Tips: Con trỏ và hàm (Pointer & Function) trong C++ Bảng băm trong C++ Cấu trúc câyCấu trúc cây (Tree) là một tập hợp các phần tử gọi là nút (node), mỗi cây có một nút gốc (root) chứa nhiều nút con, mỗi nút con lại là một tập hợp các nút khác gọi là cây con (subtree). Cấu trúc câyCác khái niệm cơ bản về cây:
Khi bạn đã nắm được các khái niệm cơ bản này, chúng ta hãy đến luôn với cây nhị phân. Cây nhị phânCây nhị phân là một trường hợp đặc biệt của cấu trúc cây và nó cũng phổ biến nhất. Đúng như tên gọi của nó, cây nhị phân có bậc là 2 và mỗi nút trong cây nhị phân đều có bậc không quá 2. Cây nhị phânCác khái niệmCó một số khái niệm khác về cây nhị phân các bạn cần nắm như sau:
Định nghĩa cấu trúc nútNhìn vào hình, ta có thể dễ dàng phân tích được rằng, mỗi nút trong cây nhị phân sẽ gồm 3 thành phần như sau:
Chúng ta sẽ có struct lưu trữ một node như sau – ở đây để đơn giản mình sử dụng kiểu dữ liệu int cho thành phần dữ liệu của node:
Khi tạo một nút node mới, chúng ta cần phải gán lại các thành phần của node để nó không nhận giá trị rác, tránh lỗi không mong muốn. Chúng ta sẽ tạo một biến động cho node và trả về địa chỉ của node đó, mình sẽ có đoạn code tạo node như sau:
Định nghĩa cấu trúc câyĐể quản lý một cái cây, bạn chỉ cần quản lý được nút gốc, bạn có thể đi được đến các nhánh và lá của nó từ đó. Trên thực tế bạn không cần phải định nghĩa một kiểu dữ liệu nào để quản lý cả, tuy nhiên, để cho code rõ ràng hơn, bạn nên định nghĩa một kiểu dữ liệu cây nữa.
Lúc này, khi tạo một cây, bản chất là nó sẽ tạo cho bạn một con trỏ có thể trỏ vào một node.
Vì nó là con trỏ nên các bạn gán nó bằng NULL để tránh lỗi, nhưng để mọi thứ rõ ràng hơn, mình sẽ dùng hàm tạo cây đơn giản gán nó bằng NULL.
Duyệt cây nhị phânCó 3 cách duyệt cây nhị phân:
Để bạn hiểu rõ hơn ba cách duyệt này, chúng ta sẽ sử dụng lại hình ảnh cây nhị phân trên: Cây nhị phân
Ứng với từng cách duyệt đó, chúng ta sẽ có các hàm duyệt cây như sau: Duyệt tiền tự
Duyệt trung tự
Duyệt hậu tự
Hủy cây nhị phânĐể hủy đi cây nhị phân, các bạn cũng thực hiện duyệt và xóa đi các nút của cây, tuy nhiên, các bạn dễ thấy rằng, nếu ta duyệt tiền tự và trung tự, khi xóa nút nhánh thì sẽ bị mất luôn địa chỉ của các nút con. Do đó, việc hủy cây nhị phân bắt buộc phải duyệt hậu tự. Hay nói cách khác, bạn phải xóa các phần tử là nút lá xóa dần lên đến nút gốc. Chúng ta sẽ có hàm hủy như sau:
Như vậy là chúng ta đã tìm hiểu về cách tạo một nút, kết nối chúng lại thành một cây nhị phân, duyệt cây và hủy cây. Tiếp theo chúng ta sẽ tìm hiểu về cây nhị phân đặc biệt khác là cây nhị phân tìm kiếm. Tham khảo thêm các vị trí tuyển lập trình viên C++ mới nhất. Cây nhị phân tìm kiếmCây nhị phân tìm kiếm là cây nhị phân mà trong đó, các phần tử của cây con bên trái đều nhỏ hơn phần tử hiện hành và các phần tử của cây con bên phải đều lớn hơn phần tử hiện hành. Do tính chất này, cây nhị phân tìm kiếm không được có phần tử cùng giá trị. Binary Search TreeNhờ vào tính chất đặc biệt này, cây nhị phân tìm kiếm được sử dụng để tìm kiếm phần tử nhanh hơn (tương tự với tìm kiếm nhị phân). Khi duyệt cây nhị phân theo cách duyệt trung tự, bạn sẽ thu được một mảng có thứ tự. Chúng ta sẽ lần lượt tìm hiểu qua chúng. Thêm phần tử vào cây nhị phân tìm kiếmĐể thêm phần tử vào cây nhị phân tìm kiếm, ta phải thêm vào cây nhưng vẫn đảm bảo được cây đó vẫn là cây nhị phân tìm kiếm. Ví dụ thêm phần tử 12 vào cây trong hình trên, mình sẽ cần chèn vào vị trí bên trái 13. Hàm duyệt tìm vị trí thích hợp và chèn của mình như sau:
Tìm một phần tử trong cây nhị phân tìm kiếmNhư đã giới thiệu ở trên, để tìm một phần tử trong cây nhị phân tìm kiếm, chúng ta sẽ thực hiện tương tự việc tìm kiếm nhị phân. Nếu như nút cần tìm nhỏ hơn nút đang xét, chúng ta sẽ tìm cây con bên trái, ngược lại chúng ta sẽ tìm trong cây con bên phải, nếu đúng nút cần tìm thì mình sẽ trả về địa chỉ của nút đó. Mình sẽ có thuật toán sau: 0Hủy nút trên cây nhị phân tìm kiếmĐể hủy một nút có khóa X trong cây nhị phân tìm kiếm, chúng ta cần giải quyết ba trường hợp sau:
Đối với hai trường hợp đầu thì dễ, tuy nhiên, với trường hợp thứ 3, chúng ta cần phải giải quyết vấn đề tìm phần tử thế mạng cho x, chúng ta sẽ có hai cách thực hiện như sau:
Lấy ví dụ cho các bạn dễ hiểu hơn, hình phía trên, xóa đi phần tử 18 theo cách 1, phần tử lớn nhất của cây con bên trái là 15, vậy thì thay 18 bằng 15 rồi xóa đi nút 15 cuối. Cách 2, phần tử nhỏ nhất của cây con bên phải là 23, vậy 18 sẽ thay bằng 23 và xóa nút 23 đó đi. Đối với hai trường hợp đầu tiên khá đơn giản, nên mình sẽ lồng nó vào code luôn ở phần dưới, mình sẽ giải quyết cách tìm phần tử thế mạng ở trường hợp 3 trước và theo cả hai cách. Theo cách 1, mình sẽ làm như sau: Trường hợp 1 1Đối với trường hợp này, các bạn phải gọi hàm FindAndReplace1(p, root->right) trong hàm DeleteNode ở phía trên. Trường hợp thứ 2 thì ngược lại. Trường hợp 2 2Và trong hàm DeleteNode, các bạn sẽ gọi hàm FindAndReplace(p, root->left). Bây giờ, tổng hợp lại, chúng ta đã có thể dể dàng xóa một nút khỏi cây nhị phân tìm kiếm, mình sẽ code như sau: 3Tổng kếtVậy là qua bài viết này, mình đã giới thiệu đến các bạn về cấu trúc cây, cây nhị phân và cây nhị phân tìm kiếm. Đương nhiên, mình không phải “master” và mình cũng không thể nào mà nắm được hết tất cả các lý thuyết đồ thị hay thuật toán, do đó sai sót là không thể tránh khỏi, hy vọng các bạn góp ý thêm. Cảm ơn các bạn đã theo dõi bài viết, nếu thấy bài viết này hay, đừng quên chia sẻ cho mọi người cùng biết nhé! Cảm ơn các bạn! |