Algorithm – Cài đặt Binary Search Tree bằng C#

Cây nhị phân tìm kiếm (Binary Search Tree – BST) là một cấu trúc dữ liệu phổ biến và là kiến thức không thể thiếu trong môn học Data Structures and Algorithms. BST có các ưu điểm là truy cập, tìm kiếm dữ liệu nhanh và cài đặt tương đối đơn giản.
Download Y2BinaryTree.cs

Download Y2 BSTreeDemo 1.0.0.rar

Giới thiệu

Mặc dù trong .Net cung cấp sẵn khá nhiều loại collection nhưng lại không có BST. Vì lý do đó và cũng làm tiền đề cho những bài hướng dẫn sau này nên tôi sẽ trình bày phương pháp cài đặt một BST cơ bản bằng C#. Kèm theo bài viết này tôi cũng viết một chương trình minh họa đơn giản để hiển thị và thực hiện các thao tác với BST trên giao diện đồ họa (GUI).

Các đặc điểm cơ bản của BST:

–               Mỗi node chỉ có tối đa hai node con

–               Node con bên trái luôn có giá trị nhỏ hơn node cha và node con bên phải có giá trị lớn hơn node cha.

–               Các node không có giá trị trùng nhau.

–               Độ sâu (depth) của một node là số node tạo thành đường đi tính từ gốc (root) đến node đó.

–               Chiều cao của cây (height) là số node tính từ gốc đến node có độ sâu lớn nhất.

–               Predecessor node là node có giá trị nhỏ hơn ngay sau node hiện tại (node lớn nhất ở cây con trái).

–               Successor node là node có giá trị lớn hơn kế tiếp của một node (node nhỏ nhất ở cây con phải).

BSTree

Cài đặt Node:

Việc đầu tiên là tạo lớp mô phỏng Node của cây. Node này phải có khả năng so sánh với các node khác thông qua thuộc tính khóa của nó và thuộc tính khóa phải có kiểu dữ liệu tùy chọn.

Để tiện lợi khi so sánh, bạn có thể overload hai toán tử < và > như trong mã nguồn bên dưới.

Y2BinaryTreeNode.cs:

class Y2BinaryTreeNode<T> : IComparable
   where T : IComparable
{

    #region Properties

    public T Value { get; set; }

    public Y2BinaryTreeNode<T> LeftChild { get; set; }
    public Y2BinaryTreeNode<T> RightChild { get; set; }
    public Y2BinaryTreeNode<T> Parent { get; set; }

    public bool IsLeaf
    {
        get { return LeftChild == null && RightChild == null; }
    }
    public bool HasLeftChild
    {
        get { return LeftChild != null; }
    }
    public bool HasRightChild
    {
        get { return RightChild != null; }
    }

    public override int GetHashCode()
    {
        return this.Value.GetHashCode();
    }
    #endregion

    public Y2BinaryTreeNode(T value)
    {
        this.Value = value;
    }

    #region IComparable Members

    public int CompareTo(object obj)
    {
        Y2BinaryTreeNode<T> node = obj as Y2BinaryTreeNode<T>;

        return this.Value.CompareTo(node.Value);
    }

    #endregion

    public static bool operator <(Y2BinaryTreeNode<T> node1, Y2BinaryTreeNode<T> node2)
    {
        return node1.Value.CompareTo(node2.Value) < 0;
    }
    public static bool operator >(Y2BinaryTreeNode<T> node1, Y2BinaryTreeNode<T> node2)
    {
        return node1.Value.CompareTo(node2.Value) > 0;
    }
}

Cài đặt Tree

Việc cài đặt cây yêu cầu bạn phải có một node gốc (Root) và thêm một số phương thức như thêm, xóa, tìm kiếm, duyệt, lấy chiều cao,… Trong phần này tôi chỉ hướng dẫn các thao tác cơ bản như chèn, xóa, tìm kiếm và duyệt cây,… còn một số thao tác khác như lấy chiều cao, tìm đường đi,… được cung cấp trong tập tin mã nguồn đính kèm.

Các thuộc tính của cây tôi sử dụng gồm có:

Root: node gốc của cây

Count: số node trong cây

Insertion

Việc thêm một node vào cây sử dụng đệ quy để gắn node vào cây con thích hợp. Tại mỗi node được duyệt đến, ta sẽ kiểm tra nếu giá trị cần thêm bằng với giá trị của node thì sẽ trả về false (node đã có trong cây). Ngược lại kiểm tra nếu node cần thêm có giá trị nhỏ hơn node hiện tại thì ta gọi đệ quy bên cây con trái, và nếu lớn hơn sẽ đệ quy bên nhánh phải.

private bool Add(Y2BinaryTreeNode<T> parentNode, Y2BinaryTreeNode<T> node)
{
    if (parentNode.Value.Equals(node.Value))
        return false;

    if (parentNode > node)
    {
        if (!parentNode.HasLeftChild)
        {
            parentNode.LeftChild = node;
            node.Parent = parentNode;
            Count++;
            return true;
        }
        else
           return Add(parentNode.LeftChild, node);
    }
    else
    {
        if (!parentNode.HasRightChild)
        {
            parentNode.RightChild = node;
            node.Parent = parentNode;
            Count++;
            return true;
        }
        else
           return Add(parentNode.RightChild, node);
    }            
}

Deletion


Việc xóa một node trên cây tương đối phức tạp vì phải chia ra ba trường hợp dựa vào số node con của node cần xóa. Cách xử lý với mỗi trường hợp được mô tả cơ bản như sau:

  • Không có node con (node lá): Chỉ cần xóa node khỏi cây.
  • Một node con: phải thay thế node hiện tại bằng node con của nó.
  • Hai node con: Chọn predecessor node hoặc successor node để thay thế cho node hiện tại.
BSTree_deletion

BSTree deletion

Phương thức xóa node được cài đặt như sau:

private bool Remove(Y2BinaryTreeNode<T> node, T value)
{
    if (node == null)
        return false;

    if (node.Value.Equals(value))
    {
        if (node.IsLeaf) // no children
        {
            if (node.Parent.LeftChild == node)
                node.Parent.LeftChild = null;
            else
                node.Parent.RightChild = null;

            node.Parent = null;
        }
        else if (node.HasLeftChild && node.HasRightChild)   // 2 children
        {
		// Tìm successor node
            Y2BinaryTreeNode<T> replacementNode = node.RightChild;

            while (replacementNode.HasLeftChild)
            {
                replacementNode = replacementNode.LeftChild;
            }
            node.Value = replacementNode.Value;

            Remove(replacementNode, replacementNode.Value);
        }
        else    // one child
        {
            Y2BinaryTreeNode<T> subNode;

            if (node.HasLeftChild)
                subNode = node.LeftChild;
            else
                subNode = node.RightChild;

            if (Root == (subNode))
                Root = subNode;

            subNode.Parent = node.Parent;

            if (node.Parent.LeftChild == node)
                node.Parent.LeftChild = subNode;
            else
                node.Parent.RightChild = subNode;
        }
        Count--;
        return true;
    }
    else
    {
        if (node.Value.CompareTo(value) > 0)
            return Remove(node.LeftChild, value);
        else
            return Remove(node.RightChild, value);
    }
}

Searching

Dựa vào đặc tính của cây nhị phân là các node bên trái có giá trị nhỏ hơn node cha và node bên phải lớn hơn node cha, thuật toán đệ quy (recursive) được áp dụng để tìm kiếm trên từng cây con dựa vào việc so sánh giá trị cần tìm với node đang xét. Ngoài ra, thay vì dùng đệ quy bạn có thể dùng cách lặp (Iteration)  thông thường để tìm kiếm. Mã nguồn của hai phiên bản đệ quy và lặp được cài đặt như dưới đây:

–               Iterative Searching

public virtual Y2BinaryTreeNode<T> Search(T value)
   {
        Y2BinaryTreeNode<T> node = this.Root;

        while (node != null)
        {
            if (node.Value.Equals(value))
                return node;
            else
            {
                if (node.Value.CompareTo(value) > 0)
                    node = node.LeftChild;
                else
                    node = node.RightChild;
            }
        }
        return null;
}

–               Recursive Searching

public virtual Y2BinaryTreeNode<T> Search(Y2BinaryTreeNode<T> node, T value)
{
    if (node == null)
        return null;

    if (node.Value.Equals(value))
        return node;
    else
    {
        if (node.Value.CompareTo(value) > 0)
            return Search(node.LeftChild,value);
        else
            return Search(node.RightChild,value);
    }
}

Traversal

Có 3 phương pháp cơ bản để duyệt qua các node của cây thao thứ tự của các node sẽ được duyệt. Bằng cách sử dụng đệ quy, ta chỉ quan tâm đến thứ tự duyệt của node đang và các node con của nó.

  • In-Order Traversal: node.LeftChild -> node -> node.RighChild
  • Pre-Order Traversal: node  -> node.LeftChild -> node.RighChild
  • Post-Order Traversal: node.LeftChild -> node.RighChild -> node

Vì các phương pháp trên sẽ duyệt node có độ sâu lớn nhất đầu tiên nên ba phương pháp trên được gọi chung là Depth-first Traversal. Bạn cũng có thể sử dụng kĩ thuật Iterative để duyệt cây bằng cách sử dụng Stack để lưu trữ các node từ root đến lá.

Các phương thức duyệt cây tương ứng được cài đặt bằng đệ quy như sau:

private void InOrderTraverse(Y2BinaryTreeNode<T> node)
{
    if (node == null)
        return;
    InOrderTraverse(node.LeftChild);
    _list.Add(node.Value);
    InOrderTraverse(node.RightChild);
}

private void PreOrderTraverse(Y2BinaryTreeNode<T> node)
{
    if (node == null)
        return;
    _list.Add(node.Value);
    PreOrderTraverse(node.LeftChild);
    PreOrderTraverse(node.RightChild);
}

private void PostOrderTraverse(Y2BinaryTreeNode<T> node)
{
    if (node == null)
        return;
    PostOrderTraverse(node.LeftChild);
    PostOrderTraverse(node.RightChild);
    _list.Add(node.Value);
}

Chương trình minh họa

Đây là chương trình tôi viết để minh họa về BST như đã nói ở trên. Vì được viết khá vội và chỉ để minh họa đơn giản nên tôi chưa chú trọng nhiều đến giao diện và hiệu suất thực thi, tuy nhiên chức năng cũng khá đầy đủ để bạn tham khảo.

Y2 BSTreeDemo 1.0

Y2 BSTreeDemo 1.0

–               Phần textbox màu đen phía dưới cửa sổ bạn có thể nhập các câu lệnh để thao tác với cây. Cách dùng các lệnh như sau (không phân biệt hoa thường):

Quy ước:

  • Tham số trong cặp {} là bắt buộc, tham số trong [] là tùy chọn.
  • Các tham số cách nhau bởi khoảng trắng hoặc dấu phẩy ’,’.

–               Tạo cây ngẫu nhiên:

Random {size} {min} {max}

Ex: random 10 1 100
Tạo cây có tối đa 10 node với các giá trị node ngẫu nhiên từ 1 đến 100. Vì hàm tạo không kiểm tra trùng nên số phần tử được thêm vào cây có thể ít hơn giá trị nhập vào.

–               Xóa toàn bộ node

Clear

–               Chèn node

Add {number1}, [number2], [number3] …

Ex:       add 10 6 8 9 20 3 11

add 10, 6, 8, 9, 20, 3

Sẽ chèn các node có các giá trị tương ứng theo thứ tự là 10, 6, 8, 9,…

–               Xóa node

Del {number}

Delete {number}

–               Tìm node

Find {number}

Search {number}

–               Duyệt cây

InOrder

PreOrder

PostOrder

–               Thoát chương trình

Exit

Xem chi tiết và download source code của chương trình tại đây.

https://yinyangit.wordpress.com

Advertisements

18 thoughts on “Algorithm – Cài đặt Binary Search Tree bằng C#

  1. Pingback: Algorithm – Tạo và sử dụng cây biểu thức (expression tree) « Nguyễn Ngọc Vạn's Blog

  2. Bạn ơi …………………..mình mới bắt đầu học C# đc vài ngày ………………..cũng chưa hiểu rõ lắm + phần mềm visual studio mình chưa thành thạo lắm ………….bạn có thể hướng daanxminhf cũng như mọi người chi tiết hơn về quá trình thiết kế form đc không /? tks bạn nhiều

    Phản hồi

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s