高度平衡的二叉搜尋樹—AVLTree

• 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<iostream>

using namespace std;

#include<cmath>

template< class K, class  V>

struct AVLBSTreeNode

{

AVLBSTreeNode<K, V>* _left;

AVLBSTreeNode<K, V>* _right;

AVLBSTreeNode<K, V>* _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 K,class V>

class AVLBSTree

typedef AVLBSTreeNode<K, V> 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)

cur = cur->_right;

else

return false;

cur = new Node(key, value);

if (parent->_key > key)

parent->_left = cur;

cur->_parent = parent;

parent->_right = cur;

//更新平衡因子，不平衡進行旋轉

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;

if (parent->_bf == -2)

if (cur->_bf == -1)

RotateR(parent);//右旋

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

if (cur->_bf == 1)

RotateL(parent);//左旋

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

void Inorder()//中序周遊

_Inorder(_root);

cout << endl;

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

return _IsBalance(_root);

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

return cur;

return NULL;

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

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

if (parent == NULL)

_root = NULL;

if (parent->_left == cur)

parent->_left = NULL;

parent->_right = NULL;

delete cur;

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

_root = cur->_right;

_root->_bf = 0;

parent->_left = cur->_right;

parent->_right = cur->_right;

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

_root = cur->_left;

_root++;

parent->_left = cur->_left;

parent->_right = cur->_left;

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->_left = left->_right;

parent->_right = left->_right;

delete left;

RotateR(parent);

RotateLR(parent);

RotateL(parent);

RotateRL(parent);

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;

if (ppnode->_left == parent)

ppnode->_left = subL;

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;

subR->_left = parent;

parent->_parent = subR;

_root = subR;

ppnode->_left = subR;

ppnode->_right = subR;

subR->_parent = ppnode;

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

void RotateLR(Node* parent)

int bf = subLR->_bf;

RotateL(parent->_left);

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

parent->_bf = 1;

subL->_bf = 0;

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

parent->_bf = 0;

subL->_bf = -1;

else//subRL就是插入的元素

subLR->_bf = 0;

void RotateRL(Node* parent)

int bf = subRL->_bf;

RotateR(parent->_right);

subR->_bf = 1;

parent->_bf = -1;

subR->_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)

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 _IsBalance(root->_left) && _IsBalance(root->_right);

int _Height(Node* root)

return 0;

if (left > right)

return left + 1;

return right + 1;

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<int, int> 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"<<t.IsBalance()<<endl;