vì ở lượt gọi đầu tiên thì h = 2^0 = 1, ở lượt thứ i thì h = 2^(i-1). Mà sau lượt gọi cuối cùng thì kích thước mảng bằng n --> 2^(i-1) = n --> i - 1 = log2n --> i xấp xỉ log2n
Vậy chi phí thời gian cho giải thuật này là O(nlog2n). Một lưu ý khác nữa đó là giải thuật này có chi phí không gian khá lớn do phải dùng mảng phụ có kích thước bằng mảng ban đầu. Vì vậy ng ta thường dùng phương pháp sắp xếp này với kiểu sắp xếp ngoài.
15. Trình bày (bằng ngôn ngữ tựa C) giải thuật loại bỏ một nút có giá trị X trên cây nhị phân tìm kiếm. Chi phí thời gian trung bình của giải thuật này có lớn hơn giải thuật tìm kiếm rồi bổ sung hay không, vì sao? Mỗi nút trên cây có cấu trúc như sau: P_L Trỏ tới cây con trái, KEY Chứa giá trị khoá, P_R Trỏ tới cây con phải
BST_DEL(T, x){ P = T; Q = NULL; //Q luôn trỏ vào nút cha của P while(P != NULL){ //vòng này tìm xem có x trong BST hay k if(P->KEY == x){ //tìm thấy break; } Q = P; if(x < Q->KEY){ P = P->P_L; }else{ P = P->P_R; } } if(P == NULL){ printf("Không tìm thấy!"); return; } //trường hợp nút tìm thấy có 2 cây con (tìm nút thay thế) if(P->P_L != NULL && P->P_R != NULL){ //ta sẽ tìm nút cực phải của cây con trái để thay vào nút cần xoá TEMP = P; //nút tạm, nhớ vị trí cần xoá Q = P; P = P->P_L; //chuyển qua cây con trái while(P->P_R != NULL){ //tìm nút cực phải Q = P; P = P->P_R; } TEMP->KEY = P->KEY; //gán lại giá trị cho nút cần xoá } //đến bước này nút cần xoá chỉ có 1 nhánh con hoặc là lá
