K******g 发帖数: 1870 | 1 如果面试被问到,在已知的BST里insert一个节点,请问这个怎么回答啊
好像简单点的就是,每次insert都产生一个新的leaf,也可以在中间产生一个新的node
。中间产生一个新的node一般是用在RB tree里吧? | d**e 发帖数: 6098 | 2 不是很明白……
插入一个节点,不管它是leaf还是中间节点,只要它保持是BST就行了吧
node
【在 K******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果面试被问到,在已知的BST里insert一个节点,请问这个怎么回答啊 : 好像简单点的就是,每次insert都产生一个新的leaf,也可以在中间产生一个新的node : 。中间产生一个新的node一般是用在RB tree里吧?
| t****t 发帖数: 387 | | f***g 发帖数: 214 | 4 就算是中间插入node
也要走到leaf来决定在哪里插入。
所以在中间插入不怎么make sense. | a****n 发帖数: 1887 | 5 简单点的log(n), 直接插到leaf,
复杂点的 red-black tree, avl tree, 通过旋转保持平衡, 一般不会考 |
|