Singly Linked List Map | Binary Search Tree Map | |
---|---|---|
增add | O(n) | O(h) |
查contains | O(n) | O(h) |
删remove | O(n) | O(h) |
改set | O(n) | O(h) |
h为二叉树的深度,当二分搜索树为满二叉树,
github不支持Markdown的mathjax渲染,解决方案chrome安装MathJax Plugin for Github
当二分搜索树为斜树时,二分搜索树退化为链表,时间复杂度同链表,即 h<=n,这一问题可以使用平衡二叉树解决。