
9-10平衡樹
由於二元搜尋樹的缺點是無法永遠保持在最佳狀態。當加入之資料部分以排序的情況下,極有可能產生歪斜樹,因而使樹的高度增加,導致搜尋效率降低。所以二元搜尋樹較不利於資料的經常變動(加入或刪除)。為了能夠盡量降低搜尋所需要的時間,讓我們在搜尋的時候能夠很快找到所要的鍵值,我們必須讓樹的高度越小越好。
所謂平衡樹(Balance Binary Tree),又稱之為AVL樹(是由Adelson-Velskii 和 Landis兩人所發明的),本身也是一棵二元搜尋樹,在AVL樹中,每次在插入資料和刪除資料後,必要的時候會對二元樹做一些高度的調整動作,而這些調整動作就是要二元搜尋樹的高度隨時維持平衡。T是一個非空的二元樹,Tl及Tr分別是它的左右子樹,若符合下列兩條件,則稱T是個高度平衡樹:



至於如何調整一二元搜尋樹成為一平衡樹,最重要找出(不平衡點),再依照以下四種不同旋轉型式,重新調整其左右子樹的長度。首先,令新插入的節點為N,且其最近的一個具有+-2的平衡因子點為A,下一層為B,再下一層C,分述如下:



現在我們來實作一個範例,下圖的二元樹,下圖的二元樹原是平衡的,加入節點12後變為不平衡,請重新調整成平衡樹,但不可破壞原有的次序結構:


9-11決策樹的智慧
我們也常把決策樹(Decision Tree)稱為(遊戲樹),這是因為遊戲中的AI經常以決策樹資料結構來實作的緣故。對資料結構而言,決策樹本身是人工智慧(AI)中一個重要理念,在資訊管理系統(MIS)中,也是決策支援系統(Decision Support System,DSS)的執行基礎。
簡單來說,決策樹是一種利用樹狀結構的方法,來討論一個問題的各種情況分布的可能性。例如最典型的(8枚金幣)問題來闡釋決策樹的觀念,內容是假設有8枚金幣a,b,c,d,e,f,g,h且其中有一枚是儰造的,儰造金幣的特徵為重量稍輕或偏重。請問如何使用決策樹方法,找出這枚儰造的錢幣;如果是以L表示輕於真品,H表示重於真品。第一次比較從8枚中挑選6枚a,b,c,d,e,f分2組來比較,則會有下列三種情形產生:
(a+b+c)>(d+e+f)
(a+b+c)=(d+e+f)
(a+b+c)<(d+e+f)
不過如果今天您要設計的遊戲並不是屬於(棋類)或是(紙牌類)的話,所採用的技巧在於實現遊戲作決策的能力,簡單的說,該下哪一步或者該出哪一張牌,因為通常可能的狀況有很多,例如象棋遊戲的人工智慧就必須在所有可能的情況中選擇一步對自己最有利的棋,想想看如果開發此類的遊戲,您會怎麼作?這時決策樹也可派上用場。
通常此類遊戲的AI實現技巧為先找出所有可走的棋(或可出的牌),然後逐一判斷如果走這步棋(或出這張牌)的優劣程度如何,或者說是替這步棋打個分數,然後選擇走得分最高的那步棋。
一個最常被用來討論決策型AI的簡單例子是(井字遊戲),因為它的可能狀況不多,也許您只要花個十分鐘便能分析完所有的狀況,並且找出最佳的玩法,例如下圖可表示某個狀況下的O方的決策樹:

上圖是井字遊戲的某個決策區域,下一步是X方下棋,很明顯的X方絕對不能選擇第二層的第二個下法,因為X方必敗無疑,而您也看出這個決策形成樹狀結構,所以也稱之為(決策樹),而樹狀結構正是資料結構所討論的範圍,這也說明了資料結構正是人工知會的基礎,而決定型人工智慧的基礎則是搜尋,在所有可能的狀況下,搜尋可能獲勝的方法。