Untitled

unknown
c_cpp
2 years ago
23 kB
3
Indexable
Never
```// C++ program to delete a node from AVL Tree
#include <bits/stdc++.h>
using namespace std;

// An AVL tree node
class Node
{
public:
int key;
Node *left;
Node *right;
int height;
};

// A utility function to get maximum
// of two integers
int max(int a, int b);

// A utility function to get height
// of the tree
int height(Node *N)
{
if (N == NULL)
return 0;
return N->height;
}

// A utility function to get maximum
// of two integers
int max(int a, int b)
{
return (a > b) ? a : b;
}

/* Helper function that allocates a
new node with the given key and
NULL left and right pointers. */
Node *newNode(int key)
{
Node *node = new Node();
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially
return (node);
}

// A utility function to right
// rotate subtree rooted with y
// See the diagram given above.
Node *rightRotate(Node *y)
{
Node *x = y->left;
Node *T2 = x->right;

// Perform rotation
x->right = y;
y->left = T2;

// Update heights
y->height = max(height(y->left),
height(y->right)) +
1;
x->height = max(height(x->left),
height(x->right)) +
1;

// Return new root
return x;
}

// A utility function to left
// rotate subtree rooted with x
// See the diagram given above.
Node *leftRotate(Node *x)
{
Node *y = x->right;
Node *T2 = y->left;

// Perform rotation
y->left = x;
x->right = T2;

// Update heights
x->height = max(height(x->left),
height(x->right)) +
1;
y->height = max(height(y->left),
height(y->right)) +
1;

// Return new root
return y;
}

// Get Balance factor of node N
int getBalance(Node *N)
{
if (N == NULL)
return 0;
return height(N->left) -
height(N->right);
}

Node *insert(Node *node, int key)
{
/* 1. Perform the normal BST rotation */
if (node == NULL)
return (newNode(key));

if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal keys not allowed
return node;

/* 2. Update height of this ancestor node */
node->height = 1 + max(height(node->left),
height(node->right));

/* 3. Get the balance factor of this
ancestor node to check whether
this node became unbalanced */
int balance = getBalance(node);

// If this node becomes unbalanced,
// then there are 4 cases

// Left Left Case
if (balance > 1 && key < node->left->key)
return rightRotate(node);

// Right Right Case
if (balance < -1 && key > node->right->key)
return leftRotate(node);

// Left Right Case
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}

// Right Left Case
if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}

/* return the (unchanged) node pointer */
return node;
}

/* Given a non-empty binary search tree,
return the node with minimum key value
found in that tree. Note that the entire
tree does not need to be searched. */
Node *minValueNode(Node *node)
{
Node *current = node;

/* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;

return current;
}

// Recursive function to delete a node
// with given key from subtree with
// given root. It returns root of the
// modified subtree.
Node *deleteNode(Node *root, int key)
{

// STEP 1: PERFORM STANDARD BST DELETE
if (root == NULL)
return root;

// If the key to be deleted is smaller
// than the root's key, then it lies
// in left subtree
if (key < root->key)
root->left = deleteNode(root->left, key);

// If the key to be deleted is greater
// than the root's key, then it lies
// in right subtree
else if (key > root->key)
root->right = deleteNode(root->right, key);

// if key is same as root's key, then
// This is the node to be deleted
else
{
// node with only one child or no child
if ((root->left == NULL) ||
(root->right == NULL))
{
Node *temp = root->left ? root->left : root->right;

// No child case
if (temp == NULL)
{
temp = root;
root = NULL;
}
else               // One child case
*root = *temp; // Copy the contents of
// the non-empty child
free(temp);
}
else
{
// node with two children: Get the inorder
// successor (smallest in the right subtree)
Node *temp = minValueNode(root->right);

// Copy the inorder successor's
// data to this node
root->key = temp->key;

// Delete the inorder successor
root->right = deleteNode(root->right,
temp->key);
}
}

// If the tree had only one node
// then return
if (root == NULL)
return root;

// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root->height = 1 + max(height(root->left),
height(root->right));

// STEP 3: GET THE BALANCE FACTOR OF
// THIS NODE (to check whether this
// node became unbalanced)
int balance = getBalance(root);

// If this node becomes unbalanced,
// then there are 4 cases

// Left Left Case
if (balance > 1 &&
getBalance(root->left) >= 0)
return rightRotate(root);

// Left Right Case
if (balance > 1 &&
getBalance(root->left) < 0)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}

// Right Right Case
if (balance < -1 &&
getBalance(root->right) <= 0)
return leftRotate(root);

// Right Left Case
if (balance < -1 &&
getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}

return root;
}

// A utility function to print preorder
// traversal of the tree.
// The function also prints height
// of every node
void preOrder(Node *root)
{
if (root != NULL)
{
cout << root->key << " ";
preOrder(root->left);
preOrder(root->right);
}
}

// Driver Code
int main()
{
Node *root = NULL;

/* Constructing tree given in
the above figure */
root = insert(root, 9);
root = insert(root, 5);
root = insert(root, 10);
root = insert(root, 0);
root = insert(root, 6);
root = insert(root, 11);
root = insert(root, -1);
root = insert(root, 1);
root = insert(root, 2);

/* The constructed AVL Tree would be
9
/ \
1 10
/ \ \
0 5 11
/ / \
-1 2 6
*/

cout << "Preorder traversal of the "
"constructed AVL tree is \n";
preOrder(root);

root = deleteNode(root, 10);

/* The AVL Tree after deletion of 10
1
/ \
0 9
/ / \
-1 5	 11
/ \
2 6
*/

cout << "\nPreorder traversal after"
<< " deletion of 10 \n";
preOrder(root);

return 0;
}

//-------------------------------
// search b tree

// Searching a key on a B-tree in C++

#include <iostream>
using namespace std;

class TreeNode
{
int *keys;
int t;
TreeNode **C;
int n;
bool leaf;

public:
TreeNode(int temp, bool bool_leaf);

void insertNonFull(int k);
void splitChild(int i, TreeNode *y);
void traverse();

TreeNode *search(int k);

friend class BTree;
};

class BTree
{
TreeNode *root;
int t;

public:
BTree(int temp)
{
root = NULL;
t = temp;
}

void traverse()
{
if (root != NULL)
root->traverse();
}

TreeNode *search(int k)
{
return (root == NULL) ? NULL : root->search(k);
}

void insert(int k);
};

TreeNode::TreeNode(int t1, bool leaf1)
{
t = t1;
leaf = leaf1;

keys = new int[2 * t - 1];
C = new TreeNode *[2 * t];

n = 0;
}

void TreeNode::traverse()
{
int i;
for (i = 0; i < n; i++)
{
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}

if (leaf == false)
C[i]->traverse();
}

TreeNode *TreeNode::search(int k)
{
int i = 0;
while (i < n && k > keys[i])
i++;

if (keys[i] == k)
return this;

if (leaf == true)
return NULL;

return C[i]->search(k);
}

void BTree::insert(int k)
{
if (root == NULL)
{
root = new TreeNode(t, true);
root->keys[0] = k;
root->n = 1;
}
else
{
if (root->n == 2 * t - 1)
{
TreeNode *s = new TreeNode(t, false);

s->C[0] = root;

s->splitChild(0, root);

int i = 0;
if (s->keys[0] < k)
i++;
s->C[i]->insertNonFull(k);

root = s;
}
else
root->insertNonFull(k);
}
}

void TreeNode::insertNonFull(int k)
{
int i = n - 1;

if (leaf == true)
{
while (i >= 0 && keys[i] > k)
{
keys[i + 1] = keys[i];
i--;
}

keys[i + 1] = k;
n = n + 1;
}
else
{
while (i >= 0 && keys[i] > k)
i--;

if (C[i + 1]->n == 2 * t - 1)
{
splitChild(i + 1, C[i + 1]);

if (keys[i + 1] < k)
i++;
}
C[i + 1]->insertNonFull(k);
}
}

void TreeNode::splitChild(int i, TreeNode *y)
{
TreeNode *z = new TreeNode(y->t, y->leaf);
z->n = t - 1;

for (int j = 0; j < t - 1; j++)
z->keys[j] = y->keys[j + t];

if (y->leaf == false)
{
for (int j = 0; j < t; j++)
z->C[j] = y->C[j + t];
}

y->n = t - 1;
for (int j = n; j >= i + 1; j--)
C[j + 1] = C[j];

C[i + 1] = z;

for (int j = n - 1; j >= i; j--)
keys[j + 1] = keys[j];

keys[i] = y->keys[t - 1];
n = n + 1;
}

int main()
{
BTree t(3);
t.insert(8);
t.insert(9);
t.insert(10);
t.insert(11);
t.insert(15);
t.insert(16);
t.insert(17);
t.insert(18);
t.insert(20);
t.insert(23);

cout << "The B-tree is: ";
t.traverse();

int k = 10;
(t.search(k) != NULL) ? cout << endl
<< k << " is found"
: cout << endl

k = 2;
(t.search(k) != NULL) ? cout << endl
<< k << " is found"
: cout << endl
}
//-------------------------------

// Inserting a key on a B-tree in C++

#include <iostream>
using namespace std;

class Node
{
int *keys;
int t;
Node **C;
int n;
bool leaf;

public:
Node(int _t, bool _leaf);

void insertNonFull(int k);
void splitChild(int i, Node *y);
void traverse();

friend class BTree;
};

class BTree
{
Node *root;
int t;

public:
BTree(int _t)
{
root = NULL;
t = _t;
}

void traverse()
{
if (root != NULL)
root->traverse();
}

void insert(int k);
};

Node::Node(int t1, bool leaf1)
{
t = t1;
leaf = leaf1;

keys = new int[2 * t - 1];
C = new Node *[2 * t];

n = 0;
}

// Traverse the nodes
void Node::traverse()
{
int i;
for (i = 0; i < n; i++)
{
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}

if (leaf == false)
C[i]->traverse();
}

// Insert the node
void BTree::insert(int k)
{
if (root == NULL)
{
root = new Node(t, true);
root->keys[0] = k;
root->n = 1;
}
else
{
if (root->n == 2 * t - 1)
{
Node *s = new Node(t, false);

s->C[0] = root;

s->splitChild(0, root);

int i = 0;
if (s->keys[0] < k)
i++;
s->C[i]->insertNonFull(k);

root = s;
}
else
root->insertNonFull(k);
}
}

// Insert non full condition
void Node::insertNonFull(int k)
{
int i = n - 1;

if (leaf == true)
{
while (i >= 0 && keys[i] > k)
{
keys[i + 1] = keys[i];
i--;
}

keys[i + 1] = k;
n = n + 1;
}
else
{
while (i >= 0 && keys[i] > k)
i--;

if (C[i + 1]->n == 2 * t - 1)
{
splitChild(i + 1, C[i + 1]);

if (keys[i + 1] < k)
i++;
}
C[i + 1]->insertNonFull(k);
}
}

// split the child
void Node::splitChild(int i, Node *y)
{
Node *z = new Node(y->t, y->leaf);
z->n = t - 1;

for (int j = 0; j < t - 1; j++)
z->keys[j] = y->keys[j + t];

if (y->leaf == false)
{
for (int j = 0; j < t; j++)
z->C[j] = y->C[j + t];
}

y->n = t - 1;
for (int j = n; j >= i + 1; j--)
C[j + 1] = C[j];

C[i + 1] = z;

for (int j = n - 1; j >= i; j--)
keys[j + 1] = keys[j];

keys[i] = y->keys[t - 1];
n = n + 1;
}

int main()
{
BTree t(3);
t.insert(8);
t.insert(9);
t.insert(10);
t.insert(11);
t.insert(15);
t.insert(16);
t.insert(17);
t.insert(18);
t.insert(20);
t.insert(23);

cout << "The B-tree is: ";
t.traverse();
}
//-------------------------------

// Deleting a key from a B-tree in C++

#include <iostream>
using namespace std;

class BTreeNode
{
int *keys;
int t;
BTreeNode **C;
int n;
bool leaf;

public:
BTreeNode(int _t, bool _leaf);

void traverse();

int findKey(int k);
void insertNonFull(int k);
void splitChild(int i, BTreeNode *y);
void deletion(int k);
void removeFromLeaf(int idx);
void removeFromNonLeaf(int idx);
int getPredecessor(int idx);
int getSuccessor(int idx);
void fill(int idx);
void borrowFromPrev(int idx);
void borrowFromNext(int idx);
void merge(int idx);
friend class BTree;
};

class BTree
{
BTreeNode *root;
int t;

public:
BTree(int _t)
{
root = NULL;
t = _t;
}

void traverse()
{
if (root != NULL)
root->traverse();
}

void insertion(int k);

void deletion(int k);
};

// B tree node
BTreeNode::BTreeNode(int t1, bool leaf1)
{
t = t1;
leaf = leaf1;

keys = new int[2 * t - 1];
C = new BTreeNode *[2 * t];

n = 0;
}

// Find the key
int BTreeNode::findKey(int k)
{
int idx = 0;
while (idx < n && keys[idx] < k)
++idx;
return idx;
}

// Deletion operation
void BTreeNode::deletion(int k)
{
int idx = findKey(k);

if (idx < n && keys[idx] == k)
{
if (leaf)
removeFromLeaf(idx);
else
removeFromNonLeaf(idx);
}
else
{
if (leaf)
{
cout << "The key " << k << " is does not exist in the tree\n";
return;
}

bool flag = ((idx == n) ? true : false);

if (C[idx]->n < t)
fill(idx);

if (flag && idx > n)
C[idx - 1]->deletion(k);
else
C[idx]->deletion(k);
}
return;
}

// Remove from the leaf
void BTreeNode::removeFromLeaf(int idx)
{
for (int i = idx + 1; i < n; ++i)
keys[i - 1] = keys[i];

n--;

return;
}

// Delete from non leaf node
void BTreeNode::removeFromNonLeaf(int idx)
{
int k = keys[idx];

if (C[idx]->n >= t)
{
int pred = getPredecessor(idx);
keys[idx] = pred;
C[idx]->deletion(pred);
}

else if (C[idx + 1]->n >= t)
{
int succ = getSuccessor(idx);
keys[idx] = succ;
C[idx + 1]->deletion(succ);
}

else
{
merge(idx);
C[idx]->deletion(k);
}
return;
}

int BTreeNode::getPredecessor(int idx)
{
BTreeNode *cur = C[idx];
while (!cur->leaf)
cur = cur->C[cur->n];

return cur->keys[cur->n - 1];
}

int BTreeNode::getSuccessor(int idx)
{
BTreeNode *cur = C[idx + 1];
while (!cur->leaf)
cur = cur->C[0];

return cur->keys[0];
}

void BTreeNode::fill(int idx)
{
if (idx != 0 && C[idx - 1]->n >= t)
borrowFromPrev(idx);

else if (idx != n && C[idx + 1]->n >= t)
borrowFromNext(idx);

else
{
if (idx != n)
merge(idx);
else
merge(idx - 1);
}
return;
}

// Borrow from previous
void BTreeNode::borrowFromPrev(int idx)
{
BTreeNode *child = C[idx];
BTreeNode *sibling = C[idx - 1];

for (int i = child->n - 1; i >= 0; --i)
child->keys[i + 1] = child->keys[i];

if (!child->leaf)
{
for (int i = child->n; i >= 0; --i)
child->C[i + 1] = child->C[i];
}

child->keys[0] = keys[idx - 1];

if (!child->leaf)
child->C[0] = sibling->C[sibling->n];

keys[idx - 1] = sibling->keys[sibling->n - 1];

child->n += 1;
sibling->n -= 1;

return;
}

// Borrow from the next
void BTreeNode::borrowFromNext(int idx)
{
BTreeNode *child = C[idx];
BTreeNode *sibling = C[idx + 1];

child->keys[(child->n)] = keys[idx];

if (!(child->leaf))
child->C[(child->n) + 1] = sibling->C[0];

keys[idx] = sibling->keys[0];

for (int i = 1; i < sibling->n; ++i)
sibling->keys[i - 1] = sibling->keys[i];

if (!sibling->leaf)
{
for (int i = 1; i <= sibling->n; ++i)
sibling->C[i - 1] = sibling->C[i];
}

child->n += 1;
sibling->n -= 1;

return;
}

// Merge
void BTreeNode::merge(int idx)
{
BTreeNode *child = C[idx];
BTreeNode *sibling = C[idx + 1];

child->keys[t - 1] = keys[idx];

for (int i = 0; i < sibling->n; ++i)
child->keys[i + t] = sibling->keys[i];

if (!child->leaf)
{
for (int i = 0; i <= sibling->n; ++i)
child->C[i + t] = sibling->C[i];
}

for (int i = idx + 1; i < n; ++i)
keys[i - 1] = keys[i];

for (int i = idx + 2; i <= n; ++i)
C[i - 1] = C[i];

child->n += sibling->n + 1;
n--;

delete (sibling);
return;
}

// Insertion operation
void BTree::insertion(int k)
{
if (root == NULL)
{
root = new BTreeNode(t, true);
root->keys[0] = k;
root->n = 1;
}
else
{
if (root->n == 2 * t - 1)
{
BTreeNode *s = new BTreeNode(t, false);

s->C[0] = root;

s->splitChild(0, root);

int i = 0;
if (s->keys[0] < k)
i++;
s->C[i]->insertNonFull(k);

root = s;
}
else
root->insertNonFull(k);
}
}

// Insertion non full
void BTreeNode::insertNonFull(int k)
{
int i = n - 1;

if (leaf == true)
{
while (i >= 0 && keys[i] > k)
{
keys[i + 1] = keys[i];
i--;
}

keys[i + 1] = k;
n = n + 1;
}
else
{
while (i >= 0 && keys[i] > k)
i--;

if (C[i + 1]->n == 2 * t - 1)
{
splitChild(i + 1, C[i + 1]);

if (keys[i + 1] < k)
i++;
}
C[i + 1]->insertNonFull(k);
}
}

// Split child
void BTreeNode::splitChild(int i, BTreeNode *y)
{
BTreeNode *z = new BTreeNode(y->t, y->leaf);
z->n = t - 1;

for (int j = 0; j < t - 1; j++)
z->keys[j] = y->keys[j + t];

if (y->leaf == false)
{
for (int j = 0; j < t; j++)
z->C[j] = y->C[j + t];
}

y->n = t - 1;

for (int j = n; j >= i + 1; j--)
C[j + 1] = C[j];

C[i + 1] = z;

for (int j = n - 1; j >= i; j--)
keys[j + 1] = keys[j];

keys[i] = y->keys[t - 1];

n = n + 1;
}

// Traverse
void BTreeNode::traverse()
{
int i;
for (i = 0; i < n; i++)
{
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}

if (leaf == false)
C[i]->traverse();
}

// Delete Operation
void BTree::deletion(int k)
{
if (!root)
{
cout << "The tree is empty\n";
return;
}

root->deletion(k);

if (root->n == 0)
{
BTreeNode *tmp = root;
if (root->leaf)
root = NULL;
else
root = root->C[0];

delete tmp;
}
return;
}

int main()
{
BTree t(3);
t.insertion(8);
t.insertion(9);
t.insertion(10);
t.insertion(11);
t.insertion(15);
t.insertion(16);
t.insertion(17);
t.insertion(18);
t.insertion(20);
t.insertion(23);

cout << "The B-tree is: ";
t.traverse();

t.deletion(20);

cout << "\nThe B-tree is: ";
t.traverse();
}```