avl tree implementation

[pallid shore]

hey, im trying to implement an avl tree by myself, was wondering if the struct i made for the avl node looks good so far (in particular the destructor, not sure if im supposed to be calling the destructor for the left and right before deleting them, or if the destructor is just called) and if anyone notices anything questionable.

struct avlNode
{
    int m_data;
    avlNode* m_left;
    avlNode* m_right;
    int height;

    avlNode() { m_data = 0; m_left = m_right = nullptr; height = 0;}
    avlNode(int data) { m_data = data; m_left = m_right = nullptr; height = 0;}
    void setLeft(avlNode* x) {m_left = x;}
    void setRight(avlNode* x) {m_right = x;}
    int getData() {return m_data;}

    avlNode* getLeft() {return m_left;}
    avlNode* getRight() {return m_right;}
    int getHeight() {return height;}
    void setHeight(){
        height = m_left->getHeight() - m_right->getHeight();
    }

    ~avlNode()
    {
        delete m_left;
        m_left = nullptr;
        delete m_right;
        m_right = nullptr;
    }
};

[gloomy halo]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

[sharp garnet]

members of structures are defaultly public, so there's no reason to use getter/setter methods

node.setLeft(l_node) is equivalent to node.m_left = l_node

it's your choice which you'd rather have

in my opinion, the ladder is superior for elementary data structures like these

secondly, your destructor models that each node owns its children

you can get rid of your destructor altogether by using std::unique_ptr

either way, there's no need to be setting the left and right children to nullptr because the object won't even exist after the destructor is called anyways

for something trivial like this i'd stick to simple pointers though

template <typename T>
struct avl_node {
    T data;
    avl_node<T>* left = nullptr;
    avl_node<T>* right = nullptr;
    int height = 0;

    void update_height() {
        if(left && right)
          height = left->height - right->height;
    }
    
    ~avl_node() {
        delete left;
        delete right;
    }
};

making it generic will also make it useful

example usage:

...
using avl_num = avl_node<int>;

avl_num top{5};

top.left = new avl_num{6};
top.right = new avl_num{3};

calling update_height would be pretty inconvenient, so you may want to use a method to automatically update the height whenever left or right changes

[echo spear]

You're missing copy and move operations

Writing them should be your first priority, without them the class is practically unusable in any real-world program

[pallid shore]

damn i need to review templates. Also, does it matter whether height is an unsigned or just int, and if we set height = 0 in the struct, it doesn't just stay 0 im guessing right?

[pallid shore]

gotchu, copy and move constructors as well as operators right?

thats the BIG 5 or some shit in cpp i think

[pallid shore]

also would you recommend not having a parameterized/default constructor? since i see you dont have any in the struct

[sharp garnet]

i'd just let data be default constructed, e.g. T data() instead. constructors are overkill unless you want something special

and i know that there's some logic that comes with AVL trees, so you indeed may want something special

[sharp garnet]

you're actually right, height should be signed because it can be less than zero

and 0 is just height's default value

it can still change

it would only not be able to change if you made it const

[pallid shore]

actually i dont think im right, how can the height be less than 0? I think we both are confusing the balance factor (left height - right height) because that in fact can be negative, but height itself cant i think

[sharp garnet]

i thought your height was your balance factor because of how you implemented setHeight

[echo spear]

Yeah. By "operations" I meant "constructors and assignment operators" :P

[pallid shore]

//move constructor
    avlNode(avlNode<T> && rhs) {
        m_data = std::move(rhs.m_data);
        m_left = rhs.m_left;
        rhs.m_left = nullptr;
        m_right = rhs.m_right;
        rhs.m_right = nullptr;
    } 

this isnt working for some reason idk

[echo spear]

This looks like it should work 🤷‍♂️

[pallid shore]

idk imma start working on the avl tree class

actually imma do the operators

[sharp garnet]

are you getting an error?

[pallid shore]

no im just couting the data of the one I std::moved and its still giving me the data as if it wasnt moved

[sharp garnet]

how are you invoking the constructor?

[pallid shore]

#include "avl.hpp"

int main()
{
    // avlNode<int> first(5);
    // avlNode<int>* psecond = new avlNode<int>(8);
    // avlNode<int>* pthird = new avlNode<int>(3);
    // avlNode<int> third(7, pthird, psecond, 1);
    
    // std::cout << third.m_left->height;
    avlNode<int> once(5);
    avlNode<int> twice(std::move(once));
    std::cout << once.m_data << " " << twice.m_data << "\n";
}

[sharp garnet]

moving an integer just copies the integer

oops

it included ur code too lol

;compile ```cpp
#include <iostream>
#include <utility>

int main() {
int a = 5;
int b;
b = std::move(a);
std::cout << a << '\n' << b << '\n';
}

[twin badger]

Program Output

5
5

cynic746 | 49ms | c++ | x86-64 gcc 14.2 | godbolt.org

[sharp garnet]

we move for efficiency

but you can't get more efficient than copying a data type whose size is equal to or less than the size of a pointer on a certain architecture

so you'll never see someone manually move an integer

[pallid shore]

gotchhuuuu

i just changed it to this

int main()
{
    // avlNode<int> first(5);
    // avlNode<int>* psecond = new avlNode<int>(8);
    // avlNode<int>* pthird = new avlNode<int>(3);
    // avlNode<int> third(7, pthird, psecond, 1);
    
    // std::cout << third.m_left->height;
    avlNode<std::string> once("hello");
    avlNode<std::string> twice(std::move(once));
    std::cout << once.m_data << "\n" << twice.m_data << "\n";
}

and it moved correctly

since moving a string is actually efficient