今天看了輝哥的AVL樹的視頻，來給自己寫一篇總結(jié)誊册，強烈推薦輝哥是視頻领突，這個是輝哥是簡書地址http://www.reibang.com/u/35083fcb7747
一、AVL樹
1.定義
在AVL樹中任何節(jié)點的兩個子樹的高度最大差別為1案怯，所以被稱為高度平衡樹君旦。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個數(shù)
2.特點
（1）本身首先是一棵二叉搜索樹
（2）帶有平衡條件：每個節(jié)點的左右子樹的高度差的絕對值(平衡因子)最多為1，也就是說嘲碱，AVL樹金砍，本質(zhì)上是帶了平衡功能的二叉查找樹
二、旋轉(zhuǎn)
在每次插入數(shù)值后麦锯，樹的平衡有可能會被破壞捞魁，這時就可以通過旋轉(zhuǎn)操作來矯正平衡
所有的旋轉(zhuǎn)都是對子樹來操作
分類：左旋、右旋离咐、先左旋再右旋谱俭、先右旋再左旋
旋轉(zhuǎn)總結(jié).png
三奉件、插入
以案例來舉例插入
案例：3 2 1 4 5 6 7 10 9 8
1.先插入3
不需要旋轉(zhuǎn)操作
2.插入2
不需要旋轉(zhuǎn)操作
符合左左原則，右旋昆著，旋轉(zhuǎn)完為：
4.插入4
插入4县貌，符合AVL數(shù)特征，不進行旋轉(zhuǎn)調(diào)整
5.插入5
符合右右原則凑懂，左旋煤痕，旋轉(zhuǎn)完為：
6.插入6
符合右右原則，左旋接谨，旋轉(zhuǎn)完為：
7.插入7
符合右右原則摆碉，左旋，旋轉(zhuǎn)完為：
8.插入10
符合AVL樹脓豪，不需要調(diào)整
-
插入9
符合右左型巷帝，先右旋，再左旋
先右旋：
再左旋：
-
插入8
符合左右型扫夜，先左旋楞泼，再右旋
先左旋：
再右旋
案例講解就到這里啦，代碼在文章最末尾
四笤闯、刪除
刪除總結(jié)
還是以案例來舉例刪除
案例：3 2 1 4 5 6 7 10 9 8
1.刪除3堕阔，移除3，對整棵樹沒有影響颗味，不需要進行調(diào)整
2.刪除3之后在刪除1
移除1超陆，對4的高度有影響，需要調(diào)整浦马，
符合：刪除的是4的左子樹上的數(shù)據(jù)时呀，左旋(符合2)，并且不需要旋轉(zhuǎn)捐韩，最后調(diào)整結(jié)果為：
3.刪除4
原來的AVL樹
刪除的是根節(jié)點退唠，或者左右有一個或兩個節(jié)點鹃锈，為了保證它是一顆二叉搜索樹荤胁，需要從左邊或者右邊找一個節(jié)點來填補上去
判斷左右子樹的高度，哪個高度高屎债，去哪邊找仅政，不會影響平衡
左子樹：找最大值
右子樹：找最小值
案例中刪除4，找右子樹的最小值5
3.先刪除4盆驹，再刪除5
刪除4的圖就不上啦圆丹，看2就可以了，直接上刪除5的圖了
刪除5會把把6挪上來躯喇，導(dǎo)致不平衡
需要左旋辫封，最終圖為：
總結(jié)就到這里吧硝枉，直接把代碼放進來吧
//
// Created by v-weiya on 2020/2/13.
//
#ifndef NDK_TREENODE2_BST_H
#define NDK_TREENODE2_BST_H
#include <iostream>
#include <queue>
#include <android/log.h>
using namespace std;
template <class K,class V>
struct TreeNode{
public:
TreeNode<K,V>* left=NULL;
TreeNode<K,V>* right=NULL;
K key;
V value;
int height;//當前樹的高度
TreeNode(K key,V value):height(1){//初始節(jié)點的高度為1
this->right=NULL;
this->left=NULL;
this->key=key;
this->value=value;
}
TreeNode(TreeNode<K,V> *pNode):height(pNode->height){
this->right=pNode->right;
this->left=pNode->left;
this->key=pNode->key;
this->value=pNode->value;
}
};
template <class K,class V>
class AVL {
TreeNode<K,V>* root;//根節(jié)點
int count;//總結(jié)點數(shù)
public:
AVL(){
root=NULL;
count=0;
}
~AVL(){//析構(gòu)函數(shù)，需要自己完成
}
//中序遍歷,void (*fun)(K, V)回調(diào)函數(shù)
void inOrderTraverse(void (*fun)(K, V)) {
inOrderTraverse(root,fun);
}
//層序遍歷,void (*fun)(K, V)回調(diào)函數(shù)
void levelTraverse(void (*fun)(K, V)) {
if (root == NULL) {
return;
}
TreeNode<K,V> *node=root;
queue<TreeNode<K,V> *> nodes;
nodes.push(node);
while (!nodes.empty()) {
node=nodes.front();
fun(node->key,node->value);
nodes.pop();
if(node->left){
nodes.push(node->left);
}
if(node->right){
nodes.push(node->right);
}
}
}
public:
//新增(修改)
void put(K key,V value){
root=addNode(root,key,value);
}
//查找
V* get(K key){
return NULL;
}
int size(){
return count;
}
//刪除
void remove(K key){
//分情況解決
root=removeNode(root,key);
}
//是否包含
bool contains(K key){
TreeNode<K,V> *node=root;
while (node){
if(node->key==key){
return node->value;
} else if(node->key > key){
node=node->left;
} else{
node=node->right;
}
}
return false;
}
private:
//中序遍歷
void inOrderTraverse(TreeNode<K, V> *pNode, void (*pFunction)(K, V)) {
if(pNode==NULL){
return;
}
inOrderTraverse(pNode->left,pFunction);
pFunction(pNode->key,pNode->value);
inOrderTraverse(pNode->right,pFunction);
}
int getHeight(TreeNode<K, V> *pNode) {
return pNode? pNode->height:0;
}
//右旋
TreeNode<K, V> *R_Rotation(TreeNode<K, V> *pNode) {
TreeNode<K,V> *left=pNode->left;//原來的左孩子要變成跟節(jié)點
TreeNode<K,V> *right=left->right;//保留一下left的right
left->right=pNode;//left的右邊是原來的根節(jié)點
pNode->left=right;//原來的左孩子右孩子放到pNode的左邊
//更新高度
pNode->height=max(getHeight(pNode->left),getHeight(pNode->right))+1;
left->height=max(getHeight(left->left),getHeight(left->right))+1;
return left;
}
//左旋
TreeNode<K, V> *L_Rotation(TreeNode<K, V> *pNode) {
TreeNode<K,V> *right=pNode->right;//原來的右孩子要變成根節(jié)點
TreeNode<K,V> *left=right->left;//保留一下pNode的left
right->left=pNode;//right的左邊是原來的根節(jié)點
pNode->right=left;//原來的右孩子的左孩子放到pNode的右邊
//更新高度
pNode->height=max(getHeight(pNode->left),getHeight(pNode->right))+1;
right->height=max(getHeight(right->left),getHeight(right->right))+1;
return right;
}
//先左旋再右旋
TreeNode<K, V> *L_R_Rotation(TreeNode<K, V> *pNode) {
pNode->left=L_Rotation(pNode->left);
return R_Rotation(pNode);
}
//先右旋再左旋
TreeNode<K, V> *R_L_Rotation(TreeNode<K, V> *pNode) {
pNode->right=R_Rotation(pNode->right);
return L_Rotation(pNode);
}
//返回一個節(jié)點倦微，
TreeNode<K, V> *addNode(TreeNode<K, V> *pNode, K key, V value) {
if(pNode==NULL){
count++;
return new TreeNode<K,V>(key,value);
}
if(pNode->key > key){//放左邊
pNode->left=addNode(pNode->left,key,value);
if(getHeight(pNode->left)-getHeight(pNode->right)==2){
//
if(getHeight(pNode->left->right)>getHeight(pNode->left->left)){
//先左旋再右旋：如果它左孩子的右孩子 大于 它左孩子的左孩子
pNode=L_R_Rotation(pNode);
} else{
pNode=R_Rotation(pNode);
}
}
} else if(pNode->key < key){
pNode->right=addNode(pNode->right,key,value);
if(getHeight(pNode->right)-getHeight(pNode->left)==2){
if(getHeight(pNode->right->left)>getHeight(pNode->right->right)){
//先右旋再左旋：如果它右孩子的左孩子 大于 它右孩子的右孩子
pNode=R_L_Rotation(pNode);
} else{
pNode=L_Rotation(pNode);
}
}
} else{
pNode->value=value;
}
//更新二叉樹的高度
pNode->height=max(getHeight(pNode->left),getHeight(pNode->right))+1;
return pNode;
}
//移除
TreeNode<K, V> *removeNode(TreeNode<K, V> *pNode, K key) {
//遞歸到底
if(pNode==NULL){
return NULL;
}
if(pNode->key > key){
pNode->left=removeNode(pNode->left,key);
//刪除左邊妻味，右邊就比左邊大
if(getHeight(pNode->right)-getHeight(pNode->left)==2){
if(getHeight(pNode->right->left)>getHeight(pNode->right->right)){
//先右旋再左旋：如果它右孩子的左孩子 大于 它右孩子的右孩子
pNode=R_L_Rotation(pNode);
} else{
pNode=L_Rotation(pNode);
}
}
} else if(pNode->key < key){
pNode->right=removeNode(pNode->right,key);
//刪除右邊，左邊就比右邊大
if(getHeight(pNode->left)-getHeight(pNode->right)==2){
//
if(getHeight(pNode->left->right)>getHeight(pNode->left->left)){
//先左旋再右旋：如果它左孩子的右孩子 大于 它左孩子的左孩子
pNode=L_R_Rotation(pNode);
} else{
pNode=R_Rotation(pNode);
}
}
} else{//相等
count--;
if(pNode->left==NULL && pNode->right==NULL){
delete pNode;
return NULL;
} else if(pNode->left==NULL){
TreeNode<K,V> *left=pNode->right;
delete (pNode);
return left;
}else if(pNode->right==NULL){
TreeNode<K,V> *right=pNode->left;
delete (pNode);
return right;
} else{//左右兩子樹都不為空,從左邊找最大值或者從右邊找最小值替代
if(getHeight(pNode->left) > getHeight(pNode->right)){//去左邊找最大值欣福，不會影響平衡
TreeNode<K,V> *maxnum=maxmun(pNode->left);
TreeNode<K,V> *successor=new TreeNode<K,V>(maxnum);
//保證移除的子節(jié)點的高度都有更新
successor->left=removeNode(pNode->left,maxnum->key);
count++;
successor->right=pNode->right;
delete(pNode);//釋放指針內(nèi)容
//重新給指針賦值
pNode = successor;
}else{//去右邊找最小值代替
TreeNode<K,V> *minnum=minimun(pNode->right);
TreeNode<K,V> *successor=new TreeNode<K,V>(minnum);
//保證移除的子節(jié)點的高度都有更新
successor->right=removeNode(pNode->right,minnum->key);
count++;
successor->left=pNode->left;
delete(pNode);//釋放指針內(nèi)容
//重新給指針賦值
pNode = successor;
}
}
}
//移除的時候更新高度
pNode->height=max(getHeight(pNode->left),getHeight(pNode->right))+1;
return pNode;
}
//查找當前樹的最大值
TreeNode<K, V>* maxmun(TreeNode<K, V> *pNode) {
//不斷往右找责球，直到找到右子樹為空的節(jié)點
if(pNode->right==NULL){
return pNode;
}
return maxmun(pNode->right);
}
TreeNode<K, V> *minimun(TreeNode<K, V> *pNode) {
if(pNode->left==NULL){
return pNode;
}
return minimun(pNode->left);
}
//刪除當前樹的最大值
TreeNode<K, V> *deleteMax(TreeNode<K, V> *pNode) {
if(pNode->right==NULL){
TreeNode<K,V> *left=pNode->left;
delete(pNode);
count--;
return left;
}
pNode->right=deleteMax(pNode->right);
return pNode;
}
};
#endif //NDK_TREENODE2_BST_H
