前言
樹是數(shù)據(jù)庫系統(tǒng)領(lǐng)域最重要的數(shù)據(jù)結(jié)構(gòu)之一，例如：Mysql中索引結(jié)構(gòu)是B+樹低滩，Hbase的底層結(jié)構(gòu)是LSM樹（Log Structure Tree）是Hbase底層檢索的數(shù)據(jù)結(jié)構(gòu)，紅黑樹是Java8里HashMap的底層數(shù)據(jù)結(jié)構(gòu)粪狼，哈弗曼樹在編碼和壓縮領(lǐng)域有著重要的應(yīng)用电抚。
樹在計(jì)算機(jī)里應(yīng)用廣泛，所以樹結(jié)構(gòu)無論是面試蔗衡、考研纤虽，還是工作、自學(xué)都會用到绞惦。
常見的樹介紹
二叉查找樹（BST）
二叉排序樹或者是一棵空樹逼纸，或者是具有下列性質(zhì)的二叉樹：
（1）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值翩隧；
（2）若右子樹不空樊展，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
（3）左堆生、右子樹也分別為二叉排序樹专缠；
（4）沒有鍵值相等的節(jié)點(diǎn)（因此，插入的時(shí)候一定是葉子節(jié)點(diǎn)）涝婉。
插入有序節(jié)點(diǎn)，退化成單支樹
1.查找效率最好O(logn)蔗怠，最壞O(n)
2.插入效率和查找效率相同（只插入葉子節(jié)點(diǎn)）
3.刪除效率最好O(logn)+O(1)->只有左子樹或者右子樹
最差O(logn)+O(logn)->左子樹和右子樹同時(shí)存在
二叉搜索樹.JPG
AVL樹-自平衡二叉查找樹
AVL樹本質(zhì)上是一顆二叉查找樹，但是它又具有以下特點(diǎn)：它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對值不超過1渔工，并且左右兩個(gè)子樹都是一棵平衡二叉樹。在AVL樹中任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差別為一桥温，所以它也被稱為平衡二叉樹。下面是平衡二叉樹和非平衡二叉樹對比的例圖：
AVL樹.png
