Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương 5: Cây nhị phân tìm kiếm - Phần 1 - Trần Minh Thái

Chương 5. Cây nhị phân tìm kiếm – Phần 1Trần Minh TháiEmail: minhthai@huflit.edu.vnWebsite: www.minhthai.edu.vn1Nội dungKhái niệmĐặc điểmĐịnh nghĩa cấu trúc dữ liệuCác lưu ý khi cài đặtCác thao tác xử lý2Khái niệmBậc của một nút: là số cây con của nút đó Bậc của cây: là bậc lớn nhất của các nút trong cây. Cây có bậc n thì gọi là cây n-phân Nút gốc: là nút không có nút chaNút lá: là nút có bậc bằng 0 Nút nhánh: là nút có bậc khác 0 và không phải là gốc3222110000Mức 4Mức 3Mức 2Mức 1Khái niệmChiều dài đường đi đến nút x: là số nhánh cần đi qua kể từ gốc đến xChiều cao h của cây: Mức lớn nhất của các nút lá4xĐặc điểm của cây nhị phânSố nút ở mức I  2I-1Số nút ở mức lá  2h-1, với h là chiều cao của câyChiều cao của cây h  log2N, với N là số nút trong cây5Biểu diễn cây nhị phânCây nhị phân là một cấu trúc bao gồm các phần tử (node) được kết nối với nhau theo quan hệ “cha-con” với mỗi cha có tối đa 2 con. Mỗi nút gồm các thông tin: Dữ liệu lưu trữ: data Liên kết tới cây con trái của nút: pLeftLiên kết tới cây con phải của nút: pRight6Cấu trúc của một node7NútGiá trịTrỏ tráiTrỏ phảiTNodedatapLeftpRightpublic class CMyTNode { T data; CMyTNode pLeft = null; CMyTNode pRight = null; //Các phương thức}Ví dụ khai báo node chứa giá trị nguyên8public class CMyIntTNode{ int data; CMyIntTNode pLeft = null; CMyIntTNode pRight = null; //Các phương thức}Cây nhị phân tìm kiếmLà 1 cây nhị phânGiá trị của một node luôn lớn hơn giá trị của các node nhánh trái và nhỏ hơn giá trị các node nhánh phảiNút có giá trị nhỏ nhất nằm ở nút trái nhất của cây Nút có giá trị lớn nhất nằm ở nút phải nhất của cây97336161540234Các thao tác cơ bản1. Tạo cây2. Duyệt cây3. Cho biết các thông tin của cây4. Tìm kiếm5. Xoá node trên cây 10Tạo cây114015461363736316415407Nếu node cần thêm nhỏ hơn node đang xét thì thêm về bên tráiNgược lại thì thêm về bên phảiKhai báo cấu trúc cây nhị phân12public class CMyBinaryTree { CMyTNode root = null; //Nút gốc //Các phương thức}Chèn một phần tử có giá trị x vào cây: TNode(x)13B1. Nếu root là null thì root = TNode(x) : Kết thúcB2. Trong khi root khác null thực hiện - Nếu data của root x thì chèn TNode(x) vào bên trái root + Ngược lại: Trùng giá trị  Kết thúcTạo TNode có giá trị x14public class CMyTNode{ T data; CMyTNode pLeft = null; CMyTNode pRight = null; public CMyTNode(T x) { data = x; pLeft = null; pRight = null; }}15public class CMyTNode{ public bool InsertData(T x){ if (x.CompareTo(data) == 0) return false; if (x.CompareTo(data) (x); else return pLeft.InsertData(x); } else { if (pRight == null) pRight = new CMyTNode(x); else return pRight.InsertData(x); } return true; }}public class CMyBinaryTree{ CMyTNode root = null; public bool Insert(T x) { if (root == null) { root = new CMyTNode(x); return true; } else { if (root.InsertData(x)) return true; } return false; }}Bài tậpViết phương thức tạo cây nhị phân số nguyên từ các giá trị nhập vào từ bàn phím. Quá trình nhập cho đến khi gặp giá trị trùngViết phương thức tạo cây nhị phân số nguyên từ dãy số nguyên cho trước17Duyệt câyThứ tự trước (PreOrder) (NLR)Thứ tự giữa (InOrder) (LNR)Thứ tự sau (PostOrder) (LRN)1819BướcKết quả duyệt theo thứ tự NLR17L7R723L3R3R731R3R746L6R754R7636L36R36715R15R36823R36940KQ73164361523407336161540234Hàm duyệt NLRTại node t đang xét, nếu khác rỗng thìIn giá trị của tDuyệt cây con bên trái của t theo thứ tự NLRDuyệt cây con bên phải của t theo thứ tự NLR 20public void NLR(){ Xuất data; if(pLeft!=null) pLeft.NLR(); if (pRight != null) pRight.NLR();}Bài tậpVẽ cây nhị phân tìm kiếm theo thứ tự nhập từ trái sang phải và duyệt cây theo thứ tự trước:27; 19; 10; 21; 35; 25; 41; 12; 46; 7H; B; C; A; E; D; Z; M; P; THuế; Đà Nẵng; Hà Nội; Vĩnh Long; Cần Thơ; Sóc Trăng; Nha Trang; Đồng Nai; Vũng Tàu; An Giang; Tiền Giang; Bình Dương; Hải Dương21VD duyệt NLR cây NPTK số nguyên22public class CMyIntTNode{ ... public void NLR() { Console.Write(Data + "; "); if(pLeft!=null) pLeft.NLR(); if (pRight != null) pRight.NLR(); }}class CMyIntBinaryTree{ ... public void PreOrder() { root.NLR(); }}23BướcKết quả duyệt theo thứ tự LNR1L77R72L33R37R7313R37R743R37R75L667R76467R7767R787R79L3636R361015R1536R36112336R361236R361340KQ13467152336407336161540234Hàm duyệt LNRTại node t đang xét, nếu khác rỗng thìDuyệt cây con bên trái của t theo thứ tự LNRIn giá trị của tDuyệt cây con bên phải của t theo thứ tự LNR 24public void LNR(){ if(pLeft!=null) pLeft.NLR(); Xuất data; if (pRight != null) pRight.NLR();}25BướcKết quả duyệt theo thứ tự LRN1L7R772L3R33R7731R33R774L663R775463R77663R7773R778L36R363679R1515R36367102315R363671115R36367124036713367147KQ14632315403677336161540234Hàm duyệt LRNTại node t đang xét, nếu khác rỗng thìDuyệt cây con bên trái của t theo thứ tự LRNDuyệt cây con bên phải của t theo thứ tự LRN In giá trị của t 26public void LRN(){ if(pLeft!=null) pLeft.NLR(); if (pRight != null) pRight.NLR(); Xuất data;}Bài tậpVẽ cây nhị phân tìm kiếm theo thứ tự nhập: 27, 19, 10, 21, 3, 15, 41, 50, 30, 7 Hãy duyệt cây trên theo thứ tự giữaVẽ cây nhị phân tìm kiếm theo thứ tự nhập: H, B, C, A, E, D, T, M, X, O Hãy duyệt cây trên theo thứ tự sau27Kiểm tra kết quả duyệt bằng cách xây dựng lại cây nhị phân từ kết quả duyệtTạo cây từ kết quả duyệt NLRChọn giá trị đầu tiên làm node gốcLần lượt đưa các giá trị còn lại từ trái sang phải vào cây theo nguyên tắc tạo câyTạo cây từ kết quả duyệt LRNChọn giá trị cuối cùng làm node gốcLần lượt đưa các giá trị còn lại từ phải sang trái vào cây theo nguyên tắc tạo cây28Bài tậpVẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự NLR thì được dãy sau: 9, 4, 1, 3, 8, 6, 5, 7, 10, 14, 12, 13, 16, 19Hãy duyệt cây T trên theo thứ tự LRNLiệt kê các nút lá của cây. Liệt kê các nút nhánh của cây29Vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự LRN thì được dãy sau: 1, 4, 7, 5, 3, 16, 18, 15, 29, 25, 30, 20, 8Hãy duyệt cây T trên theo thứ tự NLRCây T có chiều cao là bao nhiêu? Tìm các đường đi từ gốc có độ dài là 4 trên cây30Bài tậpBài tậpCài đặt các phương thức duyệt cho cây nhị phân tìm kiếm số nguyênCài đặt các phương thức duyệt cho cây nhị phân tìm kiếm có kiểu dữ liệu chung31Tìm kiếmTìm xTìm minTìm min của cây con bên phảiTìm maxTìm max của cây con bên trái32Ví dụ tìm x = 23337336161540234Bài tậpCho cây nhị phân tìm kiếm, mỗi node có giá trị nguyên, hãy định nghĩa các phương thức sau:Tìm node có giá trị xTìm node có giá trị lớn nhấtTìm node có giá trị nhỏ nhất của cây con phảiTính độ cao của câyĐếm số node của cây34Tìm node có giá trị x35public CMyIntTNode SearchNode(int x){ if (root == null) return null; return root.SearchX(x);}class CMyIntBinaryTree36 public CMyIntTNode SearchX(int x) { if (data == x) return this; if (x this.Data) { if (pRight != null) return pRight.Remove(x, this); else return false; }class CMyIntTNode50 else { if (pLeft != null && pRight != null) { this.Data = pRight.MinValue (); pRight.Remove(this.Data, this); } else if (parent.pLeft == this) { parent.pLeft = (pLeft != null) ? pLeft : pRight; } else if (parent.pRight == this) { parent.pRight = (pLeft != null) ? pLeft : pRight; } return true; }}public int MinValue (){ if (pLeft == null) return data; return pLeft.MinValue ();}Cho dãy số theo thứ tự nhập từ trái sang phải: 20, 15, 35, 30, 11, 13, 17, 36, 47, 16, 38, 28, 14Vẽ cây nhị phân tìm kiếm cho dãy số trênCho biết kết quả duyệt cây trên theo thứ tự trước, giữa và sauCho biết độ cao của cây, các nút lá, các nút có bậc 2Vẽ lại cây sau khi thêm nút: 25 và 91Trình bày từng bước và vẽ lại cây sau khi lần lượt xoá các nút: 11 và 3551Bài tậpCài đặt lớp CMyBinaryTree (mỗi node có giá trị kiểu chung) hoàn chỉnh gồm các phương thức:Tìm kiếmXóa52Đánh giáThao tác tìm kiếm, thêm mới, xóa đều có độ phức tạp trung bình O(h) TH tốt nhất, cây có n nút sẽ có độ cao h = log2(n)  Chi phí tìm kiếm sẽ tương đương tìm nhị phân trên mảng có thứ tự TH xấu nhất, cây có thể bị suy biến thành 1 DSLK  các thao tác trên sẽ có độ phức tạp O(n) Vì vậy cần có cải tiến cấu trúc của CNPTK để đạt được chi phí cho các thao tác là log2(n) 53