一、叉排序樹的ASL

叉排序樹的ASL是平均查找長度，在查找運算中，由于所費時間在關鍵字的比較上，所以把平均需要和待查找值比較的關鍵字次數稱為平均查找長度。一個算法的ASL越大，說明時間性能差，反之，時間性能好，這也是顯而易見的。

在順序查找(Sequence Search)表中，查找方式為從頭掃到尾，找到待查找元素即查找成功，若到尾部沒有找到，說明查找失敗。所以說，Ci（第i個元素的比較次數）在于這個元素在查找表中的位置，如第0號元素就需要比較一次，名列前茅號元素比較2次……第n號元素要比較n+1次。

折半查找(Binary Search)，首先待查找表是有序表，這是折半查找的要求。在折半查找中，用二叉樹描述查找過程，查找區間中間位置作為根，左子表為左子樹，右子表為右子樹，，因為這顆樹也被成為判定樹(decision tree)或比較樹(Comparison tree)。查找方式為(找k)，先與樹根結點進行比較，若k小于根，則轉向左子樹繼續比較，若k大于根，則轉向右子樹，遞歸進行上述過程，直到查找成功或查找失敗。在n個元素的折半查找判定樹中，由于關鍵字序列是用樹構建的，所以查找路徑實際為樹中從根節點到被查結點的一條路徑，因為比較次數剛好為該元素在樹中的層數。

哈希表中的ASL查找成功的平均查找長度是指查找到哈希表中已有關鍵字的平均探測次數。而查找不成功的平均查找長度是指在哈希表中找不到待查的元素，最后找到空位置元素的探測次數平均值。

延伸閱讀：

二、BFS的過程是什么

BFS的過程是首先訪問起始結點v，接著訪問頂點v的所有未被訪問的鄰接結點，然后對每個繼續進行上述步驟，直到所有結點都被訪問過為止，當然，在訪問過程中，需要使用一個隊列，然后類似二叉樹的層次遍歷來訪問。

BFS通俗的來講，就如通病毒擴散一般蔓延。往往采用BFS求解迷宮問題的入口到出口的最短路徑。