convert a random array to BST: o(nlogn)
insertion: o(logn)
deletion: o(logn)
貌似deletion有三种情况,
1 Deleting a leaf (node with no children): Deleting a leaf is easy, as we
can simply remove it from the tree.
2 Deleting a node with one child: Remove the node and replace it with its
child.
3 Deleting a node with two children:
这三种情况不都是O(logn)吧?
z*******y 发帖数: 578
2
去找本算法书看看吧,基本每本算法书都讲的很清楚
r*******y 发帖数: 1081
3
this is average complexity
【在 h*****g 的大作中提到】 : convert a random array to BST: o(nlogn) : insertion: o(logn) : deletion: o(logn) : 貌似deletion有三种情况, : 1 Deleting a leaf (node with no children): Deleting a leaf is easy, as we : can simply remove it from the tree. : 2 Deleting a node with one child: Remove the node and replace it with its : child. : 3 Deleting a node with two children: : 这三种情况不都是O(logn)吧?