8.5 二叉排序樹
有序線性表在查找時很方便，但是插入和刪除操作，會消耗大量的時間，因為插入和刪除後，為了保持線性有序，會移動大量的數據。可以用二叉排序樹來解決這個問題。
二叉排序樹，又稱為二叉查找樹。它或者是一棵空樹，或者具有下列性質的二叉樹：
1）若它的左子樹存在，則左子樹上所有節點的值均小於它的根節點的值；
2）若它的右子樹存在，則右子樹上所有節點的值均大於它的根節點的值；
3）它的左、右子樹也分別為二叉排序樹。
構造二叉排序樹的目的，並不是為了排序，而是為了提高查找和插入或刪除關鍵字的速度。
二叉排序樹以鏈接的方式存儲，保持了鏈接存儲結構在執行插入或刪除操作時不用移動元素的有點，只要找到合適的插入和刪除位置後，僅需要修改鏈接指針即可。
8.6 平衡二叉樹
在構造二叉排序樹的時候，是按數組中元素依次構造的，使其滿足二叉樹的性質，對於一個正序排列的數組，構造二叉樹的時候，會成為右斜的二叉樹，沒有左子樹，這樣會影響查找效率。所以構建平衡二叉樹。
平衡二叉樹：是一種二叉排序樹，其中每一個節點的左子樹和右子樹的告訴差至多等於1。
構造原理：每當插入一個節點時，先檢查是否因為插入破壞了樹的平衡性，若是，則找出最小不平衡樹，在保持二叉排序樹的前提下，調整最小不平衡子樹中各節點之間的鏈接關系，進行相應的旋轉，使之成為新的平衡樹。
本文出自 “李海川” 博客，請務必保留此出處http://lihaichuan.blog.51cto.com/498079/1282363
