Binary Search Tree Là Gì | Liên Kết Ngoài[Sửa | Sửa Mã Nguồn]

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

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 dùng khá phổ biến và có 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 ngôn ngữ C/C++ nhé.

NỘI DUNG BÀI VIẾT

Mã giả bằng ngôn ngữ C[sửa | sửa mã nguồn]

#include

#include

#include

//Khai bao cay nhi phan typedef char TData; typedef struct TNode{ TData Data; TNode* left; TNode* right; }; typedef TNode* TTree; /*=== Tao cay rong ===*/ void MakeNull_Tree(TTree *T) { (*T)=NULL; } /*=== Kiem tra cay rong ===*/ int EmptyTree(TTree T) { return T==NULL; } /*=== Xac dinh con trai ===*/ TTree LeftChild(TTree T) { if(T != NULL) return T->left; else return NULL; } /*=== Xac dinh con phai ===*/ TTree RightChild(TTree T) { if(T != NULL) return T->right; else return NULL; } /*=== Xac dinh nut la ===*/ int isLeaf(TTree T) { if((T != NULL) && (T->left == NULL) && (T->right == NULL)) return 1; else return NULL; } /*=== Xac dinh so nut cua cay ===*/ int nb_nodes(TTree T) { if(EmptyTree(T)) return 0; else return nb_nodes(T->left)+nb_nodes(T->right)+1; } // Ham xac dinh gia tri lon nhat trong hai so nguyen int max(int value1,int value2) { return ((value1 > value2) ? value1: value2); //xac dinh gia tri lon nhat trong 2 gia tri so nguyen } // Ham xac dinh chieu cao cua cay int TreeHeight(TTree T) { int height=0; if (!EmptyTree(T)) { if (isLeaf(T)) return 0; else height = max(TreeHeight(LeftChild(T)),TreeHeight(RightChild(T)))+1; } return height; } // Ham xac dinh so nut la tren cay int nb_leaf(TTree T) { int leaf=0; if(!EmptyTree(T)) { if (isLeaf(T)) leaf++; else leaf = nb_leaf(LeftChild(T))+nb_leaf(RightChild(T)); }; return leaf; } /*=== Tao cay moi tu hai cay co san ===*/ TTree Create2(TData v,TTree left,TTree right) { TTree N; // Khai bao 1 cay moi N = (TNode*)malloc(sizeof(TNode)); //Cap phat vung nho cho nut N N->Data = v; // Nhan cua nut N la v N->left = left; //Con trai cua N la cay left N->right = right; //Con phai cua N la cay right return N; } /*=== Duyet cay nhi phan ===*/ //Duyet tien tu void NLR(TTree T) { if(!EmptyTree(T)) { printf(” %c”,T->Data); //Xu ly nut NLR(LeftChild(T)); //Duyet tien tu con trai NLR(RightChild(T)); //Duyet tien tu con phai } } //Duyet trung tu void LNR(TTree T) { if(!EmptyTree(T)) { LNR(LeftChild(T)); //Duyet trung tu con trai printf(” %c”,T->Data);//Xu ly nut LNR(RightChild(T));//Duyet trung tu con phai } } //Duyet hau tu void LRN(TTree T) { if(!EmptyTree(T)) { LRN(LeftChild(T)); //Duyet hau tu con trai LRN(RightChild(T));//Duyet hau tu con phai printf(” %c”,T->Data);//Xu ly nut } }

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à có thêm các ràng buộc sau đây:

1. Giá trị của tất cả các Node ở cây con bên trái phải <= giá trị của Node gốc.
2. Giá trị của tất cả các Node ở cây con bên phải phải > giá trị của Node gốc.
3. Tất cả các cây con(bao gồm bên trái và phải) cũng đều phải đảm bảo 2 tính chất trên.

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ỉ có tối đa hai con
• Nó được gọi là cây tìm kiếm nhị phân vì nó có thể được sử dụng để tìm kiếm sự hiện diện của một phần tử trong thời gian O(log (n)).

Định nghĩa[sửa | sửa mã nguồn]

Cây tìm kiếm ứng với n khóa là cây nhị phân mà mỗi nút đều được gán một khóa sao cho với mỗi mỗi nút k:

• Mọi khóa trên cây con trái đều nhỏ hơn khóa trên nút k
• Mọi khóa trên cây con phải đều lớn hơn khóa trên nút k

Cây tìm kiếm nhị phân là một cấu trúc dữ liệu cơ bản được sử dụng để xây dựng các cấu trúc dữ liệu trừu tượng hơn như các tập hợp, đa tập hợp, các dãy kết hợp.

Nếu một BST có chứa các giá trị giống nhau thì nó biểu diễn một đa tập hợp. Cây loại này sử dụng các bất đẳng thức không nghiêm ngặt. Mọi nút trong cây con trái có khóa nhỏ hơn khóa của nút cha, mọi nút trên cây con phải có nút lớn hơn hoặc bằng khóa của nút cha.

Nếu một BST không chứa các giá trị giống nhau thì nó biểu diễn một tập hợp đơn trị như trong lý thuyết tập hợp. Cây loại này sử dụng các bất đẳng thức nghiêm ngặt. Mọi nút trong cây con trái có khóa nhỏ hơn khóa của nút cha, mọi nút trên cây con phải có khóa lớn hơn khóa của nút cha.

Việc chọn đưa các giá trị bằng nhau vào cây con phải (hay trái) là tùy theo mỗi người. Một số người cũng đưa các giá trị bằng nhau vào cả hai phía, nhưng khi đó việc tìm kiếm trở nên phức tạp hơn.

Binary Search Tree: Điểm khởi đầu hoàn hảo

Một trong những cách chính để đánh giá chuyên môn của một kỹ sư là thông qua kiến thức và ứng dụng của họ về cấu trúc dữ liệu. Cấu trúc dữ liệu rất hữu ích và có thể giúp tạo ra một hệ thống hiệu quả hơn. Binary Search Tree là một khởi điểm tuyệt vời cho bất kỳ nhà phát triển nào để làm quen với cấu trúc dữ liệu.

Dịch từ: https://www.makeuseof.com/what-is-a-binary-search-tree/

>>> Nếu bạn đang có nhu cầu tìm hiểu về khóa học lập trình đi làm ngay. Hãy liên hệ với FUNiX ngay tại đây:

>>> Xem thêm chuỗi bài viết liên quan:

Ứng dụng học máy trong phân tích dữ liệu

5 công cụ phần mềm phân tích dữ liệu

Phân tích dữ liệu kinh doanh là làm gì năm 2022

Data analyst là gì? Tất cả những gì cần biết về nghề phân tích dữ liệu Data analyst

Vân Nguyễn

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

Cây tìm kiếm nhị phân (viết tắt tiếng Anh: BST – Binary Search Tree) là một cấu trúc dữ liệu rất thuận lợi cho bài toán tìm kiếm. Mỗi cây tìm kiếm nhị phân đều có tính chất sau: Với mỗi nút , các nút ở cây con bên trái của đều có giá trị key nhỏ hơn : , còn các nút ở cây con bên phải của đều có key lớn hơn hoặc bằng : .

Bài tập thực hành

• 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/

Một cây tìm kiếm nhị phân (Binary Search Tree – viết tắt là BST) là một cây mà trong đó tất cả các nút đều có các đặc điểm sau:

Vì thế có thể nói rằng, một cây tìm kiếm nhị phân (BST) phân chia tất cả các cây con của nó thành hai phần: cây con bên trái và cây con bên phải và có thể được định nghĩa như sau:


left_subtree (keys) node (key) right_subtree (keys)


Cây tìm kiếm nhị phân (BST) là một tập hợp bao gồm các nút được sắp xếp theo cách để chúng có thể duy trì hoặc tuân theo các đặc điểm của cây tìm kiếm nhị phân. Mỗi một nút thì đều có một khóa và giá trị liên kết với nó. Trong khi tìm kiếm, khóa cần tìm được so sánh với các khóa trong cây tìm kiếm nhị phân (BST) và nếu tìm thấy, giá trị liên kết sẽ được thu nhận.

Ví dụ một cây tìm kiếm nhị phân (BST):

Từ hình ví dụ minh họa trên ta thấy rằng, khóa của nút gốc có giá trị 27 và tất cả khóa bên trái của cây con bên trái đều có giá trị nhỏ hơn 27 này và tất cả các khóa bên phải của cây con bên phải đều có giá trị lớn hơn 27.

Dưới đây là một số hoạt động cơ bản có thể được thực hiện trên cây tìm kiếm nhị phân:

Một nút có một vài dữ liệu, tham chiếu tới các nút con bên trái và nút con bên phải của nó.


struct node { int data; struct node *leftChild; struct node *rightChild; };


Mỗi khi một phần tử được tìm kiếm: bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu là nhỏ hơn giá trị khóa (key), thì sẽ tìm phần tử ở cây con bên trái; nếu lớn hơn thì sẽ tìm phần tử ở cây con bên phải. Dưới đây là giải thuật cho mỗi nút:


struct node* search(int data){ struct node *current = root; printf("Truy cap cac phan tu: "); while(current->data != data){ if(current != NULL) { printf("%d ",current->data); //tới cây con bên trái if(current->data > data){ current = current->leftChild; }//else tới cây con bên phải else { current = current->rightChild; } //không tìm thấy if(current == NULL){ return NULL; } } } return current; }


Mỗi khi một phần tử được chèn: đầu tiên chúng ta cần xác định vị trí chính xác của phần tử này. Bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu là nhỏ hơn giá trị khóa (key), thì tìm kiếm vị trí còn trống ở cây con bên trái và chèn dữ liệu vào đó; nếu dữ liệu là nhỏ hơn thì tìm kiếm vị trí còn sống ở cây con bên phải và chèn dữ liệu vào đó.


void insert(int data){ struct node *tempNode = (struct node*) malloc(sizeof(struct node)); struct node *current; struct node *parent; tempNode->data = data; tempNode->leftChild = NULL; tempNode->rightChild = NULL; //Nếu cây là trống if(root == NULL){ root = tempNode; }else { current = root; parent = NULL; while(1){ parent = current; //tới cây con bên trái if(data < parent->data){ current = current->leftChild; //chèn dữ liệu vào cây con bên trái if(current == NULL){ parent->leftChild = tempNode; return; } }//tới cây con bên phải else{ current = current->rightChild; //chèn dữ liệu vào cây con bên phải if(current == NULL){ parent->rightChild = tempNode; return; } } } } }


Viết câu trả lời

Các bạn đã chán với thuật toán chưa? Học thuật toán hay mà ^^. Nối tiếp series thuật toán chuyên sâu này, chúng ta sẽ tiếp tục thảo luận về một thuật toán vô cùng phổ biến, nghe tên là bạn thấy quen liền. Đó là thuật toán tìm kiếm nhị phân hay Binary Search Tree.

Chúng ta sẽ triển khai các chức năng của thuật toán để tìm kiếm, chèn và xóa các giá trị từ một cây nhị phân. Vẫn là hai phương pháp để bạn tiếp cận và thực hiện thuật toán là: sử dụng vòng lặp và đệ quy.

Nội dung chính của bài viết

Tham khảo[sửa | sửa mã nguồn]

Trích dẫn[sửa | sửa mã nguồn]

1. ^ Rowan Garnier; John Taylor (2009). Discrete Mathematics: Proofs, Structures and Applications, Third Edition. CRC Press. tr. 620. ISBN 978-1-4398-1280-8.
2. ^ Steven S Skiena (2009). The Algorithm Design Manual. Springer Science & Business Media. tr. 77. ISBN 978-1-84800-070-4.
3. ^ a b Knuth (1997). The Art Of Computer Programming, Volume 1, 3/E. Pearson Education. tr. 363. ISBN 0-201-89683-4.
4. ^ Iván Flores (1971). Computer programming system/360. Prentice-Hall. tr. 39.
5. ^ Kenneth Rosen (2011). Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. tr. 749. ISBN 978-0-07-338309-5.
6. ^ David R. Mazur (2010). Combinatorics: A Guided Tour. Mathematical Association of America. tr. 246. ISBN 978-0-88385-762-5.
7. ^ Tamassia, Michael T. Goodrich, Roberto (2011). Algorithm design : foundations, analysis, and Internet examples (ấn bản 2). New Delhi: Wiley-India. tr. 76. ISBN 978-81-265-0986-7.
8. ^ “cây nhị phân đầy đủ”. NIST.
9. ^ Richard Stanley, Enumerative Combinatorics, volume 2, p.36
10. ^ Kenneth Rosen (2011). Discrete Mathematics and Its Applications 7th edition. McGraw-Hill Science. tr. 352–353. ISBN 978-0-07-338309-5.
11. ^ “cây nhị phân hoàn hảo”. NIST.
12. ^ a b “cây nhị phân hoàn chỉnh”. NIST.
13. ^ “cây nhị phân gần như hoàn chỉnh”. Bản gốc lưu trữ ngày 4 tháng 3 năm 2016. Truy cập ngày 11 tháng 12 năm 2015.
14. ^ “cây nhị phân hầu như hoàn chỉnh” (PDF). Lưu trữ (PDF) bản gốc ngày 9 tháng 10 năm 2022.
15. ^ Aaron M. Tenenbaum, et al. Data Structures Using C, Prentice Hall, 1990 ISBN 0-13-199746-7
16. ^ Paul E. Black (ed.), mục cấu trúc dữ liệu trong Dictionary of Algorithms and Data Structures. Viện National Institute of Standards and Technology của Mỹ. 15 tháng 12 năm 2004. Phiên bản trực tuyến Lưu trữ tháng 12 21, 2010 tại Wayback Machine Truy cập ngày 2010-12-19.
17. ^ Parmar, Anand K. (22 tháng 1 năm 2020). “Các loại cây nhị phân với minh họa đầy màu sắc”. Medium (bằng tiếng Anh). Truy cập ngày 24 tháng 1 năm 2020.

Thư mục[sửa | sửa mã nguồn]

• Donald Knuth. The Art of Computer Programming vol 1. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.3, especially subsections 2.3.1–2.3.2 (pp. 318–348).

Liên kết ngoài[sửa | sửa mã nguồn]

• [1] Lưu trữ 2009-03-20 tại Wayback Machine
• Full source code to an efficient implementation in C++ Lưu trữ 2010-03-28 tại Wayback Machine
• Implementation of Binary Search Trees in C
• Implementation of a Persistent Binary Search Tree in C
• Implementation of Binary Search Trees in Java Lưu trữ 2010-03-09 tại Wayback Machine
• Iterative Implementation of Binary Search Trees in C# Lưu trữ 2008-06-13 tại Wayback Machine
• An introduction to binary trees from Stanford
• Dictionary of Algorithms and Data Structures – Binary Search Tree
• Binary Search Tree Example in Python
• Java Model illustrating the behaviour of binary search trees(In JAVA Applet) Lưu trữ 2005-08-01 tại Wayback Machine
• Interactive Data Structure Visualizations – Binary Tree Traversals Lưu trữ 2014-02-27 tại Wayback Machine
• Literate implementations of binary search trees in various languages Lưu trữ 2017-04-21 tại Wayback Machine on LiteratePrograms
• BST Tree Applet by Kubo Kovac
• Well-illustrated explanation of binary search tree. Implementations in Java and C++

Chương 6: TREES – 7.Cây tìm kiếm nhị phân(Binary Search Trees – BSTs)

Tại sao cần Binary Search Trees?

Trong các phần trước, chúng ta đã thảo luận về các cách biểu diễn cây khác nhau và trong tất cả chúng, chúng ta không áp đặt bất kỳ hạn chế nào đối với dữ liệu trong node. Do đó, để tìm kiếm một phần tử, chúng ta cần kiểm tra cả cây con bên trái và cây con bên phải. Do đó, độ phức tạp trong trường hợp xấu nhất của thao tác tìm kiếm là O(n).

Trong phần này, chúng ta sẽ thảo luận về một biến thể khác của cây nhị phân: Cây tìm kiếm nhị phân (BST). Như tên gợi ý, công dụng chính của biểu diễn này là để tìm kiếm. Trong biểu diễn này, chúng ta áp đặt hạn chế đối với loại dữ liệu mà một node có thể chứa. Trong biểu diễn này, chúng ta áp đặt hạn chế đối với loại dữ liệu mà một node có thể chứa. Kết quả là, nó giảm thao tác tìm kiếm trung bình trong trường hợp xấu nhất xuống O(logn).

Các tính chất của Binary Search Trees

Trong cây tìm kiếm nhị phân, tất cả các phần tử của cây con bên trái phải nhỏ hơn dữ liệu gốc và tất cả các phần tử của cây con bên phải phải lớn hơn dữ liệu gốc. Đây được gọi là thuộc tính cây tìm kiếm nhị phân. Lưu ý rằng, thuộc tính này phải được thỏa mãn tại mọi node trong cây.

• Cây con bên trái của một node chỉ chứa các node có data nhỏ hơn node.
• Cây con bên phải của một node chỉ chứa các node có data lớn hơn node.
• Cả cây con bên trái và bên phải cũng phải là cây tìm kiếm nhị phân.

Ví dụ: Cây bên trái là cây tìm kiếm nhị phân và cây bên phải không phải là cây tìm kiếm nhị phân (tại node 6, nó không thỏa mãn thuộc tính của cây tìm kiếm nhị phân).

Khai báo cây tìm kiếm nhị phân

Không có sự khác biệt giữa khai báo cây nhị phân thông thường và khai báo cây nhị phân tìm kiếm. Sự khác biệt chỉ ở dữ liệu chứ không phải ở cấu trúc. Nhưng để thuận tiện, chúng ta đổi tên cấu trúc thành:


public class BinarySearchTreeNode { private int data; private BinarySearchTreeNode left; private BinarySearchTreeNode right; public int getData() { return data; } public void setData(int data) { this.data = data; } public BinarySearchTreeNode getLeft() { return left; } public void setLeft(BinarySearchTreeNode left) { this.left = left; } public BinarySearchTreeNode getRight() { return right; } public void setRight(BinarySearchTreeNode right) { this.right = right; } }


Thao tác trên cây tìm kiếm nhị phân

Các thao tác chính Các hoạt động chính được hỗ trợ bởi cây tìm kiếm nhị phân:

• Tìm/Tìm tối thiểu/Tìm tối đa trong cây tìm kiếm nhị phân
• Chèn một phần tử vào cây tìm kiếm nhị phân
• Xóa một phần tử khỏi cây tìm kiếm nhị phân

Hoạt động phụ trợ

• Kiểm tra xem cây đã cho có phải là cây tìm kiếm nhị phân hay không
• Tìm phần tử nhỏ thứ k trong cây
• Sắp xếp các phần tử của cây tìm kiếm nhị phân và nhiều hơn nữa

Notes về cây tìm kiếm nhị phân

• Vì dữ liệu gốc luôn nằm giữa dữ liệu cây con bên trái và dữ liệu cây con bên phải, nên việc thực hiện duyệt theo inorder traversal cây tìm kiếm nhị phân sẽ tạo ra một danh sách được sắp xếp.
• Trong khi giải các bài toán trên cây tìm kiếm nhị phân, đầu tiên chúng ta xử lý cây con bên trái, sau đó dữ liệu gốc và cuối cùng chúng ta xử lý cây con bên phải. Điều này có nghĩa là, tùy thuộc vào vấn đề, chỉ có bước trung gian (xử lý dữ liệu gốc) thay đổi và chúng ta không chạm vào bước đầu tiên và bước thứ ba.
• Nếu chúng ta đang tìm kiếm một phần tử và nếu dữ liệu gốc của cây con bên trái nhỏ hơn phần tử mà chúng ta muốn tìm kiếm thì hãy bỏ qua nó. Điều tương tự cũng xảy ra với cây con bên phải. Do đó, cây nhị phân tìm kiếm mất ít thời gian hơn để tìm kiếm một phần tử so với cây nhị phân thông thường. Nói cách khác, cây tìm kiếm nhị phân xem xét các cây con bên trái hoặc bên phải để tìm kiếm một phần tử chứ không phải cả hai.
• Các thao tác cơ bản có thể được thực hiện trên cây tìm kiếm nhị phân (BST) là chèn phần tử, xóa phần tử và tìm kiếm phần tử. Trong khi thực hiện các thao tác này trên BST, chiều cao của cây sẽ thay đổi mỗi lần. Do đó tồn tại các biến thể về độ phức tạp thời gian của trường hợp tốt nhất, trường hợp trung bình và trường hợp xấu nhất.
• Các hoạt động cơ bản trên cây tìm kiếm nhị phân mất thời gian tỷ lệ thuận với chiều cao của cây. Đối với một cây nhị phân hoàn chỉnh với n node, các hoạt động như vậy chạy trong trường hợp xấu nhất là O(lgn). Tuy nhiên, nếu cây là một chuỗi tuyến tính gồm n node (cây xiên), thì các thao tác tương tự sẽ mất O(n) thời gian trong trường hợp xấu nhất.

Tìm phần tử trong cây tìm kiếm nhị phân

Thao tác tìm rất đơn giản trong BST. Bắt đầu với thư mục gốc và tiếp tục di chuyển sang trái hoặc phải bằng thuộc tính của BST. Nếu dữ liệu chúng ta đang tìm kiếm giống với dữ liệu node thì chúng ta trả về node hiện tại. Nếu dữ liệu chúng ta đang tìm kiếm nhỏ hơn dữ liệu node thì tìm kiếm cây con bên trái của node hiện tại; mặt khác tìm kiếm cây con bên phải của node hiện tại. Nếu không có dữ liệu, chúng ta sẽ return null link.


public BinarySearchTreeNode find(BinarySearchTreeNode root, int data){ if(root == null){ return null; } if(data < root.getData()){ return find(root.getLeft(), data); } else if (data > root.getData()) { return find(root.getRight(), data); } return root; }


Time Complexity: O(n), trong trường hợp xấu nhất (khi cây tìm kiếm nhị phân đã cho là cây nghiêng). Space Complexity: O(n), dành cho ngăn xếp đệ quy.

Phiên bản non recursive của thuật toán trên có thể là:


public BinarySearchTreeNode find(BinarySearchTreeNode root, int data) { if(root == null){ return null; } while(root != null){ if(data == root.getData()){ return root; } else if (data > root.getData()) { root = root.getRight(); } else { root = root.getLeft(); } } return null; }


Time Complexity: O(n). Space Complexity: O(1).

Tìm phần tử nhỏ nhất trong cây tìm kiếm nhị phân

Trong các BST, phần tử nhỏ nhất là node ngoài cùng bên trái mà không có node con bên trái. Trong BST bên dưới, phần tử tối thiểu là 4.


public BinarySearchTreeNode findMin(BinarySearchTreeNode root){ if(root == null){ return null; } else{ if(root.getLeft() == null){ return root; } else{ return findMin(root.getLeft()); } } }


Time Complexity: O(n), trong trường hợp xấu nhất (khi BST là cây lệch trái). Space Complexity: O(n), đối với ngăn xếp đệ quy.

Phiên bản non recursive của thuật toán trên có thể là:


public BinarySearchTreeNode findMin(BinarySearchTreeNode root) { if (root == null) { return null; } while(root.getLeft() != null){ root = root.getLeft(); } return root; }


Time Complexity: O(n). Space Complexity: O(1).

Tìm phần tử lớn nhất trong cây tìm kiếm nhị phân

Trong các BST, phần tử lớn nhất là node ngoài cùng bên phải, không có node con bên phải. Trong BST bên dưới, phần tử tối đa là 16.


public BinarySearchTreeNode findMax(BinarySearchTreeNode root){ if(root == null){ return null; } else{ if(root.getRight() == null){ return root; } else{ return findMax(root.getRight()); } } }


Time Complexity: O(n), trong trường hợp xấu nhất (khi BST là cây lệch trái). Space Complexity: O(n), đối với ngăn xếp đệ quy.

Phiên bản non recursive của thuật toán trên có thể là:


public BinarySearchTreeNode findMax(BinarySearchTreeNode root) { if (root == null) { return null; } while(root.getRight() != null){ root = root.getRight(); } return root; }


Time Complexity: O(n). Space Complexity: O(1).

Inorder Predecessor và Successor ở đâu?

Đâu là Inorder Predecessor(tiền nhiệm) và Successor(kế nhiệm) của node X trong cây tìm kiếm nhị phân giả sử tất cả các node là khác nhau?\

Nếu X có hai node con thì inorder predecessor của nó là giá trị lớn nhất trong cây con bên trái của nó và giá trị kế tiếp thứ tự của nó là giá trị nhỏ nhất trong cây con bên phải của nó.

Nếu nó không có con bên trái, thì node inorder predecessor là tổ tiên bên trái đầu tiên của nó.

Chèn một phần tử từ cây tìm kiếm nhị phân

Để chèn dữ liệu vào cây tìm kiếm nhị phân, trước tiên chúng ta cần tìm vị trí cho phần tử đó. Chúng ta có thể tìm vị trí chèn bằng cách làm theo cơ chế tương tự như cơ chế của thao tác tìm. Trong khi tìm vị trí, nếu dữ liệu đã có ở đó thì chúng ta chỉ cần bỏ qua và đi ra. Nếu không, hãy chèn dữ liệu vào vị trí cuối cùng trên đường dẫn đi qua.

Như một ví dụ, chúng ta hãy xem xét cây sau đây. node chấm chấm cho biết phần tử (5) sẽ được chèn vào. node có các gạch đứt cho biết phần tử (5) sẽ được chèn vào. Để chèn 5, duyệt qua cây bằng chức năng tìm. Tại node có giá trị 4, chúng ta cần đi sang phải, nhưng không có cây con, vì vậy 5 không có trong cây và đây là vị trí chính xác để chèn.


public BinarySearchTreeNode insert(BinarySearchTreeNode root, int data){ if(root == null){ root = new BinarySearchTreeNode(); if(root == null){ System.out.println("Memory error"); return null; } else{ root.setData(data); root.setLeft(null); root.setRight(null); } } else { if(data < root.getData()){ root.setLeft(insert(root.getLeft(), data)); } else if (data > root.getData()) { root.setRight(insert(root.getRight(), data)); } } return root; }


Lưu ý: Trong đoạn mã trên, sau khi chèn một phần tử vào cây con, cây được trả về node cha của nó. Time Complexity: O(n). Space Complexity: O(n), cho ngăn xếp đệ quy. Nếu sử dụng vòng lặp, space complexity là O(1).

Xóa một phần tử khỏi cây tìm kiếm nhị phân

Thao tác xóa phức tạp hơn các thao tác khác. Điều này là do phần tử bị xóa có thể không phải là node lá. Trong thao tác này cũng vậy, trước tiên chúng ta cần tìm vị trí của phần tử mà chúng ta muốn xóa. Khi chúng ta đã tìm thấy node bị xóa, hãy xem xét các trường hợp sau:

• Nếu phần tử cần xóa là node lá: trả lại NULL cho cha mẹ của nó. Điều đó có nghĩa là tạo con trỏ con tương ứng NULL. Trong cây bên dưới để xóa 5, đặt NULL thành node cha của nó là 2.

• Nếu phần tử bị xóa có một node con: Trong trường hợp này, chúng ta chỉ cần link node con của node hiện tại cho node cha của nó. Trong cây bên dưới, để xóa 4, cây con bên trái 4 được đặt thành node cha của nó là 2.

• Nếu phần tử bị xóa có cả hai phần tử con: Chiến lược chung là thay thế giá trị của node này bằng phần tử lớn nhất của cây con bên trái và xóa node đó đi. node lớn nhất trong cây con bên trái không thể có node con bên phải, vì vậy thao tác xóa thứ hai là dễ dàng. Ví dụ, chúng ta hãy xem xét cây sau đây. Trong cây dưới đây, để xóa 8, nó là con bên phải của gốc. Giá trị chính là 8. Nó được thay thế bằng giá trị lớn nhất trong cây con bên trái của nó (7), và sau đó node đó bị xóa như trước (trường hợp thứ hai).

Lưu ý: Chúng ta cũng có thể thay thế bằng phần tử tối thiểu trong cây con bên phải.


public BinarySearchTreeNode delete(BinarySearchTreeNode root, int data){ BinarySearchTreeNode temp; if(root == null){ System.out.println("Element not there in tree"); } else if (data < root.getData()) { root.setLeft(delete(root.getLeft(), data)); } else if (data > root.getData()) { root.setRight(delete(root.getRight(), data)); } else{ // Found element if(root.getLeft() != null && root.getRight() != null){ // Replace with largest in left subtree temp = findMax(root.getLeft()); root.setData(temp.getData()); root.setLeft(delete(root.getLeft(), root.getData())); } else{ //One child if(root.getLeft() == null){ root = root.getRight(); } if(root.getRight() == null){ root = root.getLeft(); } } } return root; }


Time Complexity: O(n). Space Complexity: O(n), cho ngăn xếp đệ quy. Nếu sử dụng vòng lặp, space complexity là O(1).

All rights reserved

Chương 6: TREES -Tree là gì? Lý thuyết về Binary Tree.

Tham khảo[sửa | sửa mã nguồn]

• Donald Knuth. The Art of Compter Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.2.2: Binary Tree Searching, pp. 426–458.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 12: Binary search trees, pp. 253–272. Section 15.5: Optimal binary search trees, pp. 356–363.

Các hoạt động cơ bản của cây tìm kiếm nhị phân

Bây giờ bạn đã hiểu rõ hơn về định nghĩa Binary Search Tree, hãy cùng xem xét các operation (hoạt động) cơ bản của nó.

2.1 Search (Tìm kiếm)

Tìm kiếm cho phép xác định một giá trị cụ thể có trong cây. Chúng ta có thể sử dụng hai loại tìm kiếm: tìm kiếm theo chiều rộng (breadth-first search, hay BFS) và tìm kiếm theo chiều sâu (depth-first search, hay DFS). Tìm kiếm theo chiều rộng là một thuật toán tìm kiếm bắt đầu từ nút gốc và di chuyển theo chiều ngang, từ bên này sang bên kia, cho đến khi tìm thấy mục tiêu. Mỗi nút được truy cập một lần trong quá trình tìm kiếm này.

Mặt khác, tìm kiếm theo chiều sâu đi qua cây theo chiều dọc – bắt đầu từ nút gốc và đi dọc xuống một nhánh duy nhất. Nếu mục tiêu được tìm thấy, operation kết thúc. Nhưng nếu không, nó sẽ tìm kiếm các nút khác.

2.2 Insert (Chèn)

Thao tác chèn sử dụng thao tác tìm kiếm để xác định vị trí nơi nút mới sẽ được chèn. Quá trình này bắt đầu từ nút gốc và quá trình tìm kiếm bắt đầu cho đến khi đến đích. Có ba trường hợp cần xem xét:.

• Trường hợp 1: Khi không có nút nào tồn tại. Nút được chèn vào sẽ trở thành nút gốc.

• Trường hợp 2: Không có con. Trong trường hợp này, nút được chèn sẽ được so sánh với nút gốc. Nếu nó lớn hơn, nó sẽ trở thành nút con bên phải; nếu không, nó sẽ trở thành nút con trái.

• Trường hợp 3: Khi có cả nút gốc và con của nó. Nút mới sẽ được so sánh với mỗi nút trên đường dẫn của nó để xác định nút nào nó sẽ truy cập tiếp theo. Nếu nút này lớn hơn nút gốc, nó sẽ đi qua cây con bên phải, nếu không thì bên trái. Tương tự, so sánh được thực hiện ở mỗi cấp độ để xác định xem nó sẽ đi sang phải hay sang trái cho đến khi đến đích.

2.3 Delete (Xóa)

Thao tác xóa được sử dụng để xóa một nút cụ thể trong cây. Việc này khá phức tạp vì sau khi xóa một nút, cây phải được tổ chức lại cho phù hợp. Có ba trường hợp chính cần xem xét:

• Trường hợp 1: Xóa một nút lá (leaf node). Nút lá là nút không có nút con nào. Đây là nút dễ nhất để loại bỏ vì nó không ảnh hưởng đến bất kỳ nút nào khác; chúng ta chỉ cần đi dọc cây cho đến khi đến vị trí của nó và xóa nó đi.

• Trường hợp 2: Xóa một nút cha có một nút con. Việc này sẽ dẫn đến việc nút con chiếm vị trí của nó và tất cả các nút tiếp theo sẽ tăng lên một cấp. Sẽ không có thay đổi về cấu trúc cây con.

• Trường hợp 3: Xóa một nút cha có hai nút con. Khi loại bỏ một nút có hai nút con, trước tiên chúng ta phải tìm một nút tiếp theo có thể thay thế vị trí của nó. Hai nút có thể thay thế nút đã bị loại bỏ: inorder successor hoặc inorder predecessor. Inorder successor là con ngoài cùng bên trái của cây con bên phải và inorder predecessor là con ngoài cùng bên phải của cây con bên trái. Chúng ta sẽ sao chép nội dung của nút successor (kế nhiệm)/predecessor (tiền nhiệm) và xóa inorder successor/predecessor.

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

#include

#include

typedef struct Node { int data; Node* left; Node* right; } node_t; void Free( node_t* root ) { if ( root == NULL ) return; Free( root->left ); Free( root->right ); free( root ); } int LeftOf( const int value, const node_t* root ) { // Nếu bạn muốn cây BST cho phép giá trị trùng lặp, hãy sử dụng dòng code thứ 2 return value < root->data; // return value <= root->data; } int RightOf( const int value, const node_t* root ) { return value > root->data; } node_t* Insert( node_t* root, const int value ) { if ( root == NULL ) { node_t* node = (node_t*)malloc( sizeof( node_t ) ); node->left = NULL; node->right = NULL; node->data = value; return node; } if ( LeftOf( value, root ) ) root->left = Insert( root->left, value ); else if ( RightOf( value, root ) ) root->right = Insert( root->right, value ); return root; } bool Search( const node_t* root, int value ) { if ( root == NULL ) return false; if(root->data == value){ return true; }else if ( LeftOf( value, root ) ){ return Search( root->left, value ); }else if( RightOf( value, root ) ){ return Search( root->right, value ); } } int LeftMostValue( const node_t* root ) { while ( root->left != NULL ) root = root->left; return root->data; } node_t* Delete( node_t* root, int value ) { if ( root == NULL ) return root; if ( LeftOf( value, root ) ) root->left = Delete( root->left, value ); else if ( RightOf( value, root ) ) root->right = Delete( root->right, value ); else { // root->data == value, delete this node if ( root->left == NULL ) { node_t* newRoot = root->right; free( root ); return newRoot; } if ( root->right == NULL ) { node_t* newRoot = root->left; free( root ); return newRoot; } root->data = LeftMostValue( root->right ); root->right = Delete( root->right, root->data ); } return root; } void PreOrder(node_t* root){ if(root != NULL) { printf(“%d “, root->data); PreOrder(root->left); PreOrder(root->right); } } void InOrder(node_t* root){ if(root != NULL) { InOrder(root->left); printf(“%d “, root->data); InOrder(root->right); } } void PostOrder(node_t* root){ if(root != NULL) { PostOrder(root->left); PostOrder(root->right); printf(“%d “, root->data); } } int main() { node_t* root = NULL; root = Insert( root, 25 ); root = Insert( root, 15 ); root = Insert( root, 50 ); root = Insert( root, 10 ); root = Insert( root, 22 ); root = Insert( root, 35 ); root = Insert( root, 70 ); root = Insert( root, 4 ); root = Insert( root, 12 ); root = Insert( root, 18 ); root = Insert( root, 24 ); root = Insert( root, 31 ); root = Insert( root, 44 ); root = Insert( root, 66 ); root = Insert( root, 90 ); printf(“\nDuyet preorder : “); PreOrder(root); printf(“\nDuyet inorder : “); InOrder(root); printf(“\nDuyet postorder:”); PostOrder(root); printf(“\n==Thu them phan tu 15 vao BTS==\n”); Insert(root, 15); printf(“\nDuyet preorder : “); PreOrder(root); printf(“\nDuyet inorder : “); InOrder(root); printf(“\nDuyet postorder:”); PostOrder(root); printf(“\n==Thu xoa phan tu 50 khoi BTS==\n”); Delete(root, 50); printf(“\nDuyet preorder : “); PreOrder(root); printf(“\nDuyet inorder : “); InOrder(root); printf(“\nDuyet postorder:”); PostOrder(root); Free( root ); root = NULL; return 0; }

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

Nhờ các bạn kiểm tra kết quả chạy của code:

Duyet preorder : 25 15 10 4 12 22 18 24 50 35 31 44 70 66 90 Duyet inorder : 4 10 12 15 18 22 24 25 31 35 44 50 66 70 90 Duyet postorder:4 12 10 18 24 22 15 31 44 35 66 90 70 50 25 ==Thu them phan tu 15 vao BTS== Duyet preorder : 25 15 10 4 12 22 18 24 50 35 31 44 70 66 90 Duyet inorder : 4 10 12 15 18 22 24 25 31 35 44 50 66 70 90 Duyet postorder:4 12 10 18 24 22 15 31 44 35 66 90 70 50 25 ==Thu xoa phan tu 50 khoi BTS== Duyet preorder : 25 15 10 4 12 22 18 24 66 35 31 44 70 90 Duyet inorder : 4 10 12 15 18 22 24 25 31 35 44 66 70 90 Duyet postorder:4 12 10 18 24 22 15 31 44 35 90 70 66 25 Process returned 0 (0x0) execution time : 0.047 s Press any key to continue.

Các loại cây nhị phân[sửa | sửa mã nguồn]

Thuật ngữ về cây không được chuẩn hóa tốt và do đó thay đổi trong các tài liệu.

• Một cây nhị phân gốc có một nút gốc và mỗi nút có tối đa hai nút con.

• Một cây nhị phân đầy đủ (đôi khi được gọi là đúng đắn[7] hay phẳng hay cây nhị phân nghiêm ngặt)[8] [9] là một cây có mỗi nút đều có hoặc không có hoặc 2 nút con. Một cách định nghĩa khác cho cây nhị phân đầy đủ là một cách định nghĩa đệ quy. Một cây nhị phân đầy đủ gồm:[10]
  • Một đỉnh đơn lẻ (một nút đơn lẻ làm nút gốc).
  • Một cây có nút gốc có hai nhánh con, cả hai đều là cây nhị phân đầy đủ.
• Một cây nhị phân hoàn hảo là một cây nhị phân mà tất cả các nút bên trong đều có hai nút con và tất cả các nút lá đều có cùng độ sâu hoặc cùng cấp độ (cấp độ của một nút được định nghĩa là số đường nối từ nút gốc đến nút đó).[11] Một ví dụ về cây nhị phân hoàn hảo là biểu đồ tổ tiên của một người đến một độ sâu nhất định nhỏ hơn mức mà tổ tiên sẽ xuất hiện nhiều hơn một lần trong biểu đồ (tại thời điểm này, biểu đồ không còn là một cây có các nút duy nhất; chú ý là cùng một tổ tiên có thể xuất hiện ở các độ sâu khác nhau trong biểu đồ), vì mỗi người có đúng hai cha mẹ sinh học (một mẹ và một cha). Miễn là biểu đồ tổ tiên luôn hiển thị mẹ và cha ở cùng một bên cho một nút nhất định, giới tính của họ có thể được coi là tương đương với nút con trái và phải, con ở đây được hiểu là một thuật ngữ thuật toán. Một cây nhị phân hoàn hảo là một cây nhị phân đầy đủ, nhưng đảo ngược của nó không nhất thiết đúng.
• Một cây nhị phân hoàn chỉnh là một cây nhị phân trong đó mọi cấp độ, ngoại trừ có thể là cấp cuối cùng, đều được lấp đầy hoàn toàn và tất cả các nút ở cấp cuối cùng nằm càng bên trái càng tốt. Nó có thể có từ 1 đến 2h nút ở cấp cuối cùng h.[12] Một cây hoàn hảo vì vậy luôn luôn là hoàn chỉnh nhưng một cây hoàn chỉnh không nhất thiết hoàn hảo. Một số tác giả sử dụng thuật ngữ hoàn chỉnh để chỉ một cây nhị phân hoàn hảo như được định nghĩa ở trên, trong trường hợp đó họ gọi loại cây này (với một cấp cuối không nhất thiết phải lấp đầy) là cây nhị phân gần như hoàn chỉnh hoặc hầu như hoàn chỉnh.[13][14] Một cây nhị phân hoàn chỉnh có thể được biểu diễn hiệu quả bằng một mảng.[12]

• Trong cây nhị phân vô hạn hoàn chỉnh, cây có cấp độ, trong đó ở mỗi cấp độ d số nút hiện có ở cấp độ d bằng 2d. Số lượng phần tử của tập hợp tất cả các cấp độ là (vô hạn đếm được). Số lượng phần tử của tập hợp tất cả các đường đi (các “lá”, cứ coi như vậy) là không đếm được, có số lượng của liên tục.
• Một cây nhị phân cân bằng là một cấu trúc cây nhị phân trong đó nhánh con trái và nhánh con phải của mỗi nút không chênh lệch về chiều cao (số đường nối từ nút trên cùng đến nút xa nhất trong nhánh con) không quá 1.[15] Người ta cũng có thể xem xét các cây nhị phân trong đó không có lá nào xa gốc hơn các lá khác. (Các lược đồ cân bằng khác nhau cho phép các định nghĩa khác nhau về “xa hơn”. [16])
• Một cây tàu lượn (hoặc bệnh lý) là một cây mà mỗi nút cha chỉ có một nút con liên quan.[17] Điều này có nghĩa là cây sẽ hoạt động như một cấu trúc dữ liệu danh sách liên kết. Trong trường hợp này, lợi ích của việc sử dụng cây nhị phân bị giảm đáng kể vì nó về cơ bản là một danh sách liên kết có độ phức tạp độ phức tạp thời gian là O(n) (n là số nút) và nó có nhiều không gian dữ liệu hơn danh sách liên kết do hai con trỏ cho mỗi nút, trong khi độ phức tạp O(log2n) cho tìm kiếm dữ liệu trong cây nhị phân cân bằng thường được mong đợi.

Binary Search Tree (Cây tìm kiếm nhị phân) là gì?

• Vai trò của kiến trúc bảo mật thích ứng trong quản lý ninh mạng
• Ưu điểm khi kết hợp trí tuệ nhân tạo AI và RPA – Robotic Process Automation
• Cấu trúc dữ liệu là gì? Những điều cần biết về cấu trúc dữ liệu
• Làm thế nào để học lập trình? Mẹo hay cho người mới bắt đầu
• Trung tâm Công nghệ chuyên sâu xSeries ra mắt phiên bản mới môn Toán rời rạc

Binary Search Tree là một trong những cấu trúc dữ liệu khác nhau giúp tổ chức và sắp xếp dữ liệu. Nó rất linh hoạt và là một cách hiệu quả để lưu trữ dữ liệu theo hệ thống phân cấp.

Trong bài viết này, chúng ta sẽ xem xét kỹ hơn cách thức hoạt động — cũng như các thuộc tính và ứng dụng của Binary Search Tree.

Binary Search Tree (BTS)

Một Binary Search Tree có thuộc tính sau:

• Tất cả các node phải sao cho node con bên trái luôn nhỏ hơn node cha.
• Node con bên phải luôn lớn hơn node cha.

Hình dưới đây là một minh họa cho một cây nhị phân, khi mà dữ liệu được tổ chức giống như một cây.

Trong các phần sau, chúng ta sẽ xem cách tìm kiếm, chèn và xóa trong BTS bằng cả hai phương pháp: sử dụng vòng lặp và đệ quy.

🔥 Đọc thêm về thuật toán:

• Thuật toán Quick Sort – Java Example
• 5 thuật toán mà mọi lập trình viên nên biết
• Bài toán tháp Hà Nội – Thuật toán và cách giải

Trước tiên, hãy tạo cấu trúc dữ liệu Binary Search Tree:

public class BinaryTree { public TreeNode root; public static class TreeNode { public TreeNode left; public TreeNode right; public Object data; public TreeNode(Object data) { this.data = data; left = right = null; } } }

Tìm kiếm đệ quy BST

Đoạn code dưới đây sẽ thực thi việc tìm kiếm một giá trị trong tree theo phương pháp đệ quy.

public class SearchInsertRemoveFromTree { public static void main(String[] args) { /** * Our Example Binary Search Tree * 10 * 5 20 * 4 8 15 25 */ BinaryTree tree = new BinaryTree(); tree.root = new TreeNode(10); tree.root.left = new TreeNode(5); tree.root.right = new TreeNode(20); tree.root.left.left = new TreeNode(4); tree.root.left.right = new TreeNode(8); tree.root.right.left = new TreeNode(15); tree.root.right.right = new TreeNode(25); System.out.println(“Search Value 2 is in tree? ” + searchRecursively(tree.root, 2)); System.out.println(“Search Value 10 in tree? ” + searchRecursively(tree.root, 10)); } public static boolean searchRecursively(TreeNode root, int value) { if (root == null) return false; if ((int) root.data == value) return true; if (value < (int) root.data) return searchRecursively(root.left, value); else if (value > (int) root.data) return searchRecursively(root.right, value); return false; } }

Kết quả thu được:

Tìm kiếm nhị phân BST sử dụng vòng lặp

Vẫn với yêu cầu tìm kiếm tương tự như phần trên, nhưng lần này chúng ta sử dụng phương pháp dùng vòng lặp.

Với phương pháp dùng vòng lặp, nó có ưu điểm là dễ debug hơn nhiều so với đệ quy.

public static boolean searchIteratively(TreeNode root, int value) { while (root != null) { if ((int) root.data == value) return true; if (value < (int) root.data) root = root.left; else root = root.right; } return false; }

Chèn thêm một giá trị vào cây nhị phân bằng đệ quy

public static TreeNode insertionRecursive(TreeNode root, int value) { if (root == null) return new TreeNode(value); if (value < (int) root.data) { root.left = insertionRecursive(root.left, value); } else if (value > (int) root.data) { root.right = insertionRecursive(root.right, value); } return root; } public static void printInorderTraversal(TreeNode root) { if (root != null) { printInorderTraversal(root.left); System.out.print(root.data + ” “); printInorderTraversal(root.right); } }

Giả sử chúng ta gọi hàm trên trong

main()

, bạn làm như sau:

tree.root = insertionRecursive(tree.root, 24); tree.root = insertionRecursive(tree.root, 2); printInorderTraversal(tree.root);

Cây được in dưới dạng inorder traversal

Chèn thêm một giá trị vào cây nhị phân bằng vòng lặp

Để làm được điều này trong cây BST, chúng ta sẽ cần duyệt qua cây bằng cách sử dụng hai con trỏ.

public static TreeNode insertionIterative(TreeNode root, int value) { TreeNode current, parent; TreeNode tempNode = new TreeNode(value); if (root == null) { root = tempNode; return root; } else { current = root; } while (true) { parent = current; if (value < (int) current.data) { current = current.left; if (current == null) { parent.left = tempNode; return root; } } else if (value > (int) current.data) { current = current.right; if (current == null) { parent.right = tempNode; return root; } } } }

Xóa một phần tử trong cây nhị phân bằng cách đệ quy

Việc xóa phần tử khỏi cây nhị phân phức tạp hơn so với tìm kiếm và chèn một chút. Vì chúng ta phải đảm bảo rằng hai thuộc tính của cây nhị phân vẫn được bảo toàn.

Để xóa một phần tử, trước tiên chúng ta cần tìm kiếm và xác định được nó đã. Sau đó, chúng ta cần xác định xem phần tử đó có phần tử con hay không!

• Nếu không có con – Chỉ cần xóa.
• Nếu có một con – Sao chép con đó vào node.
• Nếu có hai con – Xác định phần tử cao nhất tiếp theo (con kế nhiệm inorder) trong cây con bên phải. Thay thế node bị xóa bằng node kế nhiệm nhỏ hơn. Xóa bản sao kế nhiệm inorder.

Có thể thu được giá trị kế nhiệm inorder bằng cách tìm giá trị nhỏ nhất trong con bên phải của node.

Chương trình java sau đây xóa các phần tử khỏi BST:

public static TreeNode deleteRecursively(TreeNode root, int value) { if (root == null) return root; if (value < (int) root.data) { root.left = deleteRecursively(root.left, value); } else if (value > (int) root.data) { root.right = deleteRecursively(root.right, value); } else { if (root.left == null) { return root.right; } else if (root.right == null) return root.left; root.data = inOrderSuccessor(root.right); root.right = deleteRecursively(root.right, (int) root.data); } return root; } public static int inOrderSuccessor(TreeNode root) { int minimum = (int) root.data; while (root.left != null) { minimum = (int) root.left.data; root = root.left; } return minimum; }

Giả sử chúng ta gọi hàm trên trong

main()

, bạn làm như sau:

tree.root = deleteRecursively(tree.root, 4); tree.root = deleteRecursively(tree.root, 20); printInorderTraversal(tree.root);

Đầu ra là:2 5 8 10 15 24 25

Hãy làm tương tự lặp đi lặp lại.

Xóa một phần tử trong cây nhị phân bằng cách sử dụng vòng lặp

public static TreeNode deleteNodeIteratively(TreeNode root, int value) { TreeNode parent = null, current = root; boolean hasLeft = false; if (root == null) return root; while (current != null) { if ((int) current.data == value) { break; } parent = current; if (value < (int) current.data) { hasLeft = true; current = current.left; } else { hasLeft = false; current = current.right; } } if (parent == null) { return deleteNodeIteratively(current); } if (hasLeft) { parent.left = deleteNodeIteratively(current); } else { parent.right = deleteNodeIteratively(current); } return root; } private static TreeNode deleteNodeIteratively(TreeNode node) { if (node != null) { if (node.left == null && node.right == null) { return null; } if (node.left != null && node.right != null) { TreeNode inOrderSuccessor = deleteInOrderSuccessorDuplicate(node); node.data = inOrderSuccessor.data; } else if (node.left != null) { node = node.left; } else { node = node.right; } } return node; } private static TreeNode deleteInOrderSuccessorDuplicate(TreeNode node) { TreeNode parent = node; node = node.right; boolean rightChild = node.left == null; while (node.left != null) { parent = node; node = node.left; } if (rightChild) { parent.right = node.right; } else { parent.left = node.right; } node.right = null; return node; }

Độ phức tạp của thuật toán BST là 0(h). Trong đó h là độ cao của cây.

Bài viết của mình đến đây là hết rồi. Mình hi vọng vẫn cảm thấy thích thú với thuật toán ^^

Nguồn tham khảo:

• https://en.wikipedia.org/wiki/Binary_search_tree
• https://www.cs.usfca.edu/~galles/visualization/BST.html
• https://www.journaldev.com/23086/binary-search-tree-bst-search-insert-remove