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

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ó nút 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 tiìm kiếm trở nên phức tạp hơn.

Tìm kiếm (Searching)

Hàm trả về chiều cao của cây

ví dụ đây là cây có chiều cao là 2 ( 0 –> 1 –> 2 )

Hàm đếm lá trong cây

Duyệt Node theo stack

Heapsort

Heap là một cấu trúc dữ liệu , có thể được biểu diễn thông qua 2 cách :
-Dạng thứ 1: Dạng cây nhị phân có đặc điểm là node cha thì lớn hơn 2 node con trực tiếp của nó .
-Dạng thứ 2: nếu ta đánh số các node theo thứ tự từ trên xuống và từ trái qua . Bắt đầu là node root = 0 , thì ta có thể định nghĩa heap thông qua mảng một chiều , có đặc điểm là phần tử thứ k sẽ lớn hơn các phần tử thứ 2k+1 và 2k+2 . Ta có thể dễ nhận thấy là phàn tử thứ 0 sẽ tương ứng với root trong cây ở cách biểu diễn thứ 1

Nguyên tắc sắp xếp của heap sort
Dựa vào tính chất của heap trong cách biểu diễn thứ 1 và thứ 2 , ta có thể thấy phần tử đầu tiên trong cách biểu diễn theo mảng sẽ là phần tử lớn nhất —> cách sắp xếp đơn giản là : ( Gọi mảng ban đầu là A )

Khởi tạo : Tạo heap từ mảng ban đầu đã cho (mảng A )
1. Lấy phần tử đầu tiên trong mảng ra bỏ vào mảng kết quả
2. Tạo lại heap từ mảng A
3.Quay lại bước 1
Phương thức khởi tạo

Build

Heapify
ngoài ra trong C thì mảng luôn bắt đầu ở 0 nên left và right đc cộng tương ứng là 1 và 2
lấy ra giá trị max