AVL树
2020-03-02 本文已影响0人
思思入扣
今天看了辉哥的AVL树的视频，来给自己写一篇总结，强烈推荐辉哥是视频，这个是辉哥是简书地址https://www.jianshu.com/u/35083fcb7747
一、AVL树
1.定义
在AVL树中任何节点的两个子树的高度最大差别为1，所以被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个数
2.特点
（1）本身首先是一棵二叉搜索树
（2）带有平衡条件：每个节点的左右子树的高度差的绝对值(平衡因子)最多为1，也就是说，AVL树，本质上是带了平衡功能的二叉查找树
二、旋转
在每次插入数值后，树的平衡有可能会被破坏，这时就可以通过旋转操作来矫正平衡
所有的旋转都是对子树来操作
分类：左旋、右旋、先左旋再右旋、先右旋再左旋
旋转总结.png
三、插入
以案例来举例插入
案例：3 2 1 4 5 6 7 10 9 8
1.先插入3
不需要旋转操作
2.插入2
不需要旋转操作
符合左左原则，右旋，旋转完为：
4.插入4
插入4，符合AVL数特征，不进行旋转调整
5.插入5
符合右右原则，左旋，旋转完为：
6.插入6
符合右右原则，左旋，旋转完为：
7.插入7
符合右右原则，左旋，旋转完为：
8.插入10
符合AVL树，不需要调整
-
插入9
符合右左型，先右旋，再左旋
先右旋：
再左旋：
-
插入8
符合左右型，先左旋，再右旋
先左旋：
再右旋
案例讲解就到这里啦，代码在文章最末尾
四、删除
删除总结
还是以案例来举例删除
案例：3 2 1 4 5 6 7 10 9 8
1.删除3，移除3，对整棵树没有影响，不需要进行调整
2.删除3之后在删除1
移除1，对4的高度有影响，需要调整，
符合：删除的是4的左子树上的数据，左旋(符合2)，并且不需要旋转，最后调整结果为：
3.删除4
原来的AVL树
删除的是根节点，或者左右有一个或两个节点，为了保证它是一颗二叉搜索树，需要从左边或者右边找一个节点来填补上去
判断左右子树的高度，哪个高度高，去哪边找，不会影响平衡
左子树：找最大值
右子树：找最小值
案例中删除4，找右子树的最小值5
3.先删除4，再删除5
删除4的图就不上啦，看2就可以了，直接上删除5的图了
删除5会把把6挪上来，导致不平衡
需要左旋，最终图为：
总结就到这里吧，直接把代码放进来吧
//
// 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){//初始节点的高度为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;//根节点
int count;//总结点数
public:
AVL(){
root=NULL;
count=0;
}
~AVL(){//析构函数，需要自己完成
}
//中序遍历,void (*fun)(K, V)回调函数
void inOrderTraverse(void (*fun)(K, V)) {
inOrderTraverse(root,fun);
}
//层序遍历,void (*fun)(K, V)回调函数
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;//原来的左孩子要变成跟节点
TreeNode<K,V> *right=left->right;//保留一下left的right
left->right=pNode;//left的右边是原来的根节点
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;//原来的右孩子要变成根节点
TreeNode<K,V> *left=right->left;//保留一下pNode的left
right->left=pNode;//right的左边是原来的根节点
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);
}
//返回一个节点，
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);
//保证移除的子节点的高度都有更新
successor->left=removeNode(pNode->left,maxnum->key);
count++;
successor->right=pNode->right;
delete(pNode);//释放指针内容
//重新给指针赋值
pNode = successor;
}else{//去右边找最小值代替
TreeNode<K,V> *minnum=minimun(pNode->right);
TreeNode<K,V> *successor=new TreeNode<K,V>(minnum);
//保证移除的子节点的高度都有更新
successor->right=removeNode(pNode->right,minnum->key);
count++;
successor->left=pNode->left;
delete(pNode);//释放指针内容
//重新给指针赋值
pNode = successor;
}
}
}
//移除的时候更新高度
pNode->height=max(getHeight(pNode->left),getHeight(pNode->right))+1;
return pNode;
}
//查找当前树的最大值
TreeNode<K, V>* maxmun(TreeNode<K, V> *pNode) {
//不断往右找，直到找到右子树为空的节点
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
