1

I'm trying to implement a 2-3 Tree in Python (summer fun).

I'm at a stage where if a node has less than 2 children, I want to insert a new node in its "kids" list.

I thought this was a simple process of appending a new node object to the kids list. However, this seems to set the kids list of the new node from what is "[ ]" on construction to "[pointer]". And that pointer points to... the new object itself! And that continues recursively until stack overflow. All this is triggered by a simple append!

Any thoughts? I can code a workaround, but I really want to understand the engineering behind this.

class Node:
    def __init__(self, data = [], kids = []):
        if not isinstance(data, list):
            data = [data]
        self.data = data
        self.kids = kids

class TwoThreeTree:
    def __init__(self):
        self.root = None

    def insert(self, n):
        if not isinstance(n, Node):
            n = Node(n)
        if not self.root:
            self.root = n
        else:
            self.root = self._insert(n, self.root)

    def _insert(self, n, cur):
        if len(cur.kids) <= 2:
            cur.kids.append(n) #Issue occurs here
        elif n.data <= cur.data[0]:
            cur.kids[0] = self._insert(n, cur.kids[0])
        elif n.data <= cur.data[1]:
            cur.kids[1] = self._insert(n, cur.kids[1])
        elif len(cur.kids) == 3:
            cur.kids[2] = self._insert(n, cur.kids[2])

        cur = self.reorg(cur)
        return cur

As you can see, the pointers point to each other forever.

Extra: Full code for testing

def reorg(self, cur):
        cur.kids = sorted(cur.kids, key=lambda x: x.data)

        if len(self.root.kids) == 1:
            other = cur.kids[0]
            cur.kids = []
            if cur.data == min(cur.data, other.data):
                small = cur
                big = other
            else:
                small = other
                big = cur

            cur.data = [small.data[-1], big.data[-1]]
            cur.kids =[small, big]

        elif len(cur.kids) == 4:
            kid1 = Node([cur.kids[0].data[-1], cur.kids[1].data[-1]],
                        [cur.kids[0], cur.kids[1]])
            kid2 = Node([cur.kids[2].data[-1], cur.kids[3].data[-1]],
                        [cur.kids[2], cur.kids[3]])
            cur.kids = [kid1, kid2]

        cur.data = [cur.kids[0].data[-1], cur.kids[1].data[-1]]

        return cur

    def preOrder(self, cur=-1):
        if cur == -1:
            cur = self.root
        if cur:
            print(cur.data)
            if cur.kids:
                for kid in cur.kids:
                    self.preOrder(kid)

t = TwoThreeTree()
for x in [1, 2, 3, 4, 5]:
    t.insert(x)

t.preOrder()
Nick
  • 581
  • 1
  • 7
  • 13
  • What Python version are you using? I don't get to a stack overflow in either 2.7 or 3.5.4; instead, I get to a data fault (different for the two versions). – Prune May 31 '17 at 00:07
  • 2
    Your issue is not in `_insert`, but in the `__init__` function where you initialize `kids` with a default argument. That doesn't create a separate list for each `Node` instance, instead, they're all sharing a reference to the same list (which was created when the function was compiled, not when it runs). – Blckknght May 31 '17 at 00:07

0 Answers0