Given a search() method in a binary search tree:
4 phương ánCó giải thích
Node search(int x)
{ Node p = root;
while(p!=null && p.info != x)
{ if(x<p.info) p = p.left;
else p=p.right;
}
return(p);
}The complexity of this algorithm is:
Các phương án trả lời
Chọn một phương ánLời giảiChọn phương án để mở
Đáp án đúng: "O(log n).". Thân vòng while chỉ làm một việc là so x với p.info rồi chuyển p sang p.left hoặc p.right, tức mỗi lượt đi xuống đúng một tầng và cắt bỏ trọn một cây con, nên số lượt lặp nhiều nhất bằng chiều cao cây. Với cây tìm kiếm nhị phân có chiều cao tối ưu trên n nút thì chiều cao xấp xỉ log2 của n, nên chi phí tìm là O(log n), và đó cũng chính là lý do người ta phải cân bằng cây. Vì vậy "O(n^2)" sai vì không có vòng lặp lồng nhau nào, thân vòng chỉ gồm một phép so sánh và một phép gán; "O(nlog n)" sai vì đó là cấp của các thuật toán sắp xếp dựa trên so sánh phải chạm mọi phần tử, còn ở đây ta chỉ đi một đường từ gốc xuống; riêng "O(n)." chỉ đúng khi cây suy biến thành dạng xương sống, mỗi nút một con và chiều cao bằng số nút, tức trường hợp xấu nhất mà câu hỏi không nêu, nên nó không phải cấp đặc trưng được gán cho phép tìm trên cây tìm kiếm.
Cùng phần 4
What is the minimum number of nodes in a nearly complete binary tree with height 4?
(In a tree the height of root is 1, and a binary tree with height h is called nearly complete if the tree is complete at level d for d = 1, 2, ..., h-1, and the leaves in the last level are all in the leftmost positions).Có lời giảiCâu hỏiTo implement an AVL tree, a concept balance factor is introduced (bal = height(right)-height(left)). Suppose an AVL tree is created by inserting to the tree the following keys sequentially:
6, 3, 7, 2, 5, 1
What is the balance factor of the node 6? (please note that the tree is still AVL)Có lời giảiCâu hỏiSuppose the binary search tree T is made by inserting the following keys consequently: 6, 7, 8, 9, 3, 2, 5, 4
What is the result of breadth-first traverse of T?Có lời giảiCâu hỏiCả 76 câu của chủ đề76 câu
Xuất hiện trong 1 bộ đề
Đi tiếp từ đây