Given a search() method in a height balanced binary tree (AVL 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)". Vòng lặp chỉ đi theo một đường từ gốc xuống, mỗi lần so sánh thì hoặc rẽ trái hoặc rẽ phải, nên số lần lặp nhiều nhất bằng chiều cao cây. Cây AVL giữ hiệu chiều cao hai nhánh của mọi nút trong khoảng từ -1 tới 1, nhờ đó chiều cao bị chặn bởi một hằng số nhân logarit của số nút, và phép tìm tốn thời gian tỉ lệ với log n. Mức "O(n)" đúng cho cây nhị phân tìm kiếm không cân bằng, trường hợp suy biến thành một dây nút giống danh sách liên kết, chính là điều mà ràng buộc AVL ngăn lại. Mức "O(nlog n)" là chi phí của các phép sắp xếp so sánh trên cả n phần tử, ở đây chỉ có một đường đi xuống nên không có thừa số n. Mức "O(n^2)" cần hai vòng lặp lồng nhau trên dữ liệu, mà đoạn mã chỉ có một vòng và trong vòng không có phép lặp nào khác.
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