|
|
1
2
|
|
|
2
2
AVL树保证“最坏”情况查找时间是O(log(n))。它保证任何两个子树的高度差至多为1。但这并不能保证整棵树的最低和最高节点之间的高度差为1。在一棵大树中,作为一个整体,它可以得到很大的高度差。 理解AVL树的关键是理解它对“子树”的定义。对于任何给定的节点,都有两个子树,有时称为左子树和右子树。这两个子树之间的高度差至多为1。现在假设这两个子树都可以连接到一个节点上,并成为一个更大的树中的一个子树。这个新的子树,称之为节点的左子树,与同一个节点上的右子树的高度差至多为1。但这也意味着这整棵树中任意两片叶子之间的最大高度差为2。这一过程可以重复进行,而AVL树的任何到叶之间都可以有较大的高度差,但仍然保持着它的大O运行时间。 |
|
|
Zevvysan · 为什么我的打印函数之一要删除节点? 8 年前 |
|
|
user9573040 · 递归二叉树高度 8 年前 |
|
|
Dipesh Desai · 在二叉树haskell中搜索值 8 年前 |
|
|
ibrahim · “main”已停止工作-C++[开发人员++] 8 年前 |