创新互联建站-专业网站定制、快速模板网站建设、高性价比增城网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式增城网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖增城地区。费用合理售后完善，十余年实体公司更值得信赖。

• AVL树

AVL树又称为高度平衡的二叉搜索树，是1962年有俄罗斯的数学家G.M.Adel'son-Vel'skii和E.M.Landis提出来的。它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均搜索长度。

• AVL树的性质

1. 左子树和右子树的高度之差的绝对值不超过1

2. 树中的每个左子树和右子树都是AVL树

3. 每个节点都有一个平衡因子(balance factor--bf),任一节点的平衡因子是-1,0,1。(每个节点的平衡因子等于右子树的高度减去左子树的高度 )                                               

• AVL树的效率

一棵AVL树有N个节点，其高度可以保持在log2N，插入/删除/查找的时间复杂度也是log2N。

（ps：log2N是表示log以2为底N的对数，evernote不支持公式。^^）

这里要注意在插入和删除时对平衡因子BF的修改

插入

#pragma once

#include

using namespace std;

#include

template< class K, class  V>

struct AVLBSTreeNode

{

AVLBSTreeNode* _left;

AVLBSTreeNode* _right;

AVLBSTreeNode* _parent;

K _key;

V _value;

int _bf;//平衡因子

AVLBSTreeNode(const K& key, const V& value)

:_left(NULL)

, _right(NULL)

, _parent(NULL)

, _key(key)

, _value(value)

, _bf(0)

{}

};

template

class AVLBSTree

{

typedef AVLBSTreeNode Node;

public:

AVLBSTree()

:_root(NULL)

{}

bool Insert(const K& key, const V& value)//插入

{

if (_root == NULL)

{

_root = new Node(key, value);

return true;

}

Node* cur = _root;

Node* parent = NULL;

while (cur)

{

if (cur->_key > key)

{

parent = cur;

cur = cur->_left;

}

else if (cur->_key < key)

{

parent = cur;

cur = cur->_right;

}

else

{

return false;

}

}

cur = new Node(key, value);

if (parent->_key > key)

{

parent->_left = cur;

cur->_parent = parent;

}

else

{

parent->_right = cur;

cur->_parent = parent;

}

//更新平衡因子，不平衡进行旋转

while (parent)

{

if (cur == parent->_right)

{

parent->_bf++;

}

else 

{

parent->_bf--;

}

if (parent->_bf == 0)//平衡因子为0对这个树的高度不会产生影响

{

break;

}

else if (parent->_bf == 1 || parent->_bf == -1)

{

cur = parent;

parent = cur->_parent;

}

else

{

if (parent->_bf == -2)

{

if (cur->_bf == -1)

{

RotateR(parent);//右旋

}

else

{

RotateLR(parent);//先左旋再右旋

}

}

else 

{

if (cur->_bf == 1)

{

RotateL(parent);//左旋

}

else

{

RotateRL(parent);//先右旋再左旋

}

}

break;

}

}

return true;

}

void Inorder()//中序遍历

{

_Inorder(_root);

cout << endl;

}

bool IsBalance()//检查平衡因子

{

return _IsBalance(_root);

}

Node* Find(const K& key)//查找

{

Node* cur = _root;

while (cur)

{

if (cur->_key > key)

{

cur = cur->_left;

}

else if (cur->_key < key)

{

cur = cur->_right;

}

else

{

return cur;

}

}

return NULL;

}

bool Remove(const K& key)//删除

{

if (_root == NULL)

{

return false;

}

Node* cur = _root;

Node* parent = NULL;

while (cur)

{

if (cur->_key > key)

{

parent = cur;

cur = cur->_left;

}

else if (cur->_key < key)

{

parent = cur;

cur = cur->_right;

}

else

{

if (cur->_left == NULL && cur->_right == NULL)

{

if (parent == NULL)

{

_root = NULL;

}

else

{

if (parent->_left == cur)

{

parent->_left = NULL;

parent->_bf++;

}

else

{

parent->_right = NULL;

parent->_bf--;

}

}

delete cur;

}

else if (cur->_left == NULL && cur->_right != NULL)

{

if (parent == NULL)

{

_root = cur->_right;

_root->_bf = 0;

}

else

{

if (parent->_left == cur)

{

parent->_left = cur->_right;

parent->_bf++;

}

else

{

parent->_right = cur->_right;

parent->_bf--;

}

}

delete cur;

}

else if (cur->_right == NULL && cur->_left != NULL)

{

if (parent == NULL)

{

_root = cur->_left;

_root++;

}

else

{

if (parent->_left == cur)

{

parent->_left = cur->_left;

parent->_bf++;

}

else

{

parent->_right = cur->_left;

parent->_bf--;

}

}

delete cur;

}

else

{

Node* parent = cur;

Node* left = cur->_right;

while (left->_left)

{

parent = left;

left = left->_left;

}

cur->_key = left->_key;

cur->_value = left->_value;

if (parent->_left == left)

{

parent->_bf++;

parent->_left = left->_right;

}

else

{

parent->_bf--;

parent->_right = left->_right;

}

delete left;

}

break;

}

}

while (parent)

{

if (parent->_bf == 0)//平衡因子为0对这个树的高度不会产生影响

{

return true;

}

else if (parent->_bf == 1 || parent->_bf == -1)

{

return true;

}

else

{

if (parent->_bf == -2)

{

if (cur->_bf == -1)

{

RotateR(parent);

}

else

{

RotateLR(parent);

}

}

else

{

if (cur->_bf == 1)

{

RotateL(parent);

}

else

{

RotateRL(parent);

}

}

break;

}

}

}

protected:

void RotateR(Node* parent)

{

Node* subL = parent->_left;

Node* subLR = subL->_right;

parent->_left = subLR;

if (subLR)

{

subLR->_parent = parent;

}

Node* ppnode = parent->_parent;

subL->_right = parent;

parent->_parent = subL;

if (ppnode == NULL)

{

_root = subL;

}

else

{

if (ppnode->_left == parent)

{

ppnode->_left = subL;

}

else

{

ppnode->_right = subL;

}

}

subL->_parent = ppnode;

subL->_bf = parent->_bf = 0;

}

void RotateL(Node* parent)

{

Node* subR = parent->_right;

Node* subRL = subR->_left;

parent->_right = subRL;

if (subRL)

{

subRL->_parent = parent;

}

Node* ppnode = parent->_parent;

subR->_left = parent;

parent->_parent = subR;

if (ppnode == NULL)

{

_root = subR;

}

else

{

if (ppnode->_left == parent)

{

ppnode->_left = subR;

}

else

{

ppnode->_right = subR;

}

}

subR->_parent = ppnode;

subR->_bf = parent->_bf = 0;

}

void RotateLR(Node* parent)

{

Node* subL = parent->_left;

Node* subLR = subL->_right;

int bf = subLR->_bf;

RotateL(parent->_left);

RotateR(parent);

if (bf == -1)//subLRde左边插入

{

parent->_bf = 1;

subL->_bf = 0;

}

else if (bf == 1)//subLR的右边插入

{

parent->_bf = 0;

subL->_bf = -1;

}

else//subRL就是插入的元素

{

subL->_bf = parent->_bf = 0;

}

subLR->_bf = 0;

}

void RotateRL(Node* parent)

{

Node* subR = parent->_right;

Node* subRL = subR->_left;

int bf = subRL->_bf;

RotateR(parent->_right);

RotateL(parent);

if (bf == -1)//subLRde左边插入

{

parent->_bf = 0;

subR->_bf = 1;

}

else if (bf == 1)//subLR的右边插入

{

parent->_bf = -1;

subR->_bf = 0;

}

else//subRL就是插入的元素

{

subR->_bf = parent->_bf = 0;

}

subRL->_bf = 0;

}

void _Inorder(Node* root)

{

if (root == NULL)

{

return;

}

_Inorder(root->_left);

cout << root->_key << " ";

_Inorder(root->_right);

}

bool _IsBalance(Node* root)

{

if (root == NULL)

{

return true;

}

int left = _Height(root->_left);

int right = _Height(root->_right);

if ((right - left) != root->_bf || abs(right - left) >= 2)

{

cout << "not balance" << root->_key << endl;

return false;

}

return _IsBalance(root->_left) && _IsBalance(root->_right);

}

int _Height(Node* root)

{

if (root == NULL)

{

return 0;

}

int left = _Height(root->_left);

int right = _Height(root->_right);

if (left > right)

{

return left + 1;

}

else

{

return right + 1;

}

}

protected:

Node* _root;

};

void Test()

{

int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16 ,14};

//int a[] = { 30, 35, 10, 20, 9, 18 };

//int a[] = { 10, 9, 30, 20, 40, 22 };

AVLBSTree t;

int i = 0;

for (i = 0; i < sizeof(a) / sizeof(a[0]); ++i)

{

t.Insert(a[i], i);

}

t.Remove(15);

t.Inorder();

cout<<"isblance"<

//cout << t.Find(50) << endl;

}

当前标题：高度平衡的二叉搜索树—AVLTree
文章分享：http://kswjz.com/article/igpooo.html