0

I have the following python code which sets the root of an AVL tree to a specified value. But it seems that setting the root variable of the class has no effect when done by passing it through a function in the same class.

class AVLTree:
    class AVLNode:
        def __init__(self, value) -> None:
            self.value = value

    def __init__(self) -> None:
        self._root = None

    def insert(self, value: int) -> None:
        return self._insert(value, self._root)

    def _insert(self, value, node):
        if node is None:
            node = value
        return


avl = AVLTree()
avl.insert(5)
print(avl._root)

Prints None

It seems that passing the class variable self._root as a parameter to a member method does not change it's value.

I read that python passes all class members by reference and only immutable types (int, etc.) as values.

Any idea why i am not able to modify the value of self._root in _insert function and how can i do that? Thank you

Help Helper
  • 15
  • 1
  • 6
  • 1
    Python passes all objects the same way – there is no distinction between class members and immutable types. ``self._root`` *evaluates to* the object referred to by ``self._root``, and that object is passed on. The object has no idea about *any* of its aliases, including ``self._root``. You seem to want to have ``self._root`` refer both to the *value of* ``self._root`` (``if node is None``) and the *expression* ``self._root`` (``node = value``), is that correct? – MisterMiyagi Jul 06 '20 at 14:34
  • None is a value. You have to pass an object which can be modified. – Pramote Kuacharoen Jul 06 '20 at 14:38
  • Related questions for separation of expressions and their values: [In x = 1, are both x and 1 objects?](https://stackoverflow.com/questions/62433210/in-x-1-are-both-x-and-1-objects) and value reference semantics: [Are python variables pointers? or else what are they?](https://stackoverflow.com/questions/13530998/are-python-variables-pointers-or-else-what-are-they) – MisterMiyagi Jul 06 '20 at 14:43

1 Answers1

1

You have complete control over how _insert is called. Simply don't call it with node=None. Something like

def insert(self, value: int) -> None:
    if self._root is None:
        self._root = self.AVLNode(value)
    else:
        self._insert(value, self._root)

def _insert(self, value, node):
    # Assume node is not None
    ...

(Unrelated, your AVLNode class also has to store pointers to its two children, and _insert needs to update those appropriately.)

chepner
  • 497,756
  • 71
  • 530
  • 681
  • Hello, thanks for this, but after root gets initialized ` self._root = AVLNode(value)` then calling `_insert` (else clause).. then if i make changes to node (which i assume to be _root) then those changes don't persist .. this is what i am working with https://pastebin.com/j6bMQsai, after setting the root in `insert` as per your code, if i then pass the root to `_insert` then try to add children, they are never added.. i can't seem to work with root when passes to `_insert` as `node`. even tho its already initialized and is NOT none. Any clue? (root has no left or right child ever) – Help Helper Jul 06 '20 at 14:45
  • I think the "Unrelated" might be the solution to the issue in my comment above, thanks i will take a look! – Help Helper Jul 06 '20 at 14:48
  • Keep in mind that when you try to insert a value into an existing tree, it will fall into one of three cases: 1) It's already present at the root value 2) It will need to be inserted into the left subtree 3) It will need to be inserted into the right subtree. AVL trees complicate this a little bit in that any given insertion can cause a rotation that changes which node is considered the root, so as to maintain the height invariant. – chepner Jul 06 '20 at 14:53