## Simple AVL Tree in C++

An AVL tree is a binary search tree(BST) however, unlike binary search trees, an AVL tree (named after Georgy Adelson-Velsky and Evgenii Landis) is self balancing. So no matter how many nodes you insert into the tree, it will adjust it’s branches and ensure the tree is balanced at all times. Making sure the subtree heights only differ by at most 1. BSTs are great for segregating and storing data with a O(log n) search time. Downside with BST is that it can get weighted on one side and doesn’t have an restrictions to prevent it from getting skewed. By switching to an AVL, data is balanced in the tree and the search time is decreased to log n.

So it is more efficient in most cases to use the AVL tree, below is an example of how to code this in C++. Note that the AVL tree uses a lot of the same code the BST did from this post.

```#pragma once

#include <iomanip>
#include <iostream>

using namespace std;

class AVL
{
public:
AVL(){
root = nullptr;
}
~AVL(){
destroy(root);
}

//My Node class for storing data, note how I add height
struct Node{
int data;
Node *left;
Node *right;
int height;

Node(int d){
data = d;
left = nullptr;
right = nullptr;
height = 0;
}

void updateHeight(){
int lHeight = 0;
int rHeight = 0;
if (left != nullptr) {
lHeight = left->height;
}
if (right != nullptr) {
rHeight = right->height;
}
int max = (lHeight > rHeight) ? lHeight : rHeight;
height = max + 1;
}

};

void insert(int val){
insert(val, root);
}

//Rotate a Node branch to the left, in order to balance things
Node* rotateLeft(Node *&leaf){
Node* temp = leaf->right;
leaf->right = temp->left;
temp->left = leaf;

//update the Nodes new height
leaf->updateHeight();

return temp;
}

//Rotate a Node branch to the right, in order to balance things
Node* rotateRight(Node *&leaf){
Node* temp = leaf->left;
leaf->left = temp->right;
temp->right = leaf;

//update the Nodes new height
leaf->updateHeight();

return temp;
}

//Rotate a Node branch to the right then the left, in order to balance things
Node* rotateRightLeft(Node *&leaf){
Node* temp = leaf->right;
leaf->right = rotateRight(temp);
return rotateLeft(leaf);
}

//Rotate a Node branch to the left then the right, in order to balance things
Node* rotateLeftRight(Node *&leaf){
Node* temp = leaf->left;
leaf->left = rotateLeft(temp);
return rotateRight(leaf);
}

//Function that checks each Node's left and right branches to determine if they are unbalanced
//If they are, we rotate the branches
void rebalance(Node *&leaf){
int hDiff = getDiff(leaf);
if (hDiff > 1){
if (getDiff(leaf->left) > 0) {
leaf = rotateRight(leaf);
} else {
leaf = rotateLeftRight(leaf);
}
} else if(hDiff < -1) {
if (getDiff(leaf->right) < 0) {
leaf = rotateLeft(leaf);
} else {
leaf = rotateRightLeft(leaf);
}
}
}

private:
Node *root;
//Insert a Node (very similar to BST, except we need to update Node height and then check for rebalance)
void insert(int d, Node *&leaf){
if (leaf == nullptr){
leaf = new Node(d);
leaf->updateHeight();
}
else {
if (d < leaf->data){
insert(d, leaf->left);
leaf->updateHeight();
rebalance(leaf);
}
else{
insert(d, leaf->right);
leaf->updateHeight();
rebalance(leaf);
}
}
}

//Same as BST
void destroy(Node *&leaf){
if (leaf != nullptr){
destroy(leaf->left);
destroy(leaf->right);
delete leaf;
}
}

//Get the difference between Node right and left branch heights, if it returns positive
//We know the left side is greater, if negative, we know the right side is greater
int getDiff(Node *leaf){
int lHeight = 0;
int rHeight = 0;
if (leaf->left != nullptr) {
lHeight =  leaf->left->height;
}
if (leaf->right != nullptr) {
rHeight = leaf->right->height
}
return lHeight - rHeight;
}
};```

Let me know if you have any issues!

## Binary Search Trees! Simple Class in C++

Here is a really basic binary tree class, it just includes the basics of creating, inserting, erasing, and returning size. In later posts I will talk about printing and traversals.

This class also uses the Node.h talked about in this earlier post. You’ll notice that I really like to use recursion, I think this is cleaner than looping.

```#include <assert.h>
#include "Node.h"
using namespace std;

class Bst
{
public:

//constructor for when a head Node is provided and when it is not
Bst() {
root = nullptr;
}

Bst(Node *np) {
root = np;
}

//destroy the tree, we need to go through and destroy each node
~Bst() {
destroyTree(root);
}

//get the number of nodes in the tree
int size() {
return size(root);
}

//erase a value in the tree
void erase(int item) {
erase(item, root);
}

//insert a Node in the tree
void insert(int item) {
insert(item, root);
}

private:

Node* root;

//Go through each branch and recursively destroy all Nodes
void destroyTree(Node*& n) {
if (n != nullptr) {
destroyTree(n->left);
destroyTree(n->right);
delete n;
}
}

//For each Node return the number of left and right nodes
//Add it up recursively to get the total size
int size(Node* n) {
if (n != nullptr) {
int left = size(n->left);
int right = size(n->right);
int self = 1;
return left + self + right;
}
return 0;
}

//Find the minimum Node value
Node* findMin(Node* n){
assert(n != nullptr);
if (n->left != nullptr) {
return findMin(n->left);
}
return n;
}

//this one is a beast
//look through all the nodes recursively
//once you find the node value there are numerous cases we need to look for
//If the current node does not have left and right nodes, just delete it
//If it does have a left or right node, set the child to the parent
//If it has both left and right, we need to work some magic. First we find
//the smallest value and set the node we want to delete to that value (removing it)
void erase(int item, Node*& n) {
if (n != nullptr) {
if (item == n->data) {
if (n->right == nullptr && n->left == nullptr) {
delete n;
n = nullptr;
} else if (n->right == nullptr) {
Node* temp = n;
n = n->left;
delete n;
} else if (n->left == nullptr){
Node* temp = n;
n = n->right;
delete n;
} else {
Node *temp = findMin(n->right);
n->data = temp->data;
erase(item, n->right);
}
} else if (item < n->data) {
erase(item, n->left);
} else {
erase(item, n->right);
}
}
}

//look through all the nodes
//insert the node on the correct node, it will be added to the left if the value is less
//added to the right if the value is greater
void insert(int item, Node*& n) {
if (n != nullptr) {
if (item < n->data) {
insert(item, n->left);
} else {
insert(item, n->right);
}
} else {
n = new Node(item);
}
}
};
```

Let me know if you have any improvements or comments!