1樓：喵小採
在具有n個結點的二叉排序樹上插入乙個結點時，其時間複雜度是o(n) ，如果是最一般最基礎的二叉樹的話，因為深度不平衡，所以會發展成單鏈的形狀，就是一條線n個點那麼深。
若根結點的關鍵字值等於查詢的關鍵字，成功。否則，若小於根結點的關鍵字值，遞迴查左子樹。若大於根結點的關鍵字值，遞迴查右子樹。若子樹為空，查詢不成功。
擴充套件資料
插入演算法：
執行查詢演算法，找出被插結點的父親結點。判斷被插結點是其父親結點的左、右兒子。將被插結點作為葉子結點插入。
若二叉樹為空。則首先單獨生成根結點。注意：
新插入的結點總是葉子結點。
具有下列性質的二叉樹： 若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；左、右子樹也分別為二叉排序樹。
2樓：墨汁諾
最差情況下是o(n) 如果是最一般最基礎的二叉樹的話，因為深度不平衡，所以會發展成單鏈的形狀,就是一條線 n個點那麼深，如果是深度平衡的二叉樹 o(logn)。
因為插入的時候需要先查詢插入的位置，而查詢插入的位置，需要的時間就是log2n。
在二叉排序樹中插入乙個結點的時間複雜度
3樓：墨汁諾
採用邊查詢邊插入的方式，類似重新建立乙個一維陣列時間複雜度＝o（n)因為深度不平衡，所以會發展成單鏈的形狀,就是一條線 n個點那麼深。
二叉排序樹是查詢過程中，當樹中不存在關鍵字等zhi於給定值的結點時再進行插入。新插入的結點一定是乙個新新增的葉子結點，並且是查詢不成功時查詢路徑上訪問的最後乙個結點的左孩子或右結點。
因此二叉排序樹插入時間複雜度最大為o(n)。若是二叉排序樹比較平衡，其時間複雜度下降，最小的時間複雜度為o(logn)。
4樓：為你鎖愛
最壞的情況是o(n）
5樓：陝西it優就業
nlogn
n為節點數，logn為你的樹高
8. 在二叉排序樹中插入乙個結點的平均時間複雜度為( )。 a. o(1) b. o(n) c
6樓：徜逸
平均的時間復bai雜度在
duo(logn)到o(n)之間。
因為二叉排序樹是在zhi查詢過程中dao，當樹中不存內在關鍵字等於給定值的結容點時再進行插入。新插入的結點一定是乙個新新增的葉子結點，並且是查詢不成功時查詢路徑上訪問的最後乙個結點的左孩子或右孩子結點。
因此二叉排序樹插入時間複雜度最大為o(n)。若是二叉排序樹比較平衡，其時間複雜度下降，最小的時間複雜度為o(logn)。
演算法實現
效能分析
每個結點的c(i)為該結點的層次數。最壞情況下，當先後插入的關鍵字有序時，構成的二叉排序樹蛻變為單支樹，樹的深度為其平均查詢長度(n+1)/2(和順序查詢相同），
最好的情況是二叉排序樹的形態和折半查詢的判定樹相同，其平均查詢長度和log 2 (n)成正比。
7樓：匿名使用者
請上傳完整題目，很樂意為你解答，謝謝
資料結構，為什麼我記得二叉樹插入乙個結點的時間複雜度(o(n))
8樓：
因為二叉樹的機制是把較大的值放左邊較小值放右邊，所以插入和查詢跟對分查詢的機制是一樣的，平均複雜度是o（log n）。如果是平衡二叉樹那最壞次數是準確的 log n 次（以上log都是2為底）
（C語言）關於二叉排序樹的建立和查詢
include include typedef struct np node node create void node t node a,int d else if d a dat else if ddat return a void inorder node r int ser node so,...
具有結點的二叉樹可有多少種形態，具有四個結點的二叉樹可有多少種形態
幻雪狼狐 根據 卡特蘭數 公式 f n 2 n n n 1 為階乘。所以 f 4 14。具有4個節點的二叉樹有14中形態。 設具有n個節點的二叉樹的形態有f n 種，則f 0 0，f 1 1 具有四個節點的二叉樹，包含一個根節點與3個子節點，可以分以下幾類 左子樹0個節點，右子樹3個節點，此時二叉樹...
嚴蔚敏版本的資料結構中的二叉排序樹中刪除節點時重接Q的左右子樹的方法為何有選擇語句
濮方雅 因為有可能該刪除的節點下面的左子樹沒有右子樹的情況。如下 其中o是待刪除的節點，o 下面有左右子樹l r，但l下面沒有右子樹，這種情況下，直接把l的左子樹，也就是a提上來即可 a 在點p的左右子樹同時存在時，程式要用左子樹中的最大的元素，即p的左子樹中最右邊的元素替代p。while迴圈的用途...