二叉查找树
2016-11-17 本文已影响0人
crf1028
二叉查找树（英语：Binary Search Tree）Wiki
</br>
动画演示：
-
VisuAlgo
</br>
特点
- 如果任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 如果任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
</br>
api及时间复杂度
| api | 作用 | 时间复杂度 |
|---|---|---|
| insert | 插入节点 | O(log n) / O(n) |
| find | 查找数据 | O(log n) / O(n) |
| find_next | 查找下一个数据 | O(log n) / O(n) |
| range_search | 在某范围内查找数据 | O(log n) / O(n) |
| delete | 删除数据 | O(log n) / O(n) |
</br>
实现
python: gist link
心得
- find是bst的核心，因为所有其他的api都可以通过find实现
</br>
