二叉搜索树—插入、查找、删除和遍历

发布网友发布时间：2023-01-02 08:41

共1个回答

热心网友时间：2023-10-09 09:24

二叉搜索树是一种特殊的二叉树，他的每一个结点都有一个键值，且左结点的值都小于父结点的值，右结点的值都大于父结点的值，这些键值都不能重复。

一般情况下，插入、查找、删除的时间复杂度为O(logN)。

最坏情况下二叉查找树退化成一个链表，插入、查找、删除的时间复杂度为O(N)。

遍历的时间复杂度为O(N)。

二叉搜索树的中序遍历是从小到大排序的结果，中序遍历中在某结点后面的结点就是它的后继。

根据要删除结点的子结点的个数分为以下几种情况。

声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com