Java 中 TreeSet 方法的计算复杂性

algorithm data-structures java treeset avl-tree

2022-09-01 22:41:20

Java中TreeSet方法的计算复杂性是否与AVLTree相同？

具体来说，我想知道以下方法的计算复杂性：1.add 2.remove 3.first 4.last 5。6楼。高等

对于 AVL 树，有所有 O（logn）？上述树集方法的复杂性是什么？

答案 1

处理单个元素的运算是所有 O（ln n）比较，除了第一个和最后一个是 O（1）比较或 O（ln N）节点搜索时间。

comparator（）， iterator（）， clear（）， first（）， isEMpty（）， size（）， last（）， pollFirst（）， pollLast（） are O（1）

add（）， ceiling（）， contains（）， floor（）， headSet（）， higher（）， lower（）， remove（）， subSet（）， tailSet（） are O（ln N）

clone（）， equals（）， hashCode（）， toArray（）和 toString（）是 O（n）

答案 2

first（）， last（）， pollFirst（）， pollLast（）： O（lgn）， not O（1）.