El árbol AVL es un árbol de búsqueda binaria (BST) autoequilibrado donde la diferencia entre las alturas de los subárboles izquierdo y derecho no puede ser más de uno para todos los Nodes. La inserción y eliminación en árboles AVL se han discutido en el artículo anterior . En este artículo, se analizan las operaciones de inserción, búsqueda y eliminación en árboles AVL que también tienen un puntero principal en su estructura .
Definición de Node de árbol AVL:
C++
struct AVLwithparent {
// Pointer to the left and the
// right subtree
struct AVLwithparent* left;
struct AVLwithparent* right;
// Stores the data in the node
int key;
// Stores the parent pointer
struct AVLwithparent* par;
// Stores the height of the
// current tree
int height;
}
Producción:
Node: 30, Parent Node: NULL Node: 20, Parent Node: 30 Node: 10, Parent Node: 20 Node: 25, Parent Node: 20 Node: 40, Parent Node: 30 Node: 50, Parent Node: 40
Representación del Node :
A continuación se muestra el ejemplo de un árbol AVL que contiene un puntero principal:
Operación de inserción: el procedimiento de inserción es similar al de un árbol AVL normal sin un puntero principal, pero en este caso, los punteros principales deben actualizarse con cada inserción y rotación en consecuencia. Siga los pasos a continuación para realizar la operación de inserción:
- Realice una inserción BST estándar para que el Node se coloque en su posición correcta.
- Aumente la altura de cada Node encontrado en 1 mientras encuentra la posición correcta para insertar el Node.
- Actualice los punteros principal y secundario del Node insertado y su principal respectivamente.
- Desde el Node insertado hasta el Node raíz, verifique si se cumple la condición AVL para cada Node en esta ruta.
- Si w es el Node donde la condición AVL no se cumple, entonces tenemos 4 casos:
- Caso izquierdo izquierdo: (si el subárbol izquierdo del hijo izquierdo de w tiene el Node insertado)
- Caso izquierdo derecho: (si el subárbol derecho del hijo izquierdo de w tiene el Node insertado)
- Caso derecho izquierdo: (si el subárbol izquierdo del hijo derecho de w tiene el Node insertado)
- Right Right Case: (si el subárbol derecho del hijo derecho de w tiene el Node insertado)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// AVL tree node
struct AVLwithparent {
struct AVLwithparent* left;
struct AVLwithparent* right;
int key;
struct AVLwithparent* par;
int height;
};
// Function to update the height of
// a node according to its children's
// node's heights
void Updateheight(
struct AVLwithparent* root)
{
if (root != NULL) {
// Store the height of the
// current node
int val = 1;
// Store the height of the left
// and right subtree
if (root->left != NULL)
val = root->left->height + 1;
if (root->right != NULL)
val = max(
val, root->right->height + 1);
// Update the height of the
// current node
root->height = val;
}
}
// Function to handle Left Left Case
struct AVLwithparent* LLR(
struct AVLwithparent* root)
{
// Create a reference to the
// left child
struct AVLwithparent* tmpnode = root->left;
// Update the left child of the
// root to the right child of the
// current left child of the root
root->left = tmpnode->right;
// Update parent pointer of the
// left child of the root node
if (tmpnode->right != NULL)
tmpnode->right->par = root;
// Update the right child of
// tmpnode to root
tmpnode->right = root;
// Update parent pointer of
// the tmpnode
tmpnode->par = root->par;
// Update the parent pointer
// of the root
root->par = tmpnode;
// Update tmpnode as the left or the
// right child of its parent pointer
// according to its key value
if (tmpnode->par != NULL
&& root->key < tmpnode->par->key) {
tmpnode->par->left = tmpnode;
}
else {
if (tmpnode->par != NULL)
tmpnode->par->right = tmpnode;
}
// Make tmpnode as the new root
root = tmpnode;
// Update the heights
Updateheight(root->left);
Updateheight(root->right);
Updateheight(root);
Updateheight(root->par);
// Return the root node
return root;
}
// Function to handle Right Right Case
struct AVLwithparent* RRR(
struct AVLwithparent* root)
{
// Create a reference to the
// right child
struct AVLwithparent* tmpnode = root->right;
// Update the right child of the
// root as the left child of the
// current right child of the root
root->right = tmpnode->left;
// Update parent pointer of the
// right child of the root node
if (tmpnode->left != NULL)
tmpnode->left->par = root;
// Update the left child of the
// tmpnode to root
tmpnode->left = root;
// Update parent pointer of
// the tmpnode
tmpnode->par = root->par;
// Update the parent pointer
// of the root
root->par = tmpnode;
// Update tmpnode as the left or
// the right child of its parent
// pointer according to its key value
if (tmpnode->par != NULL
&& root->key < tmpnode->par->key) {
tmpnode->par->left = tmpnode;
}
else {
if (tmpnode->par != NULL)
tmpnode->par->right = tmpnode;
}
// Make tmpnode as the new root
root = tmpnode;
// Update the heights
Updateheight(root->left);
Updateheight(root->right);
Updateheight(root);
Updateheight(root->par);
// Return the root node
return root;
}
// Function to handle Left Right Case
struct AVLwithparent* LRR(
struct AVLwithparent* root)
{
root->left = RRR(root->left);
return LLR(root);
}
// Function to handle right left case
struct AVLwithparent* RLR(
struct AVLwithparent* root)
{
root->right = LLR(root->right);
return RRR(root);
}
// Function to insert a node in
// the AVL tree
struct AVLwithparent* Insert(
struct AVLwithparent* root,
struct AVLwithparent* parent,
int key)
{
if (root == NULL) {
// Create and assign values
// to a new node
root = new struct AVLwithparent;
// If the root is NULL
if (root == NULL) {
cout << "Error in memory"
<< endl;
}
// Otherwise
else {
root->height = 1;
root->left = NULL;
root->right = NULL;
root->par = parent;
root->key = key;
}
}
else if (root->key > key) {
// Recur to the left subtree
// to insert the node
root->left = Insert(root->left,
root, key);
// Store the heights of the
// left and right subtree
int firstheight = 0;
int secondheight = 0;
if (root->left != NULL)
firstheight = root->left->height;
if (root->right != NULL)
secondheight = root->right->height;
// Balance the tree if the
// current node is not balanced
if (abs(firstheight
- secondheight)
== 2) {
if (root->left != NULL
&& key < root->left->key) {
// Left Left Case
root = LLR(root);
}
else {
// Left Right Case
root = LRR(root);
}
}
}
else if (root->key < key) {
// Recur to the right subtree
// to insert the node
root->right = Insert(root->right,
root, key);
// Store the heights of the
// left and right subtree
int firstheight = 0;
int secondheight = 0;
if (root->left != NULL)
firstheight
= root->left->height;
if (root->right != NULL)
secondheight = root->right->height;
// Balance the tree if the
// current node is not balanced
if (abs(firstheight - secondheight) == 2) {
if (root->right != NULL
&& key < root->right->key) {
// Right Left Case
root = RLR(root);
}
else {
// Right Right Case
root = RRR(root);
}
}
}
// Case when given key is already
// in the tree
else {
}
// Update the height of the
// root node
Updateheight(root);
// Return the root node
return root;
}
// Function to print the preorder
// traversal of the AVL tree
void printpreorder(
struct AVLwithparent* root)
{
// Print the node's value along
// with its parent value
cout << "Node: " << root->key
<< ", Parent Node: ";
if (root->par != NULL)
cout << root->par->key << endl;
else
cout << "NULL" << endl;
// Recur to the left subtree
if (root->left != NULL) {
printpreorder(root->left);
}
// Recur to the right subtree
if (root->right != NULL) {
printpreorder(root->right);
}
}
// Driver Code
int main()
{
struct AVLwithparent* root;
root = NULL;
// Function Call to insert nodes
root = Insert(root, NULL, 10);
root = Insert(root, NULL, 20);
root = Insert(root, NULL, 30);
root = Insert(root, NULL, 40);
root = Insert(root, NULL, 50);
root = Insert(root, NULL, 25);
// Function call to print the tree
printpreorder(root);
}
Producción:
Node: 30, Parent Node: NULL Node: 20, Parent Node: 30 Node: 10, Parent Node: 20 Node: 25, Parent Node: 20 Node: 40, Parent Node: 30 Node: 50, Parent Node: 40
Complejidad temporal: O(log N), donde N es el número de Nodes del árbol .
Espacio Auxiliar: O(1)
Operación de búsqueda: la operación de búsqueda en un árbol AVL con punteros principales es similar a la operación de búsqueda en un árbol de búsqueda binaria normal . Siga los pasos a continuación para realizar la operación de búsqueda:
- Comience desde el Node raíz.
- Si el Node raíz es NULL , devuelve falso .
- Compruebe si el valor del Node actual es igual al valor del Node que se va a buscar. En caso afirmativo, devuelve verdadero .
- Si el valor del Node actual es menor que la clave buscada, vuelva al subárbol derecho.
- Si el valor del Node actual es mayor que la clave buscada, vuelva al subárbol izquierdo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// AVL tree node
struct AVLwithparent {
struct AVLwithparent* left;
struct AVLwithparent* right;
int key;
struct AVLwithparent* par;
int height;
};
// Function to update the height of
// a node according to its children's
// node's heights
void Updateheight(struct AVLwithparent* root)
{
if (root != NULL) {
// Store the height of the
// current node
int val = 1;
// Store the height of the left
// and the right subtree
if (root->left != NULL)
val = root->left->height + 1;
if (root->right != NULL)
val = max(
val, root->right->height + 1);
// Update the height of the
// current node
root->height = val;
}
}
// Function to handle Left Left Case
struct AVLwithparent* LLR(
struct AVLwithparent* root)
{
// Create a reference to the
// left child
struct AVLwithparent* tmpnode = root->left;
// Update the left child of the
// root to the right child of the
// current left child of the root
root->left = tmpnode->right;
// Update parent pointer of the left
// child of the root node
if (tmpnode->right != NULL)
tmpnode->right->par = root;
// Update the right child of
// tmpnode to root
tmpnode->right = root;
// Update parent pointer of tmpnode
tmpnode->par = root->par;
// Update the parent pointer of root
root->par = tmpnode;
// Update tmpnode as the left or
// the right child of its parent
// pointer according to its key value
if (tmpnode->par != NULL
&& root->key < tmpnode->par->key) {
tmpnode->par->left = tmpnode;
}
else {
if (tmpnode->par != NULL)
tmpnode->par->right = tmpnode;
}
// Make tmpnode as the new root
root = tmpnode;
// Update the heights
Updateheight(root->left);
Updateheight(root->right);
Updateheight(root);
Updateheight(root->par);
// Return the root node
return root;
}
// Function to handle Right Right Case
struct AVLwithparent* RRR(
struct AVLwithparent* root)
{
// Create a reference to the
// right child
struct AVLwithparent* tmpnode = root->right;
// Update the right child of the
// root as the left child of the
// current right child of the root
root->right = tmpnode->left;
// Update parent pointer of the right
// child of the root node
if (tmpnode->left != NULL)
tmpnode->left->par = root;
// Update the left child of the
// tmpnode to root
tmpnode->left = root;
// Update parent pointer of tmpnode
tmpnode->par = root->par;
// Update the parent pointer of root
root->par = tmpnode;
// Update tmpnode as the left or
// the right child of its parent
// pointer according to its key value
if (tmpnode->par != NULL
&& root->key < tmpnode->par->key) {
tmpnode->par->left = tmpnode;
}
else {
if (tmpnode->par != NULL)
tmpnode->par->right = tmpnode;
}
// Make tmpnode as the new root
root = tmpnode;
// Update the heights
Updateheight(root->left);
Updateheight(root->right);
Updateheight(root);
Updateheight(root->par);
// Return the root node
return root;
}
// Function to handle Left Right Case
struct AVLwithparent* LRR(
struct AVLwithparent* root)
{
root->left = RRR(root->left);
return LLR(root);
}
// Function to handle right left case
struct AVLwithparent* RLR(
struct AVLwithparent* root)
{
root->right = LLR(root->right);
return RRR(root);
}
// Function to insert a node in
// the AVL tree
struct AVLwithparent* Insert(
struct AVLwithparent* root,
struct AVLwithparent* parent,
int key)
{
if (root == NULL) {
// Create and assign values
// to a new node
root = new struct AVLwithparent;
if (root == NULL) {
cout << "Error in memory" << endl;
}
// Otherwise
else {
root->height = 1;
root->left = NULL;
root->right = NULL;
root->par = parent;
root->key = key;
}
}
else if (root->key > key) {
// Recur to the left subtree
// to insert the node
root->left = Insert(root->left,
root, key);
// Stores the heights of the
// left and right subtree
int firstheight = 0;
int secondheight = 0;
if (root->left != NULL)
firstheight = root->left->height;
if (root->right != NULL)
secondheight = root->right->height;
// Balance the tree if the
// current node is not balanced
if (abs(firstheight
- secondheight)
== 2) {
if (root->left != NULL
&& key < root->left->key) {
// Left Left Case
root = LLR(root);
}
else {
// Left Right Case
root = LRR(root);
}
}
}
else if (root->key < key) {
// Recur to the right subtree
// to insert the node
root->right = Insert(root->right, root, key);
// Store the heights of the left
// and right subtree
int firstheight = 0;
int secondheight = 0;
if (root->left != NULL)
firstheight = root->left->height;
if (root->right != NULL)
secondheight = root->right->height;
// Balance the tree if the
// current node is not balanced
if (abs(firstheight
- secondheight)
== 2) {
if (root->right != NULL
&& key < root->right->key) {
// Right Left Case
root = RLR(root);
}
else {
// Right Right Case
root = RRR(root);
}
}
}
// Case when given key is
// already in tree
else {
}
// Update the height of the
// root node
Updateheight(root);
// Return the root node
return root;
}
// Function to find a key in AVL tree
bool AVLsearch(
struct AVLwithparent* root, int key)
{
// If root is NULL
if (root == NULL)
return false;
// If found, return true
else if (root->key == key)
return true;
// Recur to the left subtree if
// the current node's value is
// greater than key
else if (root->key > key) {
bool val = AVLsearch(root->left, key);
return val;
}
// Otherwise, recur to the
// right subtree
else {
bool val = AVLsearch(root->right, key);
return val;
}
}
// Driver Code
int main()
{
struct AVLwithparent* root;
root = NULL;
// Function call to insert the nodes
root = Insert(root, NULL, 10);
root = Insert(root, NULL, 20);
root = Insert(root, NULL, 30);
root = Insert(root, NULL, 40);
root = Insert(root, NULL, 50);
root = Insert(root, NULL, 25);
// Function call to search for a node
bool found = AVLsearch(root, 40);
if (found)
cout << "value found";
else
cout << "value not found";
return 0;
}
Producción:
value found
Complejidad Temporal: O(log N), donde N es el número de Nodes del árbol
Espacio Auxiliar: O(1)
Operación de eliminación: el procedimiento de eliminación es similar al de un árbol AVL normal sin un puntero principal, pero en este caso, las referencias a los punteros principales deben actualizarse con cada eliminación y rotación en consecuencia. Siga los pasos a continuación para realizar la operación de eliminación:
- Realice el procedimiento de borrado como en un BST normal .
- Desde el Node que se ha eliminado, muévase hacia la raíz.
- En cada Node de la ruta, actualice la altura del Node.
- Compruebe las condiciones de AVL en cada Node. Sean 3 Nodes: w, x, y donde w es el Node actual, x es la raíz del subárbol de w que tiene mayor altura e y es la raíz del subárbol de x que tiene mayor altura.
- Si el Node w está desequilibrado, existe uno de los siguientes 4 casos:
- Left Left Case ( x es el hijo izquierdo de w y y es el hijo izquierdo de x )
- Caso izquierdo derecho ( x es el hijo izquierdo de w y y es el hijo derecho de x )
- Caso derecho izquierdo ( x es el hijo derecho de w y y es el hijo izquierdo de x )
- Right Right Case ( x es el hijo derecho de w y y es el hijo derecho de x )
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// AVL tree node
struct AVLwithparent {
struct AVLwithparent* left;
struct AVLwithparent* right;
int key;
struct AVLwithparent* par;
int height;
};
// Function to print the preorder
// traversal of the AVL tree
void printpreorder(struct AVLwithparent* root)
{
// Print the node's value along
// with its parent value
cout << "Node: " << root->key
<< ", Parent Node: ";
if (root->par != NULL)
cout << root->par->key << endl;
else
cout << "NULL" << endl;
// Recur to the left subtree
if (root->left != NULL) {
printpreorder(root->left);
}
// Recur to the right subtree
if (root->right != NULL) {
printpreorder(root->right);
}
}
// Function to update the height of
// a node according to its children's
// node's heights
void Updateheight(
struct AVLwithparent* root)
{
if (root != NULL) {
// Store the height of the
// current node
int val = 1;
// Store the height of the left
// and right subtree
if (root->left != NULL)
val = root->left->height + 1;
if (root->right != NULL)
val = max(
val, root->right->height + 1);
// Update the height of the
// current node
root->height = val;
}
}
// Function to handle Left Left Case
struct AVLwithparent* LLR(
struct AVLwithparent* root)
{
// Create a reference to the
// left child
struct AVLwithparent* tmpnode = root->left;
// Update the left child of the
// root to the right child of the
// current left child of the root
root->left = tmpnode->right;
// Update parent pointer of left
// child of the root node
if (tmpnode->right != NULL)
tmpnode->right->par = root;
// Update the right child of
// tmpnode to root
tmpnode->right = root;
// Update parent pointer of tmpnode
tmpnode->par = root->par;
// Update the parent pointer of root
root->par = tmpnode;
// Update tmpnode as the left or
// the right child of its parent
// pointer according to its key value
if (tmpnode->par != NULL
&& root->key < tmpnode->par->key) {
tmpnode->par->left = tmpnode;
}
else {
if (tmpnode->par != NULL)
tmpnode->par->right = tmpnode;
}
// Make tmpnode as the new root
root = tmpnode;
// Update the heights
Updateheight(root->left);
Updateheight(root->right);
Updateheight(root);
Updateheight(root->par);
// Return the root node
return root;
}
// Function to handle Right Right Case
struct AVLwithparent* RRR(
struct AVLwithparent* root)
{
// Create a reference to the
// right child
struct AVLwithparent* tmpnode = root->right;
// Update the right child of the
// root as the left child of the
// current right child of the root
root->right = tmpnode->left;
// Update parent pointer of the
// right child of the root node
if (tmpnode->left != NULL)
tmpnode->left->par = root;
// Update the left child of the
// tmpnode to root
tmpnode->left = root;
// Update parent pointer of tmpnode
tmpnode->par = root->par;
// Update the parent pointer of root
root->par = tmpnode;
// Update tmpnode as the left or
// the right child of its parent
// pointer according to its key value
if (tmpnode->par != NULL
&& root->key < tmpnode->par->key) {
tmpnode->par->left = tmpnode;
}
else {
if (tmpnode->par != NULL)
tmpnode->par->right = tmpnode;
}
// Make tmpnode as the new root
root = tmpnode;
// Update the heights
Updateheight(root->left);
Updateheight(root->right);
Updateheight(root);
Updateheight(root->par);
// Return the root node
return root;
}
// Function to handle Left Right Case
struct AVLwithparent* LRR(
struct AVLwithparent* root)
{
root->left = RRR(root->left);
return LLR(root);
}
// Function to handle right left case
struct AVLwithparent* RLR(
struct AVLwithparent* root)
{
root->right = LLR(root->right);
return RRR(root);
}
// Function to balance the tree after
// deletion of a node
struct AVLwithparent* Balance(
struct AVLwithparent* root)
{
// Store the current height of
// the left and right subtree
int firstheight = 0;
int secondheight = 0;
if (root->left != NULL)
firstheight = root->left->height;
if (root->right != NULL)
secondheight = root->right->height;
// If current node is not balanced
if (abs(firstheight - secondheight) == 2) {
if (firstheight < secondheight) {
// Store the height of the
// left and right subtree
// of the current node's
// right subtree
int rightheight1 = 0;
int rightheight2 = 0;
if (root->right->right != NULL)
rightheight2 = root->right->right->height;
if (root->right->left != NULL)
rightheight1 = root->right->left->height;
if (rightheight1 > rightheight2) {
// Right Left Case
root = RLR(root);
}
else {
// Right Right Case
root = RRR(root);
}
}
else {
// Store the height of the
// left and right subtree
// of the current node's
// left subtree
int leftheight1 = 0;
int leftheight2 = 0;
if (root->left->right != NULL)
leftheight2 = root->left->right->height;
if (root->left->left != NULL)
leftheight1 = root->left->left->height;
if (leftheight1 > leftheight2) {
// Left Left Case
root = LLR(root);
}
else {
// Left Right Case
root = LRR(root);
}
}
}
// Return the root node
return root;
}
// Function to insert a node in
// the AVL tree
struct AVLwithparent* Insert(
struct AVLwithparent* root,
struct AVLwithparent* parent,
int key)
{
if (root == NULL) {
// Create and assign values
// to a new node
root = new struct AVLwithparent;
if (root == NULL)
cout << "Error in memory" << endl;
else {
root->height = 1;
root->left = NULL;
root->right = NULL;
root->par = parent;
root->key = key;
}
}
else if (root->key > key) {
// Recur to the left subtree
// to insert the node
root->left = Insert(root->left,
root, key);
// Store the heights of the
// left and right subtree
int firstheight = 0;
int secondheight = 0;
if (root->left != NULL)
firstheight = root->left->height;
if (root->right != NULL)
secondheight = root->right->height;
// Balance the tree if the
// current node is not balanced
if (abs(firstheight
- secondheight)
== 2) {
if (root->left != NULL
&& key < root->left->key) {
// Left Left Case
root = LLR(root);
}
else {
// Left Right Case
root = LRR(root);
}
}
}
else if (root->key < key) {
// Recur to the right subtree
// to insert the node
root->right = Insert(root->right,
root, key);
// Store the heights of the left
// and right subtree
int firstheight = 0;
int secondheight = 0;
if (root->left != NULL)
firstheight = root->left->height;
if (root->right != NULL)
secondheight = root->right->height;
// Balance the tree if the
// current node is not balanced
if (abs(firstheight - secondheight) == 2) {
if (root->right != NULL
&& key < root->right->key) {
// Right Left Case
root = RLR(root);
}
else {
// Right Right Case
root = RRR(root);
}
}
}
// Case when given key is
// already in tree
else {
}
// Update the height of the
// root node
Updateheight(root);
// Return the root node
return root;
}
// Function to delete a node from
// the AVL tree
struct AVLwithparent* Delete(
struct AVLwithparent* root,
int key)
{
if (root != NULL) {
// If the node is found
if (root->key == key) {
// Replace root with its
// left child
if (root->right == NULL
&& root->left != NULL) {
if (root->par != NULL) {
if (root->par->key
< root->key)
root->par->right = root->left;
else
root->par->left = root->left;
// Update the height
// of root's parent
Updateheight(root->par);
}
root->left->par = root->par;
// Balance the node
// after deletion
root->left = Balance(
root->left);
return root->left;
}
// Replace root with its
// right child
else if (root->left == NULL
&& root->right != NULL) {
if (root->par != NULL) {
if (root->par->key
< root->key)
root->par->right = root->right;
else
root->par->left = root->right;
// Update the height
// of the root's parent
Updateheight(root->par);
}
root->right->par = root->par;
// Balance the node after
// deletion
root->right = Balance(root->right);
return root->right;
}
// Remove the references of
// the current node
else if (root->left == NULL
&& root->right == NULL) {
if (root->par->key < root->key) {
root->par->right = NULL;
}
else {
root->par->left = NULL;
}
if (root->par != NULL)
Updateheight(root->par);
root = NULL;
return NULL;
}
// Otherwise, replace the
// current node with its
// successor and then
// recursively call Delete()
else {
struct AVLwithparent* tmpnode = root;
tmpnode = tmpnode->right;
while (tmpnode->left != NULL) {
tmpnode = tmpnode->left;
}
int val = tmpnode->key;
root->right
= Delete(root->right, tmpnode->key);
root->key = val;
// Balance the node
// after deletion
root = Balance(root);
}
}
// Recur to the right subtree to
// delete the current node
else if (root->key < key) {
root->right = Delete(root->right, key);
root = Balance(root);
}
// Recur into the right subtree
// to delete the current node
else if (root->key > key) {
root->left = Delete(root->left, key);
root = Balance(root);
}
// Update height of the root
if (root != NULL) {
Updateheight(root);
}
}
// Handle the case when the key to be
// deleted could not be found
else {
cout << "Key to be deleted "
<< "could not be found\n";
}
// Return the root node
return root;
}
// Driver Code
int main()
{
struct AVLwithparent* root;
root = NULL;
// Function call to insert the nodes
root = Insert(root, NULL, 9);
root = Insert(root, NULL, 5);
root = Insert(root, NULL, 10);
root = Insert(root, NULL, 0);
root = Insert(root, NULL, 6);
// Print the tree before deleting node
cout << "Before deletion:\n";
printpreorder(root);
// Function Call to delete node 10
root = Delete(root, 10);
// Print the tree after deleting node
cout << "After deletion:\n";
printpreorder(root);
}
Producción:
Before deletion: Node: 9, Parent Node: NULL Node: 5, Parent Node: 9 Node: 0, Parent Node: 5 Node: 6, Parent Node: 5 Node: 10, Parent Node: 9 After deletion: Node: 6, Parent Node: NULL Node: 5, Parent Node: 6 Node: 0, Parent Node: 5 Node: 9, Parent Node: 6
Complejidad Temporal: O(log N), donde N es el número de Nodes del árbol
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por akshatsachan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA