Cây nhị phân tìm kiếm

Tìm nhị phân nhanh nhưng cần array đã sắp xếp, mà chèn vào array thì phải dời chỗ, tốn O(n). Cây nhị phân tìm kiếm giữ dữ liệu luôn có thứ tự, vừa tìm vừa thêm đều nhanh.

Khái niệm

🎄 Cây nhị phân tìm kiếm (binary search tree, BST): mỗi node có tối đa hai con, mọi giá trị ở nhánh trái nhỏ hơn giá trị của node, mọi giá trị ở nhánh phải lớn hơn hoặc bằng giá trị của node.

Node trên cùng gọi là gốc, node không có con gọi là lá.

⛰️ Chiều cao cây: số node trên đường dài nhất từ gốc xuống lá, cũng là số bước tìm hoặc thêm trong trường hợp xấu nhất.

Cây cân đối cao khoảng log n, nên tìm và thêm là O(log n). Node ở đây giống node của linked list, chỉ khác là có hai tham chiếu Left, Right thay vì một Next.

Ví dụ

TreeNode? root = null;
int[] prices = { 7000, 3000, 12000, 5000, 25000 };
foreach (int price in prices)
{
    root = Insert(root, price);
}
PrintInOrder(root);   // 3000 5000 7000 12000 25000

TreeNode Insert(TreeNode? node, int value)
{
    if (node == null)
    {
        return new TreeNode(value);
    }
    if (value < node.Value)
    {
        node.Left = Insert(node.Left, value);
    }
    else
    {
        node.Right = Insert(node.Right, value);
    }
    return node;
}

void PrintInOrder(TreeNode? node)
{
    if (node == null)
    {
        return;
    }
    PrintInOrder(node.Left);
    Console.Write(node.Value + " ");
    PrintInOrder(node.Right);
}

class TreeNode
{
    public int Value { get; }
    public TreeNode? Left { get; set; }
    public TreeNode? Right { get; set; }

    public TreeNode(int value)
    {
        Value = value;
    }
}

Insert là đệ quy: nhỏ hơn thì đi trái, không thì đi phải, gặp chỗ trống (null) thì đặt node mới.
PrintInOrder in nhánh trái, rồi node, rồi nhánh phải, nên giá in ra luôn tăng dần.

▶ Mô phỏng: Thêm từng giá rồi in in-order

TreeNode? root = null;
int[] prices = { 7000, 3000, 12000, 5000, 25000 };
foreach (int price in prices)
{
    root = Insert(root, price);
}
PrintInOrder(root);

TreeNode Insert(TreeNode? node, int value)
{
    if (node == null)
    {
        return new TreeNode(value);
    }
    if (value < node.Value)
    {
        node.Left = Insert(node.Left, value);
    }
    else
    {
        node.Right = Insert(node.Right, value);
    }
    return node;
}

void PrintInOrder(TreeNode? node)
{
    if (node == null)
    {
        return;
    }
    PrintInOrder(node.Left);
    Console.Write(node.Value + " ");
    PrintInOrder(node.Right);
}

Xem từng bước

Cây đang rỗng: 7000 thành node gốc.
Thêm 3000: bắt đầu so từ gốc.
3000 nhỏ hơn 7000: chỉ có thể nằm ở nhánh trái.
Nhánh trái của 7000 đang trống (null): đặt 3000 ở đó. Không node nào phải dời chỗ.
Thêm 12000: bắt đầu so từ gốc.
12000 không nhỏ hơn 7000: đi sang nhánh phải.
Nhánh phải của 7000 đang trống (null): đặt 12000 ở đó. Không node nào phải dời chỗ.
Thêm 5000: bắt đầu so từ gốc.
5000 nhỏ hơn 7000: chỉ có thể nằm ở nhánh trái.
5000 không nhỏ hơn 3000: đi sang nhánh phải.
Nhánh phải của 3000 đang trống (null): đặt 5000 ở đó. Không node nào phải dời chỗ.
Thêm 25000: bắt đầu so từ gốc.
25000 không nhỏ hơn 7000: đi sang nhánh phải.
25000 không nhỏ hơn 12000: đi sang nhánh phải.
Nhánh phải của 12000 đang trống (null): đặt 25000 ở đó. Không node nào phải dời chỗ.
Duyệt in-order: với mỗi node, in nhánh trái, rồi node, rồi nhánh phải.
In-order: in hết nhánh trái của 3000 rồi mới in 3000, sau đó tới nhánh phải.
In-order: in hết nhánh trái của 5000 rồi mới in 5000, sau đó tới nhánh phải.
In-order: in hết nhánh trái của 7000 rồi mới in 7000, sau đó tới nhánh phải.
In-order: in hết nhánh trái của 12000 rồi mới in 12000, sau đó tới nhánh phải.
In-order: in hết nhánh trái của 25000 rồi mới in 25000, sau đó tới nhánh phải.
Giá in ra tăng dần. Cây cao 3 tầng: tìm một giá chỉ đi qua tối đa ngần ấy node. Thêm theo thứ tự tăng dần thì cây thành một đường thẳng.

.NET có SortedDictionary<TKey, TValue> và SortedSet<T>: bên trong là cây tự cân đối, nên luôn O(log n) và duyệt ra theo thứ tự key.

Thử ngay

Thêm method đo chiều cao, rồi so hai cây cùng 7 số nhưng thêm theo thứ tự khác nhau:

int[] ascending = { 1, 2, 3, 4, 5, 6, 7 };
int[] shuffled = { 4, 2, 6, 1, 3, 5, 7 };

TreeNode? sorted = null;
foreach (int x in ascending)
{
    sorted = Insert(sorted, x);
}
TreeNode? mixed = null;
foreach (int x in shuffled)
{
    mixed = Insert(mixed, x);
}
Console.WriteLine(Height(sorted));
Console.WriteLine(Height(mixed));

int Height(TreeNode? node)
{
    if (node == null)
    {
        return 0;
    }
    return 1 + Math.Max(
        Height(node.Left), Height(node.Right));
}

Math.Max trả về số lớn hơn trong hai số.

Đoán trước khi chạy: hai cây cao bao nhiêu?

Xem kết quả

7
3

Thêm theo thứ tự tăng dần, số nào cũng lớn hơn nên đi sang phải hết: cây thành một đường thẳng như linked list, tìm mất O(n). Thêm xen kẽ thì cây cân đối, chỉ cao 3.

Lỗi hay gặp

Tự viết BST rồi nạp dữ liệu đã sắp xếp. Dữ liệu lấy từ database hay file thường đã sắp xếp sẵn, nên cây lệch hẳn về một bên và mất hết ưu điểm.

// SAI — nạp giá đã sắp xếp: cây lệch thành O(n)
TreeNode? root = null;
int[] sortedPrices = { 3000, 5000, 7000 };
foreach (int price in sortedPrices)
{
    root = Insert(root, price);
}

// ĐÚNG — SortedSet tự cân đối, luôn O(log n)
var prices = new SortedSet<int> { 3000, 5000, 7000 };
Console.WriteLine(prices.Contains(5000));   // True

Tóm tắt

BST: trái nhỏ hơn, phải lớn hơn hoặc bằng. Duyệt trái, node, phải thì ra thứ tự tăng.
Tìm và thêm tốn số bước bằng chiều cao: cây cân đối là O(log n).
Nạp dữ liệu đã sắp xếp vào BST tự viết thì cây lệch thành O(n).
Dùng SortedDictionary, SortedSet của .NET: cây tự cân đối.

Khái niệm

Node trên cùng gọi là gốc, node không có con gọi là lá.

⛰️ Chiều cao cây: số node trên đường dài nhất từ gốc xuống lá, cũng là số bước tìm hoặc thêm trong trường hợp xấu nhất.

Cây cân đối cao khoảng log n, nên tìm và thêm là O(log n). Node ở đây giống node của linked list, chỉ khác là có hai tham chiếu Left, Right thay vì một Next.

Ví dụ

TreeNode? root = null;
int[] prices = { 7000, 3000, 12000, 5000, 25000 };
foreach (int price in prices)
{
    root = Insert(root, price);
}
PrintInOrder(root);   // 3000 5000 7000 12000 25000

TreeNode Insert(TreeNode? node, int value)
{
    if (node == null)
    {
        return new TreeNode(value);
    }
    if (value < node.Value)
    {
        node.Left = Insert(node.Left, value);
    }
    else
    {
        node.Right = Insert(node.Right, value);
    }
    return node;
}

void PrintInOrder(TreeNode? node)
{
    if (node == null)
    {
        return;
    }
    PrintInOrder(node.Left);
    Console.Write(node.Value + " ");
    PrintInOrder(node.Right);
}

class TreeNode
{
    public int Value { get; }
    public TreeNode? Left { get; set; }
    public TreeNode? Right { get; set; }

    public TreeNode(int value)
    {
        Value = value;
    }
}

Insert là đệ quy: nhỏ hơn thì đi trái, không thì đi phải, gặp chỗ trống (null) thì đặt node mới.
PrintInOrder in nhánh trái, rồi node, rồi nhánh phải, nên giá in ra luôn tăng dần.

▶ Mô phỏng: Thêm từng giá rồi in in-order

TreeNode? root = null;
int[] prices = { 7000, 3000, 12000, 5000, 25000 };
foreach (int price in prices)
{
    root = Insert(root, price);
}
PrintInOrder(root);

TreeNode Insert(TreeNode? node, int value)
{
    if (node == null)
    {
        return new TreeNode(value);
    }
    if (value < node.Value)
    {
        node.Left = Insert(node.Left, value);
    }
    else
    {
        node.Right = Insert(node.Right, value);
    }
    return node;
}

void PrintInOrder(TreeNode? node)
{
    if (node == null)
    {
        return;
    }
    PrintInOrder(node.Left);
    Console.Write(node.Value + " ");
    PrintInOrder(node.Right);
}

Xem từng bước

Cây đang rỗng: 7000 thành node gốc.
Thêm 3000: bắt đầu so từ gốc.
3000 nhỏ hơn 7000: chỉ có thể nằm ở nhánh trái.
Nhánh trái của 7000 đang trống (null): đặt 3000 ở đó. Không node nào phải dời chỗ.
Thêm 12000: bắt đầu so từ gốc.
12000 không nhỏ hơn 7000: đi sang nhánh phải.
Nhánh phải của 7000 đang trống (null): đặt 12000 ở đó. Không node nào phải dời chỗ.
Thêm 5000: bắt đầu so từ gốc.
5000 nhỏ hơn 7000: chỉ có thể nằm ở nhánh trái.
5000 không nhỏ hơn 3000: đi sang nhánh phải.
Nhánh phải của 3000 đang trống (null): đặt 5000 ở đó. Không node nào phải dời chỗ.
Thêm 25000: bắt đầu so từ gốc.
25000 không nhỏ hơn 7000: đi sang nhánh phải.
25000 không nhỏ hơn 12000: đi sang nhánh phải.
Nhánh phải của 12000 đang trống (null): đặt 25000 ở đó. Không node nào phải dời chỗ.
Duyệt in-order: với mỗi node, in nhánh trái, rồi node, rồi nhánh phải.
In-order: in hết nhánh trái của 3000 rồi mới in 3000, sau đó tới nhánh phải.
In-order: in hết nhánh trái của 5000 rồi mới in 5000, sau đó tới nhánh phải.
In-order: in hết nhánh trái của 7000 rồi mới in 7000, sau đó tới nhánh phải.
In-order: in hết nhánh trái của 12000 rồi mới in 12000, sau đó tới nhánh phải.
In-order: in hết nhánh trái của 25000 rồi mới in 25000, sau đó tới nhánh phải.
Giá in ra tăng dần. Cây cao 3 tầng: tìm một giá chỉ đi qua tối đa ngần ấy node. Thêm theo thứ tự tăng dần thì cây thành một đường thẳng.

.NET có SortedDictionary<TKey, TValue> và SortedSet<T>: bên trong là cây tự cân đối, nên luôn O(log n) và duyệt ra theo thứ tự key.

Thử ngay

Thêm method đo chiều cao, rồi so hai cây cùng 7 số nhưng thêm theo thứ tự khác nhau:

int[] ascending = { 1, 2, 3, 4, 5, 6, 7 };
int[] shuffled = { 4, 2, 6, 1, 3, 5, 7 };

TreeNode? sorted = null;
foreach (int x in ascending)
{
    sorted = Insert(sorted, x);
}
TreeNode? mixed = null;
foreach (int x in shuffled)
{
    mixed = Insert(mixed, x);
}
Console.WriteLine(Height(sorted));
Console.WriteLine(Height(mixed));

int Height(TreeNode? node)
{
    if (node == null)
    {
        return 0;
    }
    return 1 + Math.Max(
        Height(node.Left), Height(node.Right));
}

Math.Max trả về số lớn hơn trong hai số.

Đoán trước khi chạy: hai cây cao bao nhiêu?

Xem kết quả

7
3

Lỗi hay gặp

// SAI — nạp giá đã sắp xếp: cây lệch thành O(n)
TreeNode? root = null;
int[] sortedPrices = { 3000, 5000, 7000 };
foreach (int price in sortedPrices)
{
    root = Insert(root, price);
}

// ĐÚNG — SortedSet tự cân đối, luôn O(log n)
var prices = new SortedSet<int> { 3000, 5000, 7000 };
Console.WriteLine(prices.Contains(5000));   // True

Tóm tắt

BST: trái nhỏ hơn, phải lớn hơn hoặc bằng. Duyệt trái, node, phải thì ra thứ tự tăng.
Tìm và thêm tốn số bước bằng chiều cao: cây cân đối là O(log n).
Nạp dữ liệu đã sắp xếp vào BST tự viết thì cây lệch thành O(n).
Dùng SortedDictionary, SortedSet của .NET: cây tự cân đối.

Khái niệm

Ví dụ

Thử ngay

Lỗi hay gặp

Tóm tắt

Bình luận

Cây nhị phân tìm kiếm

Khái niệm

Ví dụ

Thử ngay

Lỗi hay gặp

Tóm tắt

Bình luận