查找問題中的算法

編者按：教育部頒布的《普通高中信息技術課程標準（2017年版）》在“必修模塊1”中用專門的單元談論了算法，這說明，新課程要求高中信息技術在教學中應當以算法為要旨，強化算法的重要性。

本刊從本期起開設“算法園地”專欄，特邀北京大學計算機系原系主任李曉明教授、南京大學計算機系原系主任陳道蓄教授撰寫有關算法的文章，為讀者提供一些既有思想性又有實用性的材料。

專欄的讀者定位是對算法問題有興趣的中小學教師，內容的鋪陳將努力做到通俗性、趣味性和嚴謹性相結合。每月介紹一個算法，每期獨立成篇，大體按照以下六個方面展開：應用背景、算法描述、實例模擬、性質分析、思考問題、參考代碼。你以前如果學過算法，在這里會看到一種不同的視野;你以前如果沒有學過算

法，則可以通過對每月一個算法的學習，既領悟到算法思想的精髓，又形成算法實戰的能力。

現實生活中，每個人都有需要在一堆東西里找出某件特定物品的經歷。一番努力后，可能找到，也可能沒找到。此外，當我們新得到某件物品（如一本書）時，有時也會為把它在放在什么位置而糾結，希望將它放到一個今后找起來方便的地方。

計算機中與這種生活現象對應的，就是對數據的兩種基本操作：“查找”（search）和“插入”（insert）。選擇適當位置插入的目的主要就是便于今后的查找。查找和插入操作，其本身有直接的應用，同時也是計算機中許多其他復雜操作和功能的基礎。由于其基礎性，計算機科學家有不少專著對它們進行了系統介紹，最經典的是Donald Knuth的The Art of Computer Programming Vol. 3： Sorting and Searching，其中用了190頁來討論查找算法。

一般來說，討論查找和插入操作，我們總是面對一個數據元素集合A={a1，a2，…，an}和一個數據元素x，問x是否在A中。當發現x不在A中的時候，如果需要的話，則把x放入A中。

這樣的操作，如果十分頻繁，且隨著時間的積累A變得很大（如n>109）的時候，效率就是值得重視的一個問題了。關鍵歸納為兩點，一是如何組織A中的數據，二是如何平衡查找和插入操作之間的效率。后面這一點即是說，如果預計查找是頻繁的，插入是稀少的，則可以在插入操作上花更多的時間，以換取查找上時間的減少。而關于A中數據的組織，在計算機中涉及采用不同數據結構的考量，也是本文展開的線索。具體來說，下面安排有四個小節：（1）無序元素列表上的查找與插入;（2）有序元素列表上的查找與插入;（3）搜索二叉樹上的查找與插入;（4）平衡二叉樹上的查找與插入。

● 無序元素列表上的查找與插入

這是最基本也是最簡單的一種情況。集合A={a1，a2，…，an}的元素任意放在一個列表（Python）或數組A中，對于需要查找的數據元素x，執行如圖1所示的算法。

算法邏輯直截了當，挨個和A的元素比較，發現了有相等的就報告成功;若比較完了還沒看到x，就報告失敗，接著把x放到A的末尾（插入操作）。

可見，這里的插入操作很簡單，O（1）。但查找操作最壞的情況需要做n次比較，即O（n），適合插入較多（即新元素較多）、查找較少的應用場合。

● 有序元素列表上的查找與插入

當查找很頻繁，且n很大時，實質性地減少查找需要的計算量就變得很有意義了。腦筋就動在數據的組織上，即要讓A的元素按某種特定方式組織，便利查找的過程。一種簡單的方式就是讓它的元素有序，從而可以支持所謂“對分查找”的算法。原理很直觀，就是利用列表元素有序（不妨設增序）的特點，如果發現x

算法用low和high控制需要查找的范圍，每次通過mid=（low+high）//2確定“中點”（所謂“對分查找”由此而來），在偶數個元素的場合則是取中間靠左的一個。如果x和A[mid]不相等，就需要移動low或者high，對應的“mid+1”和“mid-1”保證了查找范圍總是應該包含low和high指示的元素，與初值設定的含義一致。

如果某次比較相等，就報告成功，結束。若x不在A中，最后一次比較對應high=low的情況，此時mid=low=high，若還不成功，等價地就是置low←high+1或者high←low-1，也就是while循環不再執行的條件。

報告失敗，把x插入到A中，不再像前面那么簡單了。需要有點講究，對應最后4行代碼，取決于最后一次比較時x小還是大，分別插入到mid的當前位置或后面，以保證A中元素的有序性。更重要的是，這里的插入要涉及后面元素的移動，對效率是有影響的。Python列表的插入操作對程序員屏蔽了那些數據的移動，但在程序運行中實際會發生。大多數編程語言都需要程序員在程序中表達數據移動的過程。

綜合起來，基于有序元素的列表，對分查找的查找效率高，得出判斷的復雜性是O（log2n），這與O（n）相比是實質性的提高。不過代價也是明顯的，即在沒找到又需要插入的時候，最壞情況下要在列表上往后移動n個數據，即O（n），適合查找較多、插入較少（即新元素較少）的應用場合。

● 搜索二叉樹上的查找與插入

前面介紹的兩種方法總的來說都比較簡單明了，各有千秋，也各有不足。有沒有辦法綜合它們的優點，避免它們的缺點呢？理想目標就是，判斷x是否存在于A中，希望能有O（log2n）的效率（類似于對分查找），而如果x不在A中，為插入x涉及的數據移動操作為常數量級[類似于順序查找中的A.append（x）]。

采用二叉樹數據結構是實現這一追求的基本途徑。二叉樹是一種重要的數據結構，核心概念為“樹根”“左子樹”“右子樹”和“遞歸定義”。我們假設讀者對它已有所了解，圖3所示為幾個例子。

在應用中，二叉樹中的節點常用于存放數據。當我們將數據之間的大小關系與樹中節點的結構性關系做某種對應的時候，就可能導致令人興奮的算法結果。搜索二叉樹（亦稱“查找二叉樹”）就是這方面的一個例子。

上述“數據之間的大小關系與樹中節點的結構性關系”的對應，在搜索二叉樹上即是：根節點的數值不小于左子樹節點的值，不大于右子樹節點的值。在圖3中，（a）和（c）是搜索二叉樹，（b）和（d）則不是。

這樣的搜索二叉樹對我們的查找任務有什么好處呢？仔細體會一下，它與二分查找的精神十分相近。當我們把數據集合A的元素按照搜索二叉樹的要求放好之后，查找x是否在A中，就是從根節點開始比較，如果x較小，則意味著它比右子樹的所有節點都要小，不用再去查了（相當于對分查找中不用再關注mid右邊的元素），只需關注左子樹就可以了（相當于圖2中做的high=mid-1）。

如果查找失敗，需要把x插入到A中，如何保證能插入到正確的位置呢？在前面討論對分查找的時候，我們已經明確將新元素插入到數據集合的適當位置是一件需要仔細確定的事情，目的就是要保證得到的數據結構具有相同的性質。在那里，就是元素之間的順序，在這里，就是搜索二叉樹的要求。

我們注意到，查找不成功的結論總是出現在與二叉樹中某個節點a比較不相等，按規則不能再進展之時（a可能是葉節點，也可能是一邊子樹為空的非葉節點），如果xa的情形類似。

這樣做達到本小節提出的目標了嗎？注意到n個節點的二叉樹的高度最低可達log2n，這意味著查找效率可能做到O（log2n）。同時我們也看到，這里的插入操作很簡單，即在查找不成功的時候在當前節點上生成一個子節點，效率就是常數量級的，O（1）。一個十分接近可執行程序段的偽代碼描述如上頁圖4所示。

如此，查找問題似乎就圓滿解決了。采用搜索二叉樹作為數據結構，既可能得到查找的高效率，也有插入的高效率。然而，依然還有一個潛在的問題，那就是上述方法不能保證二叉樹的高度為O（log2n）。事實上，大量如上所述的簡單插入操作很容易導致一棵“病態的”二叉樹，其高度不是log2n，而是更接近n，從而無法體現其優勢了。下一節的內容即是針對這種問題的一個解決方案。

● 平衡二叉樹上的查找與插入

目標很明確，就是希望讓二叉樹的高度總保持在log2n量級。途徑也清楚，就是允許插入操作適當復雜一些，每當完成插入的時候，不僅要保持搜索二叉樹節點間的數值關系正確，還要根據需要對二叉樹的結構做平衡調整，保證每一個節點左右子樹的高度之差不超過1。我們稱這樣的二叉樹為“平衡二叉樹”。

以圖3中的4棵二叉樹為例，（c）就是不平衡的，因為節點3的左子樹高度為0，右子樹的高度為2，高度差超過了1。我們同時注意到，（a）是一棵平衡二叉樹，它的內容和（c）完全一致，結構上則有局部調整（節點6的左子樹）。如何在發現（c）的情況出現時做代價不大的調整以達到（a）的結果，就是我們要討論的問題。下面通過一個例子來學習一種方法。

以一棵平衡二叉樹為基礎，按照前述搜索二叉樹的方式，在插入一個新節點后，每一個節點將具有如下五種狀態之一：（1）兩棵子樹的高度一樣，稱為完全平衡，用0表示。（2）左子樹高度比右子樹高1，稱為左沉（但依然平衡），用-1表示。（3）右子樹高度比左子樹高1，稱為右沉（但依然平衡），用+1表示。（4）左子樹高度比右子樹高2，稱為左失衡，用-2表示。（5）右子樹高度比左子樹高2，稱為右失衡，用+2表示。

以圖3（c）為例，對應節點6、3、7、5、9、4，就有-1、+2、+1、-1、0、0。而在圖3（a）中，節點7的狀態為+1，其他節點狀態都是0。顯然，插入一個節點后，若每個節點都處于0、-1或+1狀態，就不需要做任何事情。調整發生在有節點的狀態變成了-2或+2時。

如果一個節點（X）的狀態變成了+2（-2的情況對稱，只需要把下面兩點描述中的“左”和“右”互換即可，此處從略），有兩種情況需要考慮。

第一種情況，若X失衡的原因是其右子樹的右子樹上插入了一個節點，則令X的右兒子（Y）為根，令X為Y的左兒子，同時令Y原先的左子樹為X的右子樹。這個操作稱為“左旋”。

第二種情況，若X失衡的原因是其右子樹的左子樹上插入了一個節點[對應圖3（c）中的節點3]，那就先以右兒子（Y）為軸做一個“右旋”，讓它的左兒子“上位”（成為這棵子樹的根節點，即占據原來節點5的位置），接著再以X為軸做一個左旋。圖3（c）據此操作后即得圖3（a）。

按照這種方法得到的二叉搜索樹（平衡二叉樹）稱為“AVL樹”注，也是最早（1962年）被發明出來的一種平衡二叉樹，它保證了樹高為O（log2n），于是前面提到的“病態”情況不再出現，查找操作的效率得以保持為O（log2n）。其代價則是要記錄節點的平衡狀態（包括增加了數據結構的復雜性和每次插入一個節點后的狀態更新），以及根據狀態做上述平衡調整。其中，平衡調整本身是常數量級的操作，但節點平衡狀態維護的計算量是和樹高log2n成比例的。綜上所述，對于帶插入功能的查找操作，我們可以得出結論：（1）基于列表的效率為O（n），無論元素有序還是無序;（2）采用搜索二叉樹，理想效率為O（log2n），但很可能做不到;（3）而采用AVL樹，效率保證為O（log2n）。

前面，我們分四小節討論了查找問題，它們之間除了在目標追求上有遞進的關系外，還展示了一種技術上的共性，即在算法過程中始終要保證數據結構上某種性質的滿足。在對分查找中，要保證列表元素的有序;在搜索二叉樹查找中，要保證任何時候都滿足搜索二叉樹上節點位置與元素值大小的特定關系;在平衡二叉樹查找中，則除了搜索二叉樹的性質外，還要保證二叉樹的平衡。如果這些性質不能得到一致的保證，算法就失去了正確的基礎，一些計算代價正是為得到這些保證而付出的。

參考文獻：

[1]Donald Knuth.The Art of Computer Programming， Second Edition， Vol 3[M].Addison-Wesley，1998.

[2]鄧俊輝.數據結構（第3版）[M].北京：清華大學出版社，2018.

注：AVL由兩位發明人Georgy Adelson-Velsky和Evgenii Landis的姓氏頭字母組合而成。