??陣列查詢的效率很高但是添加和洗掉的效率會很低，鏈表的添加和洗掉的效率很高但是查詢的效率又很低，這時有沒有更好的選擇方案呢？這時二叉樹出現了，
二叉樹
1 相關概念
??? 二叉樹：每個子節點只有兩個節點的樹，每個結點至多擁有兩棵子樹(即二叉樹中不存在度大于2的結點)，并且，二叉樹的子樹有左右之分，其次序不能任意顛倒，
二叉查找樹也稱為有序二叉查找樹,滿足二叉查找樹的一般性質,是指一棵空樹具有如下性質：
-
任意節點左子樹不為空,則左子樹的值均小于根節點的值
-
任意節點右子樹不為空,則右子樹的值均大于于根節點的值
-
任意節點的左右子樹也分別是二叉查找樹
-
沒有鍵值相等的節點
二叉樹又分為：完美二叉樹，完全二叉樹，完滿二叉樹
完美二叉樹：又稱為滿二叉樹，除了葉子節點之外的每一個節點都有兩個孩子節點，每層都被完全填充
完全二叉樹:除了最后一層之外的其他每一層都被完全填充，并且所有的節點都保持向左對齊
完滿二叉樹：除了葉子節點之外的每一個節點都有兩個孩子節點，
2 遍歷操作
??二叉樹中的遍歷規則有如下三種：
中序遍歷：所謂的中序遍歷就是先訪問左節點，再訪問根節點，最后訪問右節點，即左-根-右遍歷
先序遍歷：所謂的前序遍歷就是先訪問根節點，再訪問左節點，最后訪問右節點，即根-左-右遍歷(前序)
后序遍歷：所謂的后序遍歷就是先訪問左節點，再訪問右節點，最后訪問根節點，即左-右-根遍歷
查找最小值：沿著根節點的左子樹一路查找，直到最后一個不為空的節點，該節點就是當前這個樹的最小節點
查找最大值：沿著根節點的右子樹一路查找，直到最后一個不為空的節點，該節點就是當前這個樹的最大節點
查找前驅節點：小于當前節點的最大值
查找后繼節點：大于當前節點的最小值
3 洗掉節點
??二叉樹中的洗掉節點：本質上是找前驅節點或者后繼節點來替代
- 葉子節點直接洗掉
- 只有一個子節點的用子節點替代(本質上就是找的前驅節點或者后繼節點，左節點就是前驅節點，右節點就是后繼節點)
- 有兩個子節點的，需要找到替代節點(替代節點就是前驅節點或者后繼節點)
4 查找局限性
? ?? 一個二叉查找樹是由n個節點隨機構成,所以，對于某些情況,二叉查找樹會退化成一個有n個節點的線性鏈.如下圖
AVL
??BST存在的問題是，樹在插入的時候會導致傾斜，不同的插入順序會導致數的高度不一樣，而樹的高度直接影響了樹的查找效率，最壞的情況所有的節點都在一條斜線上，這樣樹的高度為N，基于BST存在的問題，平衡查找二叉樹（Balanced BST）產生了，平衡樹的插入和洗掉的時候，會通過旋轉操作將高度保持在LogN，其中兩款具有代表性的平衡術分別為AVL樹（高度平衡樹，具備二叉搜索樹的全部特性，而且左右子樹高度差不超過1）和紅黑樹，
??AVL樹是如何實作平衡的呢？，具體是通過左旋或者右旋來實作的，具體如下圖：
??雖然AVL可以解決二叉樹所存在的問題，但是AVL樹要求太過嚴格，左旋和右旋的開銷會比較大，這時出現了紅黑樹，只要求黑色節點平衡即可，下篇我們介紹紅黑樹！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/287604.html
標籤：java
上一篇：java知識點復習