title: Red Black Tree AttributeError on NoneType
body: <p>My problem stems from trying to insert the last node (red one) in these two scenarios:</p>
  
  <p><img src="https://i.stack.imgur.com/01uG9.png" alt="enter image description here"></p>
  
  <p><img src="https://i.stack.imgur.com/G2MYw.png" alt="enter image description here"></p>
  
  <p>This is the traceback message I get:</p>
  
  <pre><code>Traceback (most recent call last):
    File "&lt;stdin&gt;", line 1, in &lt;module&gt;
    File "/home/chris/Documents/CS223/Assignment4/redblacktree.py", line 24, in insert
      self._insert(Node(data, None, 0))
    File "/home/chris/Documents/CS223/Assignment4/redblacktree.py", line 67, in _insert
      self._insertFix(z)
    File "/home/chris/Documents/CS223/Assignment4/redblacktree.py", line 71, in _insertFix
      while(z.parent.color is 1):
  AttributeError: 'NoneType' object has no attribute 'color'
  </code></pre>
  
  <p>The algorithms I am using are from the book "Introduction to Algorithms, 3rd Ed. by
  Cormen".</p>
  
  <p>I cannot for the life of me figure out how "z.parent" is a <code>NoneType</code> object when it in fact has its parent as the node above it.</p>
  
  <p>Here is the code in question:</p>
  
  <pre><code>class RBTree:
      __slots__ = {'_root'}
  
      def __init__(self):
          self._root = None
  
      def insert(self, data):
          if(self._root is None):
              self._root = Node(data, None, 0)
          else:
              self._insert(Node(data, None, 0))
  
      def _insert(self, z):
          y = None
          x = self._root
          while(x is not None):
              y = x
              if(z.data &lt; x.data):
                  x = x.left
              else:
                  x = x.right
          z.parent = y
          if(y is None):
              self._root = z
          elif(z.data &lt; y.data):
              y.left = z
          else:
              y.right = z
  
          z.left = None
          z.right = None
          z.color = 1
          self._insertFix(z)
  
      def _insertFix(self, z):
          print("Print z from _insertFix: " + str(z.data) + "\n")
          while(z.parent.color is 1):
              if(z.parent == z.parent.parent.left):
                  y = z.parent.parent.right
                  if(y.color is 1):
                      z.parent.color = 0
                      y.color = 0
                      z.parent.parent.color = 1
                      z = z.parent.parent
                  else:
                      if(z == z.parent.right):
                          z = z.parent
                          self._rotateLeft(z)
                      z.parent.color = 0
                      z.parent.parent = 1
                      self._rotateRight(z.parent.parent)
              else:
                  y = z.parent.parent.left
                  if(y.color is 1):
                      z.parent.color = 0
                      y.color = 0
                      z.parent.parent.color = 1
                      z = z.parent.parent
                  else:
                      if(z == z.parent.left):
                          z = z.parent
                          self._rotateRight(z)
                      z.parent.color = 0
                      z.parent.parent = 1
                      self._rotateLeft(z.parent.parent)
          self._root.color = 0
  
      def _rotateLeft(self, x):
          y = x.right
          x.right = y.left
          if(y.left is not None):
              y.left.parent = x
          y.parent = x.parent
          if(x.parent is not None):
              self._root = y
          elif(x == x.parent.left):
              x.parent.left = y
          else:
              x.parent.right = y
          y.left = x
          x.parent = y
  
      def _rotateRight(self, x):
          x = y.left
          y.left = x.right
          if(x.right is not None):
              x.right.parent = y
          x.parent = y.parent
          if(y.parent is None):
              self._root = x
          elif(y == y.parent.right):
              y.parent.right = x
          else:
              y.parent.left = x
          x.right = y
          y.parent = x
  
  class Node:
      __slots__ = {"_left", "_right", "_parent", "_data", "_color"}
  
      def __init__(self, data, parent, color):
          self._left = None
          self._right = None
          self._parent = parent
          self._data = data
          self._color = color
  </code></pre>
  
  <p>I am testing my code using the interpreter, as I don't have a <code>main</code> yet to be called. I think I just need a push in the right direction.</p>