对于一个高度为h的AVL树，其最少结点数是多少?反之，对于一个有n个结点的AVL树,其最大高度是多少?最小高度是多少?
解 设高度为h (空树的高度为-1)的AVL树的最少结点数为Nh,则[tex=5.214x1.214]CLAs2JL5wicsJ/0ueNRktZUxj1ESmnaohDo5xr6OiBg=[/tex]。[tex=1.071x1.214]shjtgs9PXFtm0DtVo52gbA==[/tex]是斐波那契数。又设AVL树有n个结点，则其最大高度不超过[tex=6.786x1.357]2v/eh8QoCfqeLm/+GqqDZeYFoeOYu6RhMcM0NtJFYQ6My63Qi4yx6VkK6OQuwnUF[/tex],最小高度为[tex=7.071x1.357]WViEpUU2rguUZzuk9kOgFjijfZSL5yJuO1vCSxYp5v+7O03i/XlOlko+7GBAY8Hu[/tex]。[img=272x134]17aeaff765c428b.png[/img] [img=312x176]17aeb00161460dd.png[/img]
举一反三
- 【AVL树的性质】①含有n个结点的AVL树的高度为____1_____;②在含有n个结点的AVL树中搜索一个元素需要___2____时间；③将一个新元素插入一棵n个 结点的AVL树中，可得到一棵____3__个结点的AVL树，且插入所需的计算时间为_____4___;④从一棵n个结点的AVL树中删除一个元素，可得到一棵__5___个结点的AVL树，且删除所需的 计算时间为_____6___;
- 若一AVL树的结点数是21，则该树的高度至多是多少？注：只有一个根节点的树高度为0 A: 4 B: 5 C: 6 D: 7
- 若一AVL树的结点数是21，则该树的高度至多是多少？注：只有一个根节点的树高度为0 A: 4 B: 5 C: 6 D: 7
- 若一AVL树的结点数是21，则该树的高度至多是多少？注：只有一个根节点的树高度为0 A: 4 B: 5 C: 6 D: 7
- 中国大学MOOC: 若一AVL树的结点数是21，则该树的高度至多是多少？注：只有一个根节点的树高度为0
内容
- 0
中国大学MOOC: 含有 54 个结点的平衡二叉树（ AVL 树）的最小高度是（ ）。
- 1
若一AVL树的结点数是21，则该树的高度至多是多少？注：只有一个根节点的树高度为0 A: 4 B: 5 C: 6 D: 7
- 2
中国大学MOOC: 含有 54 个结点的平衡二叉树（ AVL 树）的最大高度是（ ）。
- 3
高度为7的AVL树最少有（）个结点 A: 31 B: 32 C: 33D
- 4
一棵高度为h的AVL树，若其每个非叶结点的平衡因子都是0，则该树共有______个结点。 A: 2h-1-1 B: 2h-1 C: 2h-1+1 D: 2h-1