"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 21: Cây nhị phân tìm kiếm" thông tin đến các bạn những kiến thức về khái niệm cây nhị phân tìm kiếm, các thao tác trên cây nhị phân tìm kiếm, một vài ví dụ sử dụng cây nhị phân tìm kiếm. | Cấu trúc dữ liệu và giải thuật Bài 21. Cây nhị phân tìm kiếm Giảng viên TS. Ngo Huu Phuc Tel 0438 326 077 Mob 098 5696 580 Email ngohuuphuc76@ 1 @copyright by PhD Ngo Huu Phuc Le Quy Don Technical University Bài 21 Cây nhị phân tìm kiếm Nội dung . Khái niệm cây nhị phân tìm kiếm. . Các thao tác trên cây nhị phân tìm kiếm. . Một vài ví dụ sử dụng cây nhị phân tìm kiếm. Tham khảo 1. Deshpande Kakde C and Data Chapter 20 Linked Lists 2. Elliz Horowitz Fundamentals of Data Chapter 4 Linked Lists 3. Kyle Loudon Mastering Algorithms with Chapter 5 Linked Lists. 4. Bài giảng TS Nguyễn Nam Hồng 2 @copyright by PhD Ngo Huu Phuc Le Quy Don Technical University . Khái niệm về cây nhị phân tìm kiếm 1 4 Khái niệm Cây nhị phân tìm kiếm là cây rỗng hoặc cây mà node có chứa các khóa. Các khóa của node trên cây con bên trái nhỏ hơn khóa của root khóa của các node trên cây con bên phải lớn hơn khóa của root. Cây con bên trái và phải cũng là cây nhị phân tìm kiếm. Việc quản lý cây nhị phân thông qua node root. 3 @copyright by PhD Ngo Huu Phuc Le Quy Don Technical University . Khái niệm về cây NPTK 2 4 50 30 60 25 40 70 35 65 Ví dụ về cây nhị phân tìm kiếm 4 @copyright by PhD Ngo Huu Phuc Le Quy Don Technical University . Khái niệm về cây NPTK 3 4 Một số tính chất của cây NPTK Cây nhị phân tìm kiếm là tập con của cây nhị phân nên nó cũng có các cách duyệt LNR LRN NLR. Với cây nhị phân tìm kiếm nếu duyệt cây theo kiểu inorder ta sẽ được một dãy đã sắp theo chiều tăng dần. Cây nhị phân tìm kiếm là cấu trúc tìm kiếm hiệu quả. Việc tìm kiếm trên cây nhị phân tìm kiếm nhanh hơn tìm kiếm tuần tự. Tuy nhiên việc biểu diễn cây dạng mảng sẽ gây khó khăn cho việc thêm bớt. Với việc biểu diễn dạng liên kết ta có độ phức tạp của việc tìm kiếm là O logn . 5 @copyright by PhD Ngo Huu Phuc Le Quy Don Technical University . Khái niệm về cây NPTK 4 4 Cấu trúc cây nhị phân tìm kiếm template struct tbnode TreeEntry data struct .
