State True or False: Definition of a balanced tree: "A balanced tree is one whose root has many more left descendents than right descendants, or vice versa."
2 phương ánCó giải thích
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: "False". Phát biểu trong đề nói cây cân bằng là cây mà gốc có số con cháu bên trái nhiều hơn hẳn bên phải hoặc ngược lại, nhưng đó đúng là mô tả của một cây LỆCH, trái hẳn khái niệm cân bằng. Cân bằng nghĩa là hai phía của mỗi nút xấp xỉ nhau: ở cây AVL, chiều cao cây con trái và cây con phải của mọi nút lệch nhau nhiều nhất 1, nhờ đó chiều cao giữ ở mức khoảng log2 của n và các phép tìm, chèn, xoá còn O(log n). Vì vậy "True" sai vì nếu chấp nhận định nghĩa ấy thì cây xâu, loại cây mà mỗi nút chỉ có một con và toàn bộ con cháu dồn về một phía, lại được coi là cân bằng nhất; trong khi nó có chiều cao đúng bằng số nút và làm phép tìm tụt xuống O(n), tức chính cái mà việc cân bằng được đặt ra để tránh.
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