Avl Tree Program
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Avl Tree Program as PDF for free.
More details
- Words: 1,738
- Pages: 16
AVL TREES First we develop a class AVLNode for the nodes in an AVL tree. The code is given below and in the file avlnode.h. template class AVLNode { friend AVLtree<E,K>; public: AVLNode() {LeftChild = RightChild = 0;} AVLNode(const E& e) {data = e; bf = 0; LeftChild = RightChild = 0;} private: E data; int bf;
// balance factor
AVLNode<E,K> *LeftChild,
// left subtree
*RightChild; // right subtree }; The interface for the class AVLtree is given below and in the file avl.h. template class AVLtree {
public: AVLtree() {root = 0;} ~AVLtree() {Erase(root);} bool Search(const K& k, E& e) const; AVLtree<E,K>& Insert(const E& e); AVLtree<E,K>& Delete(const K& k, E& e); void Ascend() {
InOutput(root); cout << endl;
} protected: AVLNode<E,K> *root;
// root node
void Erase(AVLNode<E,K> *t); void InOutput(AVLNode<E,K> *t); void FixBF(AVLNode<E,K> *,AVLNode<E,K>*, const E&); 1
void RRrotate(AVLNode<E,K> *,AVLNode<E,K>*, AVLNode<E,K> *); void LLrotate(AVLNode<E,K> *,AVLNode<E,K>*, AVLNode<E,K> *); void RLrotate(AVLNode<E,K> *,AVLNode<E,K>*, AVLNode<E,K> *); void LRrotate(AVLNode<E,K> *,AVLNode<E,K>*, AVLNode<E,K> *); }; Erase template void AVLtree<E,K>::Erase(AVLNode<E,K> *t) {// Delete all nodes in AVL tree with root t. // Use a postorder traversal. if (t) {
Erase(t->LeftChild); Erase(t->RightChild); delete t;
} }
Search template bool AVLtree<E,K>::Search(const K& k, E &e) const {// Search for element that matches k. // pointer p starts at the root and moves through // the tree looking for an element with key k AVLNode<E,K> *p = root; while (p) // examine p->data if (k < p->data) p = p->LeftChild;
2
else if (k > p->data) p = p->RightChild; else {// found element e = p->data; return true; } return false; } Fix Balance Factor template void AVLtree<E,K>::FixBF(AVLNode<E,K> *q, AVLNode<E,K> *r, const E &e) {
// Balance factors from q to r were originally 0. //They need to be changed to +1or-1. //Use e to find path from q to r. while (q != r) if (e < q->data) {
// height of left subtree has increased q->bf = 1; q = q->LeftChild;
} else {
// height of right subtree has increased q->bf = -1; q = q->RightChild;
} }
The elements can be output in ascending order by performing an inorder traversal as below. template void AVLtree<E,K>::InOutput(AVLNode<E,K> *t) 3
{
// Output in ascending order. // Use an inorder traversal. if (t) {
InOutput(t->LeftChild); cout << t->data << " "; InOutput(t->RightChild);
} }
Rotations template void AVLtree<E,K>::LLrotate(AVLNode<E,K> *PA, AVLNode<E,K> *A, AVLNode<E,K> *B) {
// LL rotation around A.
PA is parent of A
// and B left child of A. // restructure subtree at A A->LeftChild = B->RightChild; B->RightChild = A; if (PA) // A is not the root if (A == PA->LeftChild) PA->LeftChild = B; else PA->RightChild = B; else root = B;
4
// set balance factors A->bf = B->bf = 0; } template void AVLtree<E,K>::RRrotate(AVLNode<E,K> *PA, AVLNode<E,K> *A, AVLNode<E,K> *B) {
// RR rotation around A.
PA is parent of A
// and B right child of A. // restructure subtree at A A->RightChild = B->LeftChild; B->LeftChild = A; if (PA) // A is not the root if (A == PA->LeftChild) PA->LeftChild = B; else PA->RightChild = B; else root = B; // set balance factors A->bf = B->bf = 0; } template void AVLtree<E,K>::LRrotate(AVLNode<E,K> *PA, AVLNode<E,K> *A, AVLNode<E,K> *B) {
// LR rotation around A.
PA is parent of A
// and B left child of A. AVLNode<E,K> *C = B->RightChild; 5
// restructure subtree at A A->LeftChild = C->RightChild; B->RightChild = C->LeftChild; C->LeftChild = B; C->RightChild = A; if (PA) // A is not the root if (A == PA->LeftChild) PA->LeftChild = C; else PA->RightChild = C; else root = C; // set balance factors int b = C->bf; if (b == 1) {
B->bf = 0;
A->bf = -1;
} else if (b) {
B->bf = 1;
A->bf = 0;
} else // b = 0 B->bf = A->bf = 0; C->bf = 0; } template 6
void AVLtree<E,K>::RLrotate(AVLNode<E,K> *PA, AVLNode<E,K> *A, AVLNode<E,K> *B) {
// RL rotation around A.
PA is parent of A
// and B left child of A. AVLNode<E,K> *C = B->LeftChild; // restructure subtree at A A->RightChild = C->LeftChild; B->LeftChild = C->RightChild; C->LeftChild = A; C->RightChild = B; if (PA) // A is not the root if (A == PA->LeftChild) PA->LeftChild = C; else PA->RightChild = C; else root = C; // set balance factors int b = C->bf; if (b == 1) {
B->bf = -1;
A->bf = 0;
} else if (b) {
B->bf = 0;
A->bf = 1;
} 7
else // b = 0 B->bf = A->bf = 0; C->bf = 0; }
Insertion template AVLtree<E,K>& AVLtree<E,K>::Insert(const E& e) {
// Insert e if not duplicate. AVLNode<E,K> *p = root,
// search pointer
*pp = 0,
// parent of p
*A = 0,
// node with bf != 0
*PA;
// parent of A
// find place to insert // also record most recent node with bf != 0 // in A and its parent in PA while (p) {
// examine p->data if (p->bf) {
// new candidate for A node A = p; PA = pp;
} pp = p; 8
// move p to a child if (e < p->data) p = p->LeftChild; else if (e > p->data) p = p->RightChild; else throw BadInput(); // duplicate }
// get a node for e and attach to pp AVLNode<E,K> *r = new AVLNode<E,K> (e); if (root) {
// tree not empty if (e < pp->data) pp->LeftChild = r; else pp->RightChild = r;
} else {
// insertion into empty tree root = r; return *this; }
// see if we must rebalance or simply change balance factors if (A) // possible rebalancing needed {
if (A->bf < 0) // bf = -1 before insertion {
if (e < A->data) {
// insertion in left subtree // height of left subtree has increased by 1 // new bf of A is 0, no rebalancing 9
A->bf = 0; // fix bf on path from A to r FixBF(A->LeftChild,r,e); } else {
// insertion in right subtree // bf of A is -2, rebalance AVLNode<E,K> *B = A->RightChild; if (e > B->data) {
// RR case FixBF(B->RightChild,r,e); RRrotate(PA,A,B);
} else {
// RL case FixBF(B->LeftChild,r,e); RLrotate(PA,A,B);
} } } else {
// bf = +1 before insertion
if (e > A->data) {
// insertion in right subtree // height of right subtree has increased by 1 // new bf of A is 0, no rebalancing A->bf = 0; // fix bf on path from A to r FixBF(A->RightChild,r,e);
} else {
// insertion in left subtree // bf of A is +2, rebalance 10
AVLNode<E,K> *B = A->LeftChild; if (e < B->data) {
// LL case FixBF(B->LeftChild,r,e); LLrotate(PA,A,B);
} else {
// LR case FixBF(B->RightChild,r,e); LRrotate(PA,A,B);
} } } } else // A is NULL, no rebalancing FixBF(root,r,e); return *this; }
Deletion template AVLtree<E,K>& AVLtree<E,K>::Delete(const K& k, E& e) {
// Delete element with key k and put it in e. // Throw BadInput exception if there is no element // with key k. Stack*> S(100); 11
// set p to point to node with key k AVLNode<E,K> *p = root; // search pointer while (p && p->data != k) {
// move to a child of p S.Add(p); if (k < p->data) p = p->LeftChild; else p = p->RightChild;
} if (!p) throw BadInput(); // no element with key k e = p->data;
// save element to delete
// restructure tree // handle case when p has two children if (p->LeftChild && p->RightChild) {
// two children // convert to zero or one child case // find largest element in left subtree of p S.Add(p); AVLNode<E,K> *s = p->LeftChild; while (s->RightChild) {
// move to larger element S.Add(s); s = s->RightChild;
} 12
// move largest from s to p p->data = s->data; p = s; } // p has at most one child
// save child pointer in c
AVLNode<E,K> *c; if (p->LeftChild) c = p->LeftChild; else c = p->RightChild; // delete p if (p == root) root = c; else {
// is p a left or right child? if (p == S.Top()->LeftChild) S.Top()->LeftChild = c; else S.Top()->RightChild = c; }
E f = p->data; // f may not equal e delete p; // rebalance tree & correct BF, use stack to retrace path to root // set q to parent of deleted node AVLNode<E,K> *q; try {
S.Delete(q); 13
} catch (OutOfBounds) {
return *this;
// root was deleted
} while (q) { if (f <= q->data) {
// deleted from left subtree of q // height of left subtree reduced by 1 q->bf--; if (q->bf == -1) // height of q is unchanged return *this; if (q->bf == -2) {
// q is unbalanced // classify imbalance and rotate AVLNode<E,K> *B = q->RightChild,*PA; // q is A node, PA is parent of A try {
S.Delete(PA);
} catch (OutOfBounds) {
PA = 0;
// A is root
} switch (B->bf) { case 0:
// L0 imbalance
RRrotate(PA,q,B); B->bf = 1; q->bf = -1;
// q is A node
return *this; case 1:
// L1 imbalance
RLrotate(PA,q,B); break; case -1:
// must continue on path to root // L-1 imbalance 14
RRrotate(PA,q,B); } q = PA; } else {
// q->bf is 0 try {
S.Delete(q);
} catch (OutOfBounds) {
return *this;
} } } else {
// f > q->data // deleted from right subtree of q // height of right subtree reduced by 1 q->bf++; if (q->bf == 1) // height of q is unchanged return *this; if (q->bf == 2) {
// q is unbalanced,classify imbalance and rotate AVLNode<E,K> *B = q->LeftChild,*PA; // q is A node,PA is parent of A try {
S.Delete(PA);
} catch (OutOfBounds) { }
PA = 0; // A is root
switch (B->bf) { case 0:
// R0 imbalance 15
LLrotate(PA,q,B); B->bf = -1; q->bf = 1;
// q is A node
return *this; case 1:
// R1 imbalance
LLrotate(PA,q,B); break; case -1:
// must continue on path to root // R-1 imbalance
LRrotate(PA,q,B); } q = PA; } else {
// q->bf is 0 try {
S.Delete(q);
} catch (OutOfBounds) {
return *this;
} } } } return *this; }
16
// balance factor
AVLNode<E,K> *LeftChild,
// left subtree
*RightChild; // right subtree }; The interface for the class AVLtree is given below and in the file avl.h. template
public: AVLtree() {root = 0;} ~AVLtree() {Erase(root);} bool Search(const K& k, E& e) const; AVLtree<E,K>& Insert(const E& e); AVLtree<E,K>& Delete(const K& k, E& e); void Ascend() {
InOutput(root); cout << endl;
} protected: AVLNode<E,K> *root;
// root node
void Erase(AVLNode<E,K> *t); void InOutput(AVLNode<E,K> *t); void FixBF(AVLNode<E,K> *,AVLNode<E,K>*, const E&); 1
void RRrotate(AVLNode<E,K> *,AVLNode<E,K>*, AVLNode<E,K> *); void LLrotate(AVLNode<E,K> *,AVLNode<E,K>*, AVLNode<E,K> *); void RLrotate(AVLNode<E,K> *,AVLNode<E,K>*, AVLNode<E,K> *); void LRrotate(AVLNode<E,K> *,AVLNode<E,K>*, AVLNode<E,K> *); }; Erase template
Erase(t->LeftChild); Erase(t->RightChild); delete t;
} }
Search template
2
else if (k > p->data) p = p->RightChild; else {// found element e = p->data; return true; } return false; } Fix Balance Factor template
// Balance factors from q to r were originally 0. //They need to be changed to +1or-1. //Use e to find path from q to r. while (q != r) if (e < q->data) {
// height of left subtree has increased q->bf = 1; q = q->LeftChild;
} else {
// height of right subtree has increased q->bf = -1; q = q->RightChild;
} }
The elements can be output in ascending order by performing an inorder traversal as below. template
{
// Output in ascending order. // Use an inorder traversal. if (t) {
InOutput(t->LeftChild); cout << t->data << " "; InOutput(t->RightChild);
} }
Rotations template
// LL rotation around A.
PA is parent of A
// and B left child of A. // restructure subtree at A A->LeftChild = B->RightChild; B->RightChild = A; if (PA) // A is not the root if (A == PA->LeftChild) PA->LeftChild = B; else PA->RightChild = B; else root = B;
4
// set balance factors A->bf = B->bf = 0; } template
// RR rotation around A.
PA is parent of A
// and B right child of A. // restructure subtree at A A->RightChild = B->LeftChild; B->LeftChild = A; if (PA) // A is not the root if (A == PA->LeftChild) PA->LeftChild = B; else PA->RightChild = B; else root = B; // set balance factors A->bf = B->bf = 0; } template
// LR rotation around A.
PA is parent of A
// and B left child of A. AVLNode<E,K> *C = B->RightChild; 5
// restructure subtree at A A->LeftChild = C->RightChild; B->RightChild = C->LeftChild; C->LeftChild = B; C->RightChild = A; if (PA) // A is not the root if (A == PA->LeftChild) PA->LeftChild = C; else PA->RightChild = C; else root = C; // set balance factors int b = C->bf; if (b == 1) {
B->bf = 0;
A->bf = -1;
} else if (b) {
B->bf = 1;
A->bf = 0;
} else // b = 0 B->bf = A->bf = 0; C->bf = 0; } template
void AVLtree<E,K>::RLrotate(AVLNode<E,K> *PA, AVLNode<E,K> *A, AVLNode<E,K> *B) {
// RL rotation around A.
PA is parent of A
// and B left child of A. AVLNode<E,K> *C = B->LeftChild; // restructure subtree at A A->RightChild = C->LeftChild; B->LeftChild = C->RightChild; C->LeftChild = A; C->RightChild = B; if (PA) // A is not the root if (A == PA->LeftChild) PA->LeftChild = C; else PA->RightChild = C; else root = C; // set balance factors int b = C->bf; if (b == 1) {
B->bf = -1;
A->bf = 0;
} else if (b) {
B->bf = 0;
A->bf = 1;
} 7
else // b = 0 B->bf = A->bf = 0; C->bf = 0; }
Insertion template
// Insert e if not duplicate. AVLNode<E,K> *p = root,
// search pointer
*pp = 0,
// parent of p
*A = 0,
// node with bf != 0
*PA;
// parent of A
// find place to insert // also record most recent node with bf != 0 // in A and its parent in PA while (p) {
// examine p->data if (p->bf) {
// new candidate for A node A = p; PA = pp;
} pp = p; 8
// move p to a child if (e < p->data) p = p->LeftChild; else if (e > p->data) p = p->RightChild; else throw BadInput(); // duplicate }
// get a node for e and attach to pp AVLNode<E,K> *r = new AVLNode<E,K> (e); if (root) {
// tree not empty if (e < pp->data) pp->LeftChild = r; else pp->RightChild = r;
} else {
// insertion into empty tree root = r; return *this; }
// see if we must rebalance or simply change balance factors if (A) // possible rebalancing needed {
if (A->bf < 0) // bf = -1 before insertion {
if (e < A->data) {
// insertion in left subtree // height of left subtree has increased by 1 // new bf of A is 0, no rebalancing 9
A->bf = 0; // fix bf on path from A to r FixBF(A->LeftChild,r,e); } else {
// insertion in right subtree // bf of A is -2, rebalance AVLNode<E,K> *B = A->RightChild; if (e > B->data) {
// RR case FixBF(B->RightChild,r,e); RRrotate(PA,A,B);
} else {
// RL case FixBF(B->LeftChild,r,e); RLrotate(PA,A,B);
} } } else {
// bf = +1 before insertion
if (e > A->data) {
// insertion in right subtree // height of right subtree has increased by 1 // new bf of A is 0, no rebalancing A->bf = 0; // fix bf on path from A to r FixBF(A->RightChild,r,e);
} else {
// insertion in left subtree // bf of A is +2, rebalance 10
AVLNode<E,K> *B = A->LeftChild; if (e < B->data) {
// LL case FixBF(B->LeftChild,r,e); LLrotate(PA,A,B);
} else {
// LR case FixBF(B->RightChild,r,e); LRrotate(PA,A,B);
} } } } else // A is NULL, no rebalancing FixBF(root,r,e); return *this; }
Deletion template
// Delete element with key k and put it in e. // Throw BadInput exception if there is no element // with key k. Stack
// set p to point to node with key k AVLNode<E,K> *p = root; // search pointer while (p && p->data != k) {
// move to a child of p S.Add(p); if (k < p->data) p = p->LeftChild; else p = p->RightChild;
} if (!p) throw BadInput(); // no element with key k e = p->data;
// save element to delete
// restructure tree // handle case when p has two children if (p->LeftChild && p->RightChild) {
// two children // convert to zero or one child case // find largest element in left subtree of p S.Add(p); AVLNode<E,K> *s = p->LeftChild; while (s->RightChild) {
// move to larger element S.Add(s); s = s->RightChild;
} 12
// move largest from s to p p->data = s->data; p = s; } // p has at most one child
// save child pointer in c
AVLNode<E,K> *c; if (p->LeftChild) c = p->LeftChild; else c = p->RightChild; // delete p if (p == root) root = c; else {
// is p a left or right child? if (p == S.Top()->LeftChild) S.Top()->LeftChild = c; else S.Top()->RightChild = c; }
E f = p->data; // f may not equal e delete p; // rebalance tree & correct BF, use stack to retrace path to root // set q to parent of deleted node AVLNode<E,K> *q; try {
S.Delete(q); 13
} catch (OutOfBounds) {
return *this;
// root was deleted
} while (q) { if (f <= q->data) {
// deleted from left subtree of q // height of left subtree reduced by 1 q->bf--; if (q->bf == -1) // height of q is unchanged return *this; if (q->bf == -2) {
// q is unbalanced // classify imbalance and rotate AVLNode<E,K> *B = q->RightChild,*PA; // q is A node, PA is parent of A try {
S.Delete(PA);
} catch (OutOfBounds) {
PA = 0;
// A is root
} switch (B->bf) { case 0:
// L0 imbalance
RRrotate(PA,q,B); B->bf = 1; q->bf = -1;
// q is A node
return *this; case 1:
// L1 imbalance
RLrotate(PA,q,B); break; case -1:
// must continue on path to root // L-1 imbalance 14
RRrotate(PA,q,B); } q = PA; } else {
// q->bf is 0 try {
S.Delete(q);
} catch (OutOfBounds) {
return *this;
} } } else {
// f > q->data // deleted from right subtree of q // height of right subtree reduced by 1 q->bf++; if (q->bf == 1) // height of q is unchanged return *this; if (q->bf == 2) {
// q is unbalanced,classify imbalance and rotate AVLNode<E,K> *B = q->LeftChild,*PA; // q is A node,PA is parent of A try {
S.Delete(PA);
} catch (OutOfBounds) { }
PA = 0; // A is root
switch (B->bf) { case 0:
// R0 imbalance 15
LLrotate(PA,q,B); B->bf = -1; q->bf = 1;
// q is A node
return *this; case 1:
// R1 imbalance
LLrotate(PA,q,B); break; case -1:
// must continue on path to root // R-1 imbalance
LRrotate(PA,q,B); } q = PA; } else {
// q->bf is 0 try {
S.Delete(q);
} catch (OutOfBounds) {
return *this;
} } } } return *this; }
16
Related Documents
Avl Tree Program
November 2019 3
Avl Tree Notes
July 2020 11
Avl
November 2019 4
Avl Trees
July 2020 4
Arboles Avl
April 2020 13