1樓:匿名使用者
2lnn 大概是 1.39lgn
2樓:匿名使用者
少年你是做作業麼......
關於資料結構二分法查詢成功的平均查詢長度和失敗的查詢長度
3樓:匿名使用者
做這種題目的時候,應該畫出二叉樹。然後把葉子補足。葉子的高度就是查詢失敗的次數。
然後求和除以葉子數目就是失敗的平均查詢長度。而非葉子節點就是成功的,高度就是成功的查詢次數,然後除以非葉子節點的數目,就是成功的平均長度。
對於11個節點,其構成的二叉樹成功的查詢長度是(1x1+2x2+3x4+4x4)/11=33/11失敗的查詢長度是
(4x8+3x4)/(8+4)=44/12
平衡二叉樹平均比較次數和最多比較次數一樣嗎
4樓:世界文明導師
是的,因為如果平衡二叉樹t有x個節點,就會有[ log2(x) ] + 1層,在插入操作時就要平均進行 log2(x) (不包括常數項和係數)次操作【雖然如果插入資料等於根節點,就只需要進行2次操作(!(a < b) && !(b < a) 與 a == b 等價),但畢竟在元素個數無窮多的實數或整數集中,a == b的概率為 a / +∞ = 0,所以我們只考慮插入資料 x ∉ |t| 的情況】,顯而易見地,最多比較次數也只有log2(x) (不包括常數項和係數)。
當然,平均比較次數還很大程度上依賴於資料範圍,如果是在1~1000的整數內構造有400個節點的平衡二叉樹,那麼插入重複資料的概率就很大了,平均比較次數就會小於log2(x) (不包括常數項和係數)。
什麼是二叉樹,舉二叉樹的例子，什麼是二叉樹,舉一個二叉樹的例子
二叉樹樹是一種重要的非線性資料結構，直觀地看，它是資料元素 在樹中稱為結點 按分支關係組織起來的結構，很象自然界中的樹那樣。樹結構在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可用樹形象表示。樹在計算機領域中也得到廣泛應用，如在編譯源程式如下時，可用樹表示源源程式如下的語法結構。又如在資...
二叉樹有n個度為2的節點，該二叉樹中葉子結點個數為多少
n 1。解題過程 一 對任何一棵二叉樹t,如果其終端節點數為n0,度為2的節點數為n2,則n0 n2 1.二 設n1為二叉樹t中度為1的結點數 三 因為二叉樹中所有結點的度軍小於或等於2,所以其結點總數為 n n0 n1 n2 1 再看二叉樹中的分支數.除了根結點外，其餘結點都有一個分支進入，設b為...
堆和二叉樹的區別堆個二叉樹的區別
在二叉排序樹中，每個結點的值均大於其左子樹 上所有結點的值，小於其右子樹上所有結點的值，對二叉排序樹進行中序遍歷得到一個有序序列。所以，二叉排序樹是結點之間滿足一定次序關係的二叉樹 堆是一個完全二叉樹，並且每個結點的值都大於或等於其左右孩子結點的值 這裡的討論以大根堆為例 所以，堆是結點之間滿足一定...