堆
? ?堆也被稱為優(yōu)先隊(duì)列，隊(duì)列是先進(jìn)先出，隊(duì)尾插入，隊(duì)頭刪除，而堆也是堆底插入，堆頂刪除。
棧
? ? 棧先進(jìn)后出，棧頂插入和刪除。它是一種運(yùn)算受限的線性表。
隊(duì)列
? ??隊(duì)列是先進(jìn)先出，隊(duì)尾插入，隊(duì)頭刪除。動(dòng)態(tài)的創(chuàng)建，動(dòng)態(tài)是否，因而不存在溢出問題。
散列表
????又稱哈希表，是把關(guān)鍵碼根據(jù)映射函數(shù)映射到表中一個(gè)地址中，以加快查找速度。
? ? 散列地址沖突
? ? ? ? 是因?yàn)槎鄠€(gè)關(guān)鍵碼的映射地址相同。
? ? 解決方法? ? ? ? ? ??
? ? ? ? ?開放地址法：出現(xiàn)沖突，順序的尋找寫一個(gè)地址是否沖突，不沖突則放入，否則，繼續(xù)向下尋找。
? ? ? ? ? 鏈地址法：每個(gè)哈希地址單元為一個(gè)同義鏈表，來維護(hù)相同地址的關(guān)鍵碼。
二叉樹
? ? ? ? ? 第i層最大為2^（i-1），深度為k的二叉樹最多有2^k-1? 個(gè)結(jié)點(diǎn)，n個(gè)結(jié)點(diǎn)高度至少log2(n+1)。任一棵二叉樹，n0=n2+1。
? ? ? ? ? 前序遍歷：
? ??????????//二叉樹前序遍歷遞歸
void?PreOrder(TreeNode*?root)
{
????if(root)
????{
????????cout?<<?root->val?<<?endl;
????????PreOrder(root->left);
????????PreOrder(root->right);
????}
}
//二叉樹前序遍歷非遞歸
void?PreOrder(TreeNode*?root)
{
????stack<TreeNode*>?s;
????while(root?!=?nullptr?||?!s.emtpy())
????{
????????if(root)
????????{
????????????s.push(root);
????????????cout?<<?root->val?<<?endl;
????????????root?=?root->left;
????????}
????????else
????????{
????????????root?=?s.top();
????????????s.pop();
????????????if(root)
????????????{
????????????????root?=?root->right;
????????????}
????????}
????}
}
? ? ? ? ? ? 中序遍歷：
//二叉樹中序遍歷遞歸
void?InOrder(TreeNode*?root)
{
????if(root)
????{
????????InOrder(root->left);
????????cout?<<?root->val?<<?endl;
????????InOrder(root->right);
????}
}
//二叉樹中序遍歷非遞歸
void?InOrder(TreeNode*?root)
{
????stack<TreeNode*>?s;
????????while(root)
????????{
????????????s.push(root);
????????????root?=?root->left;
????????}
????????if(!s.empty())
????????{
????????????root?=?s.top();
????????????cout?<<?root->val?<<?endl;
????????????s.pop();
????????????if(root)
????????????{
????????????????root?=?root->right;
????????????}
????????}
}
? ? 后序遍歷：
//二叉樹后序遍歷遞歸
void?PostOrder(TreeNode*?root)
{
????if(root)
????{
????????PostOrder(root->left);
????????PostOrder(root->right);
????????cout?<<?root->val?<<?endl;
????}
}
//二叉樹后序遍歷非遞歸
void?PostOrder(TreeNode*?root)
{
????TreeNode*?cur;
????TreeNode*?pre?=?nullptr;
????stack<TreeNode*>?s;
????????if(root)
????????{
????????????s.push(root);
????????}
????????while(!s.empty())
????????{
????????????cur?=?s.top();
????????????if(cur->left?==?nullptr?&&?cur->right?==?nullptr?||?pre?&&?(cur->left?==?pre?||?cur->right?==?pre))
????????????{
????????????????cout?<<?cur->val?<<?endl;
????????????????pre?=?cur;
????????????????s.pop();
????????????}
????????????else
????????????{
????????????????if(cur->right)
????????????????{
????????????????????s.push(cur->right);
????????????????}
????????????????if(cut->left)
????????????????????s.push(cur->left);
????????????}
????????}
}
? ? ? ? 層次遍歷：
//層次遍歷
void?LevelOrder(TreeNode*?root)
{
????if(root?==?nullptr)
????????return;
????queue<TreeNode*>?q;
????if(root)
????????q.push(root);
????while(!q.empty())
????{
????????TreeNode*?tmp?=?q->front();
????????cout?<<?tmp->val?<<?endl;
????????q.pop();
????????if(tmp->left)
????????{
????????????q.push(tmp->left);
????????}
????????if(tmp->right)
????????{
????????????q.push(tmp->right);
????????}
????}
}
二叉查找樹：
? ? ? ? 又稱二叉搜索樹,二叉排序樹。即中序遍歷有序，若左子樹不空，則左子樹的值都小于根結(jié)點(diǎn)的值，若右子樹不空，右子樹的值都大于根結(jié)點(diǎn)，不存在值相同的結(jié)點(diǎn)。
完全二叉樹：
? ? ? ? 只有最小兩層的結(jié)點(diǎn)度小于2，且全都左連續(xù)。
平衡二叉樹：
? ? ? ? 每個(gè)結(jié)點(diǎn)的左子樹和右子樹高度差不超過1。
b 樹、b+ 樹
??????? 首先 b 樹屬于多叉樹又名平衡多路查找樹
其規(guī)則是
所有節(jié)點(diǎn)關(guān)鍵字是按遞增順序排列，并遵循左小右大規(guī)則
子節(jié)點(diǎn)數(shù)，非葉子節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)大于 1 且小于 M，且 M > 2，空樹除外
關(guān)鍵字?jǐn)?shù)，枝接點(diǎn)的關(guān)鍵字?jǐn)?shù)量大于等于 ceil(m/2)-1 個(gè)且小于等于 M-1 個(gè)(注：ceil() 是個(gè)朝正無窮方向取整的函數(shù)，比如 ceil(1,1) = 2)
葉節(jié)點(diǎn)的指針為空且葉節(jié)點(diǎn)具有相同的深度
????????而對于 b+ 樹，是 b 樹的一個(gè)升級版，相對于 b 樹而言 b+ 樹更充分利用了節(jié)點(diǎn)的空間，讓查詢速度更加穩(wěn)定，其速度完全接近二分查找。
紅黑樹：
? ? ? ? 一種特殊的二叉查找樹。
? ? ? ?特性：
? ? ? ? ? ? 1、每個(gè)結(jié)點(diǎn)非紅即黑。
? ? ? ? ? ? 2、根結(jié)點(diǎn)黑色。
? ? ? ? ? ? 3、每個(gè)葉子結(jié)點(diǎn)黑色。
? ? ? ? ? ? 4、若結(jié)點(diǎn)為紅色，其子節(jié)點(diǎn)為黑色。
? ? ? ? ? ? 5、從一個(gè)結(jié)點(diǎn)到該子孫結(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑結(jié)點(diǎn)。
? ? ? ? ?紅黑樹的基本操作
紅黑樹的基本操作是添加、刪除，在對紅黑樹進(jìn)行添加刪除之后，都會(huì)用到旋轉(zhuǎn)方法(之所以要進(jìn)行旋轉(zhuǎn)，是因?yàn)橐诓迦雱h除后還必須滿足紅黑樹的性質(zhì))
? ??????????左旋
? ? ? ? ? ? 右旋
紅黑樹如何進(jìn)行插入刪除？
插入
如果父節(jié)點(diǎn)為黑色，直接插入不處理
如果父節(jié)點(diǎn)為紅色，叔叔節(jié)點(diǎn)為紅色，則父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)變?yōu)楹谏?，祖先?jié)點(diǎn)變?yōu)榧t色，將節(jié)點(diǎn)操作轉(zhuǎn)換為祖先節(jié)點(diǎn)
如果當(dāng)前節(jié)點(diǎn)為父親節(jié)點(diǎn)的右節(jié)點(diǎn)，則以父親結(jié)點(diǎn)為中心左旋操作
如果當(dāng)前節(jié)點(diǎn)為父親節(jié)點(diǎn)的左節(jié)點(diǎn)，則父親節(jié)點(diǎn)變?yōu)楹谏嫦裙?jié)點(diǎn)變?yōu)榧t色，以祖先節(jié)點(diǎn)為中心右旋操作
刪除
先按照排序二叉樹的方法，刪除當(dāng)前節(jié)點(diǎn)，如果需要轉(zhuǎn)移即轉(zhuǎn)移到下一個(gè)節(jié)點(diǎn)
當(dāng)前節(jié)點(diǎn)，必定為這樣的情況：沒有左子樹。
刪除為紅色節(jié)點(diǎn)，不需要處理，直接按照刪除二叉樹節(jié)點(diǎn)一樣
如果兄弟節(jié)點(diǎn)為黑色，兄弟節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)為黑色，則將兄弟節(jié)點(diǎn)變?yōu)榧t色，將著色轉(zhuǎn)移到父親節(jié)點(diǎn)
如果兄弟節(jié)點(diǎn)為紅色，將兄弟節(jié)點(diǎn)設(shè)為黑色，父親結(jié)點(diǎn)設(shè)為紅色節(jié)點(diǎn)，對父親結(jié)點(diǎn)進(jìn)行左旋操作
如果兄弟節(jié)點(diǎn)為黑色，左孩子為紅色，右孩子為黑色，對兄弟節(jié)點(diǎn)進(jìn)行右旋操作
如果兄弟節(jié)點(diǎn)為黑色，右孩子為紅色，則將父親節(jié)點(diǎn)的顏色賦值給兄弟節(jié)點(diǎn)，將父親節(jié)點(diǎn)設(shè)置為黑色，將兄弟節(jié)點(diǎn)的右孩子設(shè)為黑色，對父親節(jié)點(diǎn)進(jìn)行左旋
紅黑樹、b 樹、b+ 樹區(qū)別
紅黑樹的深度比較大，而B+和B-的深度則相對要小一些，而B+較B-則將數(shù)據(jù)都保存在葉子節(jié)點(diǎn)，同時(shí)通過鏈表的形式將他們連接在一起。
