# BST : Binary Search Tree (Cây nhị phân tìm kiếm)
**Người viết**: _Nguyễn Phú Vinh_ (THPT Quang Trung)
## Nói về cây:
### Định nghĩa
Cây là một cấu trúc dữ liệu gồm một tập hữu hạn các nút, giữa các nút có một quan hệ phân cấp gọi là quan hệ **"cha - con"**. Có một nút đặc biệt gọi là gốc (root).
Có thể định nghĩa cây bằng các đệ quy như sau:
* Mỗi nút là một cây, nút đó cũng là gốc của cây ấy
* Nếu $n$ là một nút và $n_1$, $n_2$, ..., $nk$ lần lượt là gốc của các cây $T_1$, $T_2$, ..., $T_k$; các cây này đôi một không có nút chung. Thì nếu cho nút $n$ trở thành cha của các nút $n_1$, $n_2$, ..., $n_k$ ta sẽ được một cây mới $T$. Cây này có nút n là gốc còn các cây $T_1$, $T_2$, ..., $T_k$ trở thành các **cây con (subtree)** của gốc.
Để tiện, người ta còn cho phép tồn tại một cây không có nút nào mà ta gọi là **cây rỗng (null tree)**.
Về mặt đồ thị,ta định nghĩa cây là:
* Một đồ thị liên thông
* có $n$ và $n-1$ cạnh
* Nếu ta thêm bất kì 1 cạnh vào cây thì sẽ tạo ra một **chu trình**
### Cây nhị phân
Cây nhị phân là một dạng quan trọng của cấu trúc cây. Nó có đặc điểm là mọi nút trên cây chỉ có tối đa hai nhánh con. Với một nút thì người ta cũng phân biệt cây con trái và cây con phải của nút đó. Cây nhị phân là cây có tính đến thứ tự của các nhánh con. Cần chú ý tới một số dạng đặc biệt của cây nhị phân
Chiều cao (height) hay chiều sâu (depth) của một cây là số mức lớn nhất của nút có trên cây đó. Cây ở trên có chiều cao là 4
Các cây nhị phân trong hình trên được gọi là **cây nhị phân suy biến (degenerate binary tree)**, các nút không phải là lá chỉ có một nhánh con. Cây a) được gọi là cây lệch phải, cây b) được gọi là cây lệch trái, cây c) và d) được gọi là cây zíc-zắc.
## Cây nhị phân tìm kiếm là gì?
Cây nhị phân tìm kiếm (binary search trees - BST) là một dạng cây nhị phân, trong đó
mỗi nút chứa một phần tử (khóa). Khóa chứa trong mỗi nút phải thỏa mãn hai điều
kiện:
* Lớn hơn mọi khóa trong nhánh con trái
* Nhỏ hơn mọi khóa trong nhánh con phải
## Các thao tác
### Cấu tạo nút
BST trong bài này được biểu diễn bằng một cấu trúc các nút và con trỏ liên kết. Mỗi nút trên BST gồm các biến và con trỏ như sau:
```cpp=1
struct node { /// tạo cấu trúc nút bst
int key; // lưu giá trị nút
node* p; // con trỏ chỉ đến nút cha
node* l; // con trỏ chỉ đến nút trái
node* r; // con trỏ chỉ đến nút phải
};
```
Ta đồng nhất khái niệm nút với con trỏ tới chính nút đó cho tiện trình bày. Tuy nhiên trong một vài trường hợp vẫn cần định rõ ràng khái niệm nút và con trỏ tới nút, vì vậy ta định nghĩa thêm kiểu ```bptr``` là kiểu con trỏ tới một nút. Biến ```root``` là con trỏ tới nút gốc của ```BST```. Cây được quản lý qua nút gốc, vì vậy trong các thao tác trên ```BST```, ta coi
nút gốc là đại diện cho cây và có thể đồng nhất khái niệm cây/nhánh với khái niệm nút gốc của cây/nhánh đó.
Ta sẽ sử dụng luôn ```struct``` để build cây:
```cpp=1
struct bst {
struct node { /// tạo cấu trúc nút bst
int key; // lưu giá trị nút
node* p; // con trỏ chỉ đến nút cha
node* l; // con trỏ chỉ đến nút trái
node* r; // con trỏ chỉ đến nút phải
};
using bptr=node*;
bptr root;//Gốc của bst
node nll; //Nút lính canh, các trường vô nghĩa
bptr nil; //Con trỏ nil
};
```
Thông thường người ta dùng con trỏ ```nullptr``` hoặc ```NULL``` để gán cho những liên kết không tồn tại.
Tuy vậy việc sử dụng con trỏ ```nullptr``` sẽ dẫn đến một số phiền toái: Muốn truy cập các giá trị của nút x sẽ phải kiểm tra $x \neq$ ```nullptr``` trước, kéo theo rất nhiều lệnh if… phải thêm vào trong các thao tác xử lý cây
Ở đây ta dùng con trỏ nil để gán cho những liên kết không tồn tại. Khác với con trỏ ```nullptr```, con trỏ nil chứa địa chỉ của một nút có thực: nll, quy ước rằng nút này cũng như các giá trị của nó là vô nghĩa. Mục đích của con trỏ nil cũng như nút lính canh nll là để ta có thể thoải mái viết ```nil->r```,``` nil->l```, ```nil->p```, mà không bị gặp lỗi như đối với con trỏ ```nullptr```.
Tóm lại thì tác dụng của ```nil``` như ```nullptr```
### Khởi tạo cây:
```cpp=1
bst(){
nil=&nll;
root=nil; //Khởi tạo cây rỗng
}
```
Ở đây ta sẽ dùng đến ```Constructor```
Nhắc lại về ```Constructor``` trong ```struct```
Đây là hàm khởi tạo trong ```struct``` không cần kiểu trả về,nó giúp ta khởi tạo các dữ liệu ban đầu cho ```struct```
Vậy ta đã khởi tạo hoàn thành 1 cái cây ```BST```:
```cpp=1
struct bst {
struct node { /// tạo cấu trúc nút bst
int key; // lưu giá trị nút
node* p; // con trỏ chỉ đến nút cha
node* l; // con trỏ chỉ đến nút trái
node* r; // con trỏ chỉ đến nút phải
};
using bptr=node*;
bptr root;//Gốc của bst
node nll; //Nút lính canh, các trường vô nghĩa
bptr nil; //Con trỏ nil
bst(){ //constructor
nil=&nll;
root=nil; //Khởi tạo cây rỗng
}
};
```
### Các cách duyệt cây
Ở đây ta sẽ nói về $3$ cách duyệt chính của ```BST```
* **Duyệt theo thứ tự sau (Post-order Traversal) aka RNL(Right-Node-Left)**: Duyệt cây theo thứ tự trước sẽ thăm nút hiện tại trước, sau đó là nút con trái, và cuối cùng là nút con phải.
:::spoiler
```cpp=1
void nlr(bptr x){
if(x==nil) return;
///.... xử lý nút
nlr(x->l);// Duyệt cây con bên trái
nlr(x->r);// Duyệt cây con bên phải
}
```
:::
* **Duyệt theo thứ tự giữa (In-order Traversal) aka LNR(Left-Node-Right):** Duyệt cây theo thứ tự giữa sẽ thăm nút con trái, sau đó là nút hiện tại, và cuối cùng là nút con phải.
:::spoiler
```cpp=1
void lnr(bptr x) {
if (x == nil) return;
lnr(x->l);// Duyệt cây con bên trái
/// .....xử lý nút
lnr(x->r);// Duyệt cây con bên phải
}
```
:::
* **Duyệt theo thứ tự sau (Post-order Traversal) aka RNL(Right-Node-Left):** Duyệt cây theo thứ tự sau sẽ thăm nút con trái, sau đó là nút con phải, và cuối cùng là nút hiện tại
:::spoiler
```cpp=1
void rnl(bptr x){
if (x == nil) return;
rnl(x->r); // Duyệt cây con bên phải
//....... Xử lý nút,
rnl(x->l); // Duyệt cây con bên trái
}
```
:::
#### Bổ đề 1:
:::danger
Nếu duyệt cây nhị phân tìm kiếm theo thứ tự giữa **(In-order Traversal)**, các khóa trên cây sẽ được liệt kê theo thứ tự tăng dần.
:::
**Chứng minh:**
:::info
Ta chứng minh bằng quy nạp:
Rõ ràng bổ đề đúng với ```BST``` chỉ có một nút. Giả sử bổ đề đúng với mọi BST có ít hơn $n$ nút, xét một ```BST``` bất kỳ gồm $n$ nút, và ở nút gốc chứa khóa $k$, thuật toán duyệt cây theo thứ tự giữa trước hết sẽ liệt kê tất cả các khóa trong nhánh con trái **theo thứ tự tăng dần** **(giả thiết quy nạp)**, các khóa này đều $< k$ **(tính chất của cây nhị phân tìm kiếm)**.
Tiếp theo thuật toán sẽ liệt kê khóa $k$ của nút gốc, cuối cùng, lại theo giả thiết quy nạp, thuật toán sẽ liệt kê tất cả các khóa trong nhánh con phải **theo thứ tự tăng dần**, tương tự như trên, các khóa trong nhánh con phải đều $> k$. Vậy tất cả $n$ khóa trên BST sẽ được liệt kê theo thứ tự tăng dần, định lý đúng với mọi BST gồm n nút. **ĐPCM**.
:::
:::success
Bạn cũng có thể chứng minh điều ngược lại đúng với thứ tự duyệt sau **(Post-order Traversal)**
:::
### Các thao tác trên cây
#### Chèn/thêm 1 phần tử
Chèn một khóa $k$ vào ```BST``` tức là thêm một nút mới chứa khóa $k$ trên ```BST``` và móc nối nút đó vào ```BST``` sao cho vẫn đảm bảo cấu trúc của một ```BST```.
:::warning
Hãy dừng lại và suy nghĩ bạn sẽ làm như nào?
:::
:::spoiler
Bài toán chèn $k$ vào cây ```BST``` sẽ được quy về bài toán:
:::info
Chèn $k$ vào cây con trái hay cây con phải, tùy theo khóa $k$ nhỏ hơn hay lớn hơn hoặc bằng khóa chứa trong nút gốc
Phép chèn được thực hiện dựa trên nguyên lý **chia để trị**:
:::success
**Trường hợp cơ sở** là $k$ được chèn vào một nhánh cây rỗng, khi đó ta chỉ việc tạo nút mới, móc nối nút mới vào nhánh rỗng này và đặt khóa $k$ vào nút mới đó.
:::
:::info
Để các đoạn code sau này được ngắn gọn, ta viết hàm:
```set_link(parent, child, is_r)```
Có nhiệm vụ cho nút child làm con của nút parent (làm con trái hay con phải tùy theo is_r là false hay true)
:::spoiler
```cpp=1
void set_link(bptr parent, bptr child, bool is_r) {
child->p = parent;
if(is_r) parent->r = child;
else parent->l = child;
}
```
Đồng thời ta sẽ tạo thêm một hàm nữa,dùng để khởi tạo nút:
```cpp=1
bptr create(int val) {
bptr newn = new node();
newn->key = val;
newn->p = nil;
newn->l = nil;
newn->r = nil;
return newn;
}
````
:::
:::success
(Có thể thấy công dụng của việc dùng con trỏ nil thay cho ```nullptr```: Ta thoải mái truy cập ```child->p```, ```parent->r```, ```parent->l```, mà không lo ngại sinh lỗi).
:::
Hàm chèn khóa $k$ vào ```BST``` có thể viết như sau:
```cpp=1
//chèn 1 nút vào cây
void ins(int k) {
bptr y = nil;
bptr x = root; //Bắt đầu từ gốc
while(x != nil){ //Chưa chạm tới nút rỗng
if(k == x->key) return; //Khóa k đã có trên bst
y = x;//Giữ lại vị trí x cũ
x = (k < x->key) ? x->l : x->r; //x chuyển xuống con trái hoặc con phải
}
x = create(k); //Tạo nút x mới chứa khóa k
set_link(y, x, k > y->key);
if(root == nil) root = x;//Nếu gốc đang là nil thì cập nhật gốc mới là x
}
```
#### Tìm kiếm
###### Tìm khóa lớn nhất và nhỏ nhất
Theo cấu trúc của ```BST```, khóa nhỏ nhất của ```BST``` nằm ở nút cực trái: Bắt đầu từ gốc ta đi sang con trái chừng nào vẫn còn đi được, quá trình dừng lại ở nút cực trái là nút chứa khóa nhỏ nhất.
```cpp=1
bptr min_bst(bptr x){
while(x->l!= nil ) x=x->l;
return x;
}
```
Vấn đề tương tự với việc tìm khóa lớn nhất: Khóa nằm ở nút cực phải của ```BST```
```cpp=1
bptr max_bst(bptr x){
while(x->r!= nil ) x=x->r;
return x;
}
```
##### Tìm nút liền trước và nút liền sau
Ở đây là ta dùng cho thứ tự duyệt giữa,vậy nút liền trước của một nút $x$ sẽ là nút nhỏ hơn $x$ và nút liền sau sẽ là nút lớn hơn $x$
Chúng ta sẽ tìm nút liền trước như sau:
* Nếu $x$ có con trái thì trả về nút cực phải của nhánh con trái.
* Nếu $x$ không có con trái thì từ $x$, ta đi dần lên phía gốc cây cho tới khi gặp một nút chứa $x$ trong nhánh con phải thì dừng lại và trả về nút đó.
```cpp=1
///Tìm nút liền trước nút x theo thứ tự giữa, trả về nil nếu không tìm thấy
bptr lower(bptr x){
if(x->l!=nil) return max_bst(x->l); //x có con trái,trả về nút cực phải trong nhánh con trái
while(x->p!=nil && x->p->r!=x) x=x->p;//Đi lên cha x
return x->p; //Trả về cha x, mặc nhiên trả về nil nếu x đã là gốc
}
```
Việc tìm nút đằng sau nút $x$ có cách làm tương tự nếu ta đổi vai trò $l$ và $r$, ```max_bst``` và ```min_bst```
```cpp=1
bptr upper(bptr x){
if(x->r!=nil) return min_bst(x->r); //x có con phải
//Trả về nút cực phải trong nhánh con trái
while (x->p != nil && x->p->l != x) //x không phải gốc và x không là con trái
x=x->p;//Đi lên cha x
return x->p; //Trả về cha x, mặc nhiên trả về nil nếu x đã là gốc
}
```
##### Tìm kiếm nút
Phép tìm kiếm nhận vào một khóa $k$. Nếu khóa $k$ có trong BST thì trả về một nút chứa khóa $k$, nếu không trả về ```nil```.
Phép tìm kiếm trên ```BST``` có thể cài đặt bằng hàm ```_find```, hàm này được xây dựng dựa trên nguyên lý ***chia để trị***:
Bắt đầu với nút $x$ là gốc, nếu nút $x$ chứa khóa $= k$ thì hàm đơn giản trả về nút $x$, nếu không thì việc tìm kiếm sẽ được tiến hành tương tự trên cây con trái hoặc cây con phải tùy theo nút $x$ chứa khóa nhỏ hơn hay lớn hơn $k$:
```cpp=1
bptr _find(int k)
{
bptr x=root;
while(x!=nil&& x->key!=k) x=(k<x->key ? x->l :x->r);
return x;
}
```
#### Xoá nút
Việc xóa một nút $x$ trong ```BST``` có thể thực hiện bằng cách xóa đi khóa chứa trong nút $x$. Phép xóa được thực hiện như sau:
* Nếu $x$ có ít hơn $2$ con, lấy nút con (nếu có) của $x$ lên thay cho $x$ và hủy nút $x$.
* Nếu $x$ có hai con, xác định nút $y$ là nút cực phải của nhánh con trái, đưa khóa chứa trong nút $y$ lên nút $x$ rồi xóa nút $y$. Chú ý rằng nút $y$ chắc chắn không có nhánh con phải, việc xóa quy về trường hợp trên (Hình dưới)
```cpp=1
//Xóa nút x khỏi BST
void ers(bptr x) {
bptr y;
if (x->l != nil && x->r != nil) //x có 2 con
{
y = max_bst(x->l); //y = nút cực phải của nhánh con trái
x->key = y->key; //Đưa khóa trong y sang x
x = y; //Quy về xóa nút x không có con phải
}
//x có ít hơn 2 nhánh con, cắt x khỏi cây
y = x->l != nil ? x->l : x->r; //y = nút con của x (nếu có)
set_link(x->p, y, x->p->r == x); //Cho y làm con của x->P thay cho x
if (x == root) //x đang là gốc
root = y; //thì y sẽ là gốc mới
delete x; //Hủy nút x
}
```
:::warning
Mặc dù đây là phương pháp được trình bày trong hầu hết các sách thuật toán để xóa nút trên ```BST```. Cách làm này thực ra rất nguy hiểm và không bao giờ nên sử dụng.
**Hai nhược điểm lớn nhất của nó là:**
* Thuật toán cần di chuyển dữ liệu khóa giữa các nút, khi khóa thuộc kiểu dữ liệu có **cấu trúc phức tạp**, việc di chuyển dữ liệu khóa khá tốn thời gian và kéo theo nhiều rắc rối.
* Thuật toán có nhiệm vụ xóa nút, nhưng trên thực tế nó chỉ loại bỏ khóa trong nút đó ra khỏi ```BST```, nút bị xóa có thể là một nút khác. Nếu con trỏ tới một nút đang lưu lại ở đâu đó trong chương trình cho nhiệm vụ khác, khi đó sẽ có tình trạng con trỏ tới nút **“đã bị xóa”** nhưng thực ra nút đó vẫn tồn tại, trong khi con trỏ tới nút không hề bị xóa nhưng thực ra nút đó không còn tồn tại nữa. Những lỗi truy cập bộ nhớ trái phép có cơ hội phát sinh và không dễ để kiểm soát
:::
Vì vậy để xóa nút 𝑥 một cách chính quy hơn, ta sẽ sử dụng cách cài đặt khác:
:::success
* Nếu $x$ có ít hơn $2$ con, ta lấy nút con (nếu có) của $x$ lên thay cho $x$ và hủy nút $x$.
* Nếu $x$ có cả hai con, xác định nút $y$ là nút cực phải của nhánh con trái, $y$ chắc chắn không có nhánh con phải, ta cắt rời $y$ khỏi cây bằng cách đưa nhánh con trái của nó (nếu có) vào thế chỗ $y$. Cuối cùng là cho nút $y$ thế chỗ nút $x$ trên cây và xóa nút $x$. Tất cả các thao tác được thực hiện trên con trỏ liên kết mà không động chạm vào khóa trong nút (Hình dưới).
:::
```cpp=1
void ers(bptr x){
bptr y;
if (x->l == nil || x->r == nil){ //x có ít hơn 2 con
y = x->l != nil ? x->l : x->r; //y = nút con của x nếu có
set_link(x->p, y, x->p->r == x); //Cho y thế chỗ x làm con của x->p
}
else //x có 2 con
{
y=max_bst(x->l); //y = nút cực phải của nhánh con trái
set_link(y->p, y->l, y->p->r == y); //Cho con trái y thế chỗ y, cắt y khỏi cây
//Cho y thế chỗ x
set_link(y, x->l, false); //y nhận con trái của x
set_link(y, x->r, true); //y nhận con phải của x
set_link(x->p, y, x->p->r == x); //y nhận cha của x
}
if (x == root) root = y;
delete x;
}
```
Vậy là ta đã đã build hoàn thành các thao tác chính của ```BST```.Đoạn template cho mọi người tham khảo:
:::spoiler
```cpp=1
struct bst {
struct node {
int key;
node* p;
node* l;
node* r;
};
using bptr=node*;
bptr root;
node nll;
bptr nil;
bst(){
nil=&nll;
root=nil;
}
void set_link(bptr parent, bptr child, bool is_r) {
child->p = parent;
if(is_r) parent->r = child;
else parent->l = child;
}
bptr create(int val) {
bptr newn = new node();
newn->key = val;
newn->p = nil;
newn->l = nil;
newn->r = nil;
return newn;
}
void ins(int k) {
bptr y = nil;
bptr x = root;
while(x != nil){
if(k == x->key) return;bst
y = x;
x = (k < x->key) ? x->l : x->r;
}
x = create(k);
set_link(y, x, k > y->key);
if(root == nil) root = x;
}
bptr max_bst(bptr x){
while(x->r!= nil ) x=x->r;
return x;
}
bptr min_bst(bptr x){
while(x->l!= nil ) x=x->l;
return x;
}
void ers(bptr x){
bptr y;
if (x->l == nil || x->r == nil){
y = x->l != nil ? x->l : x->r;
set_link(x->p, y, x->p->r == x);
}
else
{
y=max_bst(x->l);
set_link(y->p, y->l, y->p->r == y);
set_link(y, x->l, false);
set_link(y, x->r, true);
set_link(x->p, y, x->p->r == x);
}
if (x == root) root = y;
delete x;
}
bptr lower(bptr x){
if(x->l!=nil) return max_bst(x->l);
while(x->p!=nil && x->p->r!=x) x=x->p;
return x->p;
}
bptr upper(bptr x){
if(x->r!=nil) return min_bst(x->r);
while (x->p != nil && x->p->l != x)
x=x->p;
return x->p;
}
bptr _find(int k)
{
bptr x=root;
while(x!=nil&& x->key!=k) x=(k<x->key ? x->l :x->r);
return x;
}
void nlr(bptr x){
if(x==nil) return;
///......làm gì đó ở đây
nlr(x->l);
nlr(x->r);
}
void lnr(bptr x) {
if (x == nil) return;
lnr(x->l);
/// .......làm gì đó ở đây
lnr(x->r);
}
void rnl(bptr x){
if (x == nil) return;
rnl(x->r);
///........làm gì đó ở đây
rnl(x->l);
}
};
```
:::
## Cân bằng cây nhị phân
đang cập nhật :3
Sign in with Wallet
Connect another wallet