An example of balanced binary tree (AVL tree) for C language data structures
- 2020-06-03 07:21:15
- OfStack
An example of C language data structure is presented in this paper. To share for your reference, specific as follows:
AVL tree is a two-pronged search tree where the height difference between the left and right subtrees of each node is at most one.
To maintain the tree, you must detect the presence of a broken tree structure at both insert and delete times. Then adjust immediately.
I have been looking at all kinds of AVL trees on the Internet for a long time.
The key is to understand the concept of rotation when inserting.
//
// AvlTree.h
// HelloWorld
// Created by feiyin001 on 17/1/9.
// Copyright (c) 2017 years FableGame. All rights reserved.
//
#ifndef __HelloWorld__AvlTree__
#define __HelloWorld__AvlTree__
#include <iostream>
namespace Fable
{
int max(int a, int b)
{
return a > b? a:b;
}
//2 Cross find the tree, for Comparable, It has to happen ><= The comparison of
template<typename Comparable>
class AvlTree
{
public:
// The constructor
AvlTree(){}
// Copy constructor
AvlTree(const AvlTree& rhs)
{
root = clone(rhs.root);
}
// The destructor
~AvlTree()
{
makeEmpty(root);
}
// Copy assignment operator
const AvlTree& operator=(const AvlTree& rhs)
{
if (this != &rhs)
{
makeEmpty(root);// To clear
root = clone(rhs.root);// copied
}
return *this;
}
// Find the smallest object
const Comparable& findMin()const
{
findMin(root);
}
// Find the largest object
const Comparable& findMax()const
{
findMax(root);
}
// Contains an object
bool contains(const Comparable& x)const
{
return contains(x, root);
}
// The tree is empty
bool isEmpty()const
{
return root == nullptr;
}
// Print the entire tree
void printTree()const
{
printTree(root);
}
// Empty the tree
void makeEmpty()
{
makeEmpty(root);
}
// Insert an object
void insert(const Comparable& x)
{
insert(x, root);
}
// Remove an object
void remove(const Comparable& x)
{
remove(x, root);
}
private:
struct AvlNode
{
Comparable element;
AvlNode* left;
AvlNode* right;
int height;
AvlNode(const Comparable& theElement, AvlNode* lt, AvlNode* rt, int h = 0)
:element(theElement), left(lt), right(rt), height(h){}
};
typedef AvlNode* AvlNodePtr;
AvlNodePtr root;// The root node
// Clockwise rotation
void clockwiseRotate(AvlNodePtr& a)
{
AvlNodePtr b = a->left;// Left the leaves
a->left = b->right;//a Of the left leaf b Of the right leaf, b The ratio of all the children a Small.
b->right = a;//b The right node points to a . b The height of theta has risen.
a->height = max(height(a->left), height(a->right)) + 1;// recalculate a The height of the
b->height = max(height(b->left), a->height) + 1;// recalculate b The height of the
a = b;//a Theta is now theta b , the current root
}
// Counterclockwise rotation
void antiClockWiseRotate(AvlNodePtr& a)
{
AvlNodePtr b = a->right;// Right node
a->right = b->left;//a receive b The left node
b->left = a;// To become b The left node
a->height = max(height(a->left), height(a->right)) + 1;// Calculate height
b->height = max(b->height, height(a->right)) + 1;// Calculate height
a = b;// New root
}
// Double rotation of the left node
void doubleWithLeftChild(AvlNodePtr& k3)
{
antiClockWiseRotate(k3->left);// Rotate the left node counterclockwise
clockwiseRotate(k3);// Rotate itself clockwise
}
// Double rotation of the right node
void doubleWithRightChild(AvlNodePtr& k3)
{
clockwiseRotate(k3->right);// Rotate the nodes clockwise
antiClockWiseRotate(k3);// Rotate itself counterclockwise
}
// Insert object, where reference is used
void insert(const Comparable& x, AvlNodePtr& t)
{
if (!t)
{
t = new AvlNode(x, nullptr, nullptr);
}
else if (x < t->element)
{
insert(x, t->left);// It's smaller than the root. Insert to the left
if (height(t->left) - height(t->right) == 2)// Height difference reach 2 the
{
if (x < t->left->element)// Insert the left side
{
clockwiseRotate(t);// Clockwise rotation
}
else
{
doubleWithLeftChild(t);// Double rotation
}
}
}
else if (x > t->element)
{
insert(x, t->right);// Bigger than the root, insert to the right
if (height(t->right) - height(t->left) == 2)// Height difference reach 2
{
if (t->right->element < x)// Insert the right
{
antiClockWiseRotate(t);// rotating
}
else
{
doubleWithRightChild(t);// Double rotation
}
}
}
else
{
// The same
}
t->height = max(height(t->left), height(t->right)) + 1;// Calculate the height of the node
}
void removeMin(AvlNodePtr& x, AvlNodePtr& t)const
{
if (!t)
{
return;// Can't find
}
if (t->left)
{
removeMin(t->left);// I'm using recursion
}
else
{
// We found the smallest node
x->element = t->element;
AvlNodePtr oldNode = t;
t = t->right;
delete oldNode;// Delete the node you want to delete
}
if (t)
{
t->height = max(height(t->left), height(t->right)) + 1;// Calculate the height of the node
if(height(t->left) - height(t->right) == 2)
{ // If the left son is taller than the right son
if(height(t->left->left) >= height(t->left->right))// And the left son's left subtree height is greater than the left son's right subtree height
{
clockwiseRotate(t); // Clockwise rotation
}
else
{
doubleWithLeftChild(t);// Double rotate the left subtree
}
}
else
{
if(height(t->right->right) - height(t->right->left) == 2) // If the right subtree is greater than the left
{
antiClockWiseRotate(t);// Counterclockwise rotation
}
else
{
doubleWithRright(t);// Double rotate the right subtree
}
}
}
}
// To delete an object, a reference must be made
void remove(const Comparable& x, AvlNodePtr& t)const
{
if (!t)
{
return;// The tree is empty
}
else if (x < t->element)
{
remove(x, t->left);// Smaller than the root, go to the left
}
else if (x > t->element)
{
remove(x, t->right);// Bigger than the root, go to the right
}
else if (!t->left && !t->right)// We've found the node. We have two leaves
{
removeMin(t, t->right);// The choice here is to delete the smallest node in the right subtree
}
else
{
AvlNodePtr oldNode = t;
t = (t->left) ? t->left : t->right;// When I get here, t Only up to 1 A leaf, will t Point to the leaf
delete oldNode;// Delete the node you want to delete
}
if (t)
{
t->height = max(height(t->left), height(t->right)) + 1;// Calculate the height of the node
if(height(t->left) - height(t->right) == 2)
{ // If the left son is taller than the right son
if(height(t->left->left) >= height(t->left->right))// And the left son's left subtree height is greater than the left son's right subtree height
{
clockwiseRotate(t); // Clockwise rotation
}
else
{
doubleWithLeftChild(t);// Double rotate the left subtree
}
}
else
{
if(height(t->right->right) - height(t->right->left) == 2) // If the right subtree is greater than the left
{
antiClockWiseRotate(t);// Counterclockwise rotation
}
else
{
doubleWithRright(t);// Double rotate the right subtree
}
}
}
}
// The node of the left subtree must be smaller than the current root, so 1 Look straight to the left
AvlNodePtr findMin(AvlNodePtr t)const
{
if (!t)
{
return nullptr;// Can't find
}
if (!t->left)
{
return t;
}
return findMin(t->left);// I'm using recursion
}
// The node of the right subtree must be larger than the current root, so 1 Go straight to the right
AvlNodePtr findMax(AvlNodePtr t)const
{
if (t)
{
while (t->right)// A loop is used
{
t = t->right;
}
}
return t;
}
// Determine whether an object is included or not, because you are using recursion, so there is 1 a public Version of the
bool contains(const Comparable& x, AvlNodePtr t)const
{
if (!t)
{
return false;// The empty nodes
}
else if (x < t->element)
{
// According to the 2 The definition of a cross tree, an object smaller than a node, must only exist in the subtree to the left of that node
return contains(x, t->left);
}
else if (x > t->element)
{
// According to the 2 The definition of a cross tree, an object larger than a node, must only exist in a subtree to the right of that node
return contains(x, t->right);
}
else
{
// If it's equal, it's found.
return true;
}
}
// Qing loophole tree
void makeEmpty(AvlNodePtr& t)
{
if (t)
{
makeEmpty(t->left);// The left empty
makeEmpty(t->right);// To empty the right
delete t;// Release itself
}
t = nullptr;// Set to null
}
// Typing subtree, where no complex ranking is used, is just printing
void printTree(AvlNodePtr t)const
{
if (!t)
{
return;
}
std::cout << t->element << std::endl;// Output its own object
printTree(t->left);// Print the left subtree
printTree(t->right);// Print the right subtree
}
AvlNodePtr clone(AvlNodePtr t)const
{
if (!t)
{
return nullptr;
}
return new AvlNode(t->element, clone(t->left), clone(t->right));
}
int height(AvlNodePtr t)const
{
return t == nullptr ? -1 : t->height;
}
};
}
#endif
Simple test 1.
//
// AvlTree.cpp
// HelloWorld
// Created by feiyin001 on 17/1/9.
// Copyright (c) 2017 years FableGame. All rights reserved.
//
#include "AvlTree.h"
using namespace Fable;
int main(int argc, char* argv[])
{
AvlTree<int> a;
for(int i = 0; i < 100; ++i)
{
a.insert(i);
}
return 0;
}
This deletion method is completely self-written and may not be very efficient.
I hope this article has been helpful to the C language programming.