1.查找(Search)
算法:从根节点开始,如果目标键值小于当前节点的键值,则递归地在左子树中查找;如果目标键值大于当前节点的键值,则递归地在右子树中查找;如果找到目标键值,则返回该节点。
时间复杂度:在最坏情况下(树退化为链表),时间复杂度为 O(n);在最优情况下(树是平衡的),时间复杂度为 O(logn)。
2.插入(Insert)
算法:从根节点开始,找到合适的位置插入新节点。如果目标键值小于当前节点的键值,则递归地在左子树中查找插入位置;如果目标键值大于当前节点的键值,则递归地在右子树中查找插入位置;如果目标键值已经存在,则根据具体需求更新节点(例如,更新节点的值或不做任何操作)。
时间复杂度:与查找操作类似,最坏情况下为 O(n),最优情况下为 O(logn)。
3.删除(Delete)
算法:找到要删除的节点,然后分三种情况处理:
叶子节点:直接删除。
只有一个子节点:用其子节点替代被删除节点。
有两个子节点:找到该节点的中序后继(或中序前驱),用其值替代被删除节点的值,然后递归删除中序后继(或中序前驱)。
时间复杂度:最坏情况下为 O(n),最优情况下为 O(logn)。