Cây tìm kiếm nhị phân – Binary search tree

This entry is part 8 of 16 in the series Cấu trúc dữ liệu

Trong bài viết này, chúng ta sẽ tiếp tục tìm hiểu về cấu trúc dữ liệu Cây, và cụ thể là cây tìm kiếm nhị phân. Đây là một cấu trúc dữ liệu được tiêu dùng khá phổ biến và mang tính ứng dụng cao. Hãy cùng Nguyễn Văn Hiếu tìm hiểu và cài đặt cây tìm kiếm nhị phân sử dụng tiếng nói C/C++ nhé.

1. Lý thuyết về cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân(TA: Binary Search Tree – viết tắt: BST) – là một cây nhị phân và mang thêm những ràng buộc sau đây:

  1. Trị giá của tất cả những Node ở cây con bên trái phải <= trị giá của Node gốc.
  2. Trị giá của tất cả những Node ở cây con bên phải phải > trị giá của Node gốc.
  3. Tất cả những cây con(bao gồm bên trái và phải) cũng đều phải đảm bảo Hai tính chất trên.
Nhận diện cây tìm kiếm nhị phân. Hình thứ Hai ko phải BST do vi phạm ràng buộc số 2

Cây tìm kiếm nhị phân là một cấu trúc dữ liệu hiệu quả cho phép chúng ta xây dựng nên một danh sách mà dữ liệu trên đó được sắp xếp:

  • Nó được gọi là cây nhị phân vì mỗi Node của cây chỉ mang tối đa hai con
  • Nó được gọi là cây tìm kiếm nhị phân vì nó mang thể được sử dụng để tìm kiếm sự hiện diện của một phần tử trong thời kì O(log (n)).

2. Cài đặt cây BST

Sau đây, tôi sẽ cùng những bạn đi cài đặt cây tìm kiếm nhị phân sử dụng danh sách liên kết. Do đó, dòng bạn cần lưu giữ là Node root của cây mà thôi. Với được root chúng ta mang thể duyệt qua mọi phần tử của cây.

Trước nhất, chúng ta sẽ khái niệm kiểu dữ liệu cho những Node của cây:

Tiếp theo, chúng ta sẽ triển khai code cho tức chức năng của cây BST. Chúng ta sẽ sử dụng đệ quy rất nhiều trong những chức năng này. Bạn mang thể tự tìm hiểu cách viết khử đệ quy nhé.

2.1. Hàm phóng thích dữ liệu

Chúng ta sẽ sử dụng hàm này lúc muốn xóa một cây con hoặc toàn bộ cây bằng cách phân phối Node root của cây muốn xóa. Việc phóng thích được thực hiện theo trình tự:

  1. Gọi đệ quy xóa cây con bên trái
  2. Gọi đệ quy xóa cây con bên phải
  3. Phóng thích vùng nhớ cho con trỏ hiện tại

2.2. Hàm điều hướng của cây

Hai hàm dưới đây sẽ phục vụ chúng ta trong quá trình Insert(thêm phần tử vào cây) và Tìm kiếm trên cây tìm kiếm nhị phân.

Nếu bạn cho phép cây BST mang trị giá trùng lặp, hãy lưu ý hàm LeftOf nhé. Ở đây tôi sẽ ko cho phép thêm phần tử đã mang trên cây(bỏ qua trùng lặp trị giá).

2.3. Thêm phần tử vào BST

Việc thêm Một phần tử vào cây nhị phân tìm kiếm vẫn phải đảm bảo được những ràng buộc của một BST đã trình bày ở trên. Tương tự, bạn cần phải tìm kiếm vị trí thích hợp trong BST để lưu giữ nó.

Nếu bạn quan tâm, bạn sẽ nhìn thấy vị trí của những Node được thêm vào sẽ luôn Node lá(ko mang Child nào hết). Tương tự, tại vị trí đó trước lúc những Node mới tới ở thì nó là NULL. Ta mang thứ tự như sau:

  1. Nếu Node hiện tại = NULL, đó là vị trí cần thêm. Thêm vào BST và kết thúc
  2. Nếu trị giá cần thêm < trị giá root hiện tại, gọi đệ quy Insert vào cây con bên trái
  3. Nếu trị giá cần thêm > trị giá root hiện tại, gọi đệ quy Insert vào cây con bên phải.

Hãy xem hình ảnh mô phỏng việc thêm trị giá 4 vào BST dưới đây:

2.4. Tìm kiếm trên BST

Việc tìm kiếm cũng tương tự như việc thêm phần tử vào BST. Ta mang thứ tự như sau:

  1. Nếu Node hiện tại mang trị giá = trị giá cần tìm, trả về true và kết thúc.
  2. Nếu Node hiện tại mang trị giá > trị giá cần tìm, gọi đệ quy tìm ở cây con bên trái.
  3. Nếu Node hiện tại mang trị giá < trị giá cần tìm, gọi đệ quy tìm ở cây con bên phải
  4. Nếu tìm tới hết cây(Node đó = NULL) mà ko xảy ra (1), trả về false và kết thúc.

Chúng ta sẽ quan sát cách BST tìm kiếm trị giá 4 trong hình ảnh dưới đây:

2.5. Lấy trị giá con trái nhất

Rất đơi giản, duyệt theo con trỏ trỏ tới cây con bên trái tới chừng nào ko còn con bên trái nữa thì đó là con trái nhất rồi.

Hàm này sẽ được chúng ta sử dụng trong việc xóa một Node mang trị giá chỉ định trên BST ở mục tiếp theo.

Hình ảnh dưới đây mô phỏng hàm LestMostChild hoạt động:

Con trái nhất của Node root(15) là 8; Con trái nhất của Node root(20) là 16

2.6. Xóa Node trong BST

Việc xóa Node trong BST có nhẽ là phức tạp nhất trong những chức năng của cây tìm kiếm nhị phân. Nếu Node bạn cần xóa là Node lá thì việc xóa rất thuần tuý. Chiếc khó ở chỗ xóa một Node ở trung gian, lúc đó, bạn phải tìm cách xóa và nối lại mà vẫn đảm bảo cây mới vẫn là BST. Chúng ta sẽ xem xét từng trường hợp trước lúc code nhé:

1. Node cần xóa là Node lá(ko mang child nào cả)

Giả sử ta cần xóa 20 trong hình dưới đây, thuần tuý là chỉ cần phóng thích ô nhớ đó.

2. Node cần xóa mang Một child

Trong trường hợp này, Node bị xóa sẽ được phóng thích và cây con duy nhất của Node bị xóa sẽ được liên kết trực tiếp với cha của Node bị xóa.

3. Node cần xóa mang đủ Hai child

Giả sử cần xóa Node khoanh đỏ. Lúc đó, ta cần tìm Node thế thân cho Node đỏ này, đó là Node LeftMostChild của cây con bên phải của Node đỏ(72) = Node khoanh màu xanh(54) . Sau đó, gọi đệ quy Xóa Node màu xanh. Lúc đó Node cần xóa sẽ quay trở về trường hợp Một hoặc 2(Trong ảnh này là trường hợp 2 – mang Một child).

Đây là trường hợp nan giải nhất, nhưng chúng ta vẫn mang cách làm như sau:

  1. Tìm Node của con trái nhất(giả sử nó là leftmost) của cây con bên phải của Node cần xóa.
  2. Cập nhật trị giá của Node cần xóa = trị giá của Node leftmost.
  3. Gọi đệ quy hàm Delete xóa Node leftmost khỏi BST.

Giảng giải:

  • Lúc muốn xóa Node mang Hai con, ta cần tìm Node nào đó trong BST thỏa mãn tính chất to hơn to hơn tất cả những con bên trái và nhỏ hơn tất cả những con bên phái -> Node đó chính là LeftMostChild của con bên phải của Node cần xóa.
  • Ta chỉ cần sửa trị giá của Node cần xóa, ko cần xóa Node đó làm gì. Thay vào đó, xóa Node bị thế thân(LeftMostChild của con bên phải của Node cần xóa).

3. Duyệt cây tìm kiếm nhị phân

Ở mục này mình sẽ trình bày về 3 cách duyệt cây tìm kiếm nhị phân. Chúng ta sẽ đi vào chi tiết từng cách nhé. Thứ tự duyệt được đặt tên phụ thuộc vào vị trí của Node root trong quá trình duyệt:

  • PreOrder: Node -> Left -> Right
  • InOrder: Left -> Node -> Right
  • PostOrder: Left -> Right -> Node
  • Thực ra 3 phần tử Left, Right, Node mang tất cả 6 hoán vị cơ. Còn 3 dòng nữa những bạn tự cài nhé.

3.1. Duyệt PreOrder

  1. Ghé thăm Node root
  2. Gọi đệ quy duyệt qua cây con bên trái
  3. Gọi đệ quy duyệt qua cây con bên phải

Thứ tự duyệt pre_order trên BTS

3.2. Duyệt InOrder

  1. Gọi đệ quy duyệt qua cây con bên trái
  2. Ghé thăm Node root
  3. Gọi đệ quy duyệt qua cây con bên phải

Thứ tự duyệt in_order trên BTS

3.1. Duyệt PostOrder

  1. Gọi đệ quy duyệt qua cây con bên trái
  2. Gọi đệ quy duyệt qua cây con bên phải
  3. Ghé thăm Node root

Duyệt post_order trên BTS

4. Code đầy đủ cây tìm kiếm nhị phân

Trong hàm main tôi đã cài đặt BTS cho cây nhị phân sau:

Cây nhị phân tìm kiếm được sử dụng trong source code

Nhờ những bạn rà soát kết quả chạy của code:

5. Bài tập thực hiện

  • https://vn.spoj.com/problems/NKTREE/
  • http://ntucoder.net/Problem/List?ThemeID=17
  • https://www.hackerearth.com/practice/data-structures/trees/binary-search-tree/practice-problems/

Related Posts

Leave a Comment

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *