Source of RBTNode.java

Structures and functions

class RBTNode

  1: //RBTNode.java

  3: class RBTNode
  4: {
  5:     public enum Child
  6:     {
  7:         LEFT, RIGHT
  8:     }

 10:     public enum Color
 11:     {
 12:         RED, BLACK
 13:     }

 15:     public int key;
 16:     public RBTNode parent;
 17:     public RBTNode left;
 18:     public RBTNode right;
 19:     public Color color;

 21:     public RBTNode(int nodeKey, RBTNode parentNode, boolean isRed)
 22:     {
 23:         this(nodeKey, parentNode, isRed, null, null);
 24:     }

 26:     public RBTNode(int nodeKey, RBTNode parentNode, boolean isRed,
 27:                    RBTNode leftChild, RBTNode rightChild)
 28:     {
 29:         key = nodeKey;
 30:         parent = parentNode;
 31:         left = leftChild;
 32:         right = rightChild;
 33:         color = isRed ? Color.RED : Color.BLACK;
 34:     }

 36:     // Returns true if both child nodes are black. A child set to None is
 37:     // considered to be black.
 38:     public boolean areBothChildrenBlack()
 39:     {
 40:         if (left != null && left.isRed())
 41:         {
 42:             return false;
 43:         }
 44:         if (right != null && right.isRed())
 45:         {
 46:             return false;
 47:         }
 48:         return true;
 49:     }

 51:     public int count()
 52:     {
 53:         int count = 1;
 54:         if (left != null)
 55:         {
 56:             count += left.count();
 57:         }
 58:         if (right != null)
 59:         {
 60:             count += right.count();
 61:         }
 62:         return count;
 63:     }

 65:     public RBTNode getGrandparent()
 66:     {
 67:         if (parent == null)
 68:         {
 69:             return null;
 70:         }
 71:         return parent.parent;
 72:     }

 74:     // Gets this node's predecessor from the left child subtree
 75:     // Precondition: This node's left child is not null
 76:     public RBTNode getPredecessor()
 77:     {
 78:         RBTNode node = left;
 79:         while (node.right != null)
 80:         {
 81:             node = node.right;
 82:         }
 83:         return node;
 84:     }

 86:     // Returns this node's sibling, or null if this node
 87:     // does not have a sibling
 88:     public RBTNode getSibling()
 89:     {
 90:         if (parent != null)
 91:         {
 92:             if (this == parent.left)
 93:             {
 94:                 return parent.right;
 95:             }
 96:             return parent.left;
 97:         }
 98:         return null;
 99:     }

101:     // Returns the uncle of this node
102:     public RBTNode getUncle()
103:     {
104:         RBTNode grandparent = getGrandparent();
105:         if (grandparent == null)
106:         {
107:             return null;
108:         }
109:         if (grandparent.left == parent)
110:         {
111:             return grandparent.right;
112:         }
113:         return grandparent.left;
114:     }

116:     // Returns true if this node is black, false otherwise
117:     public boolean isBlack()
118:     {
119:         return color == Color.BLACK;
120:     }

122:     // Returns true if this node is red, false otherwise
123:     public boolean isRed()
124:     {
125:         return color == Color.RED;
126:     }

128:     // Replaces one of this node's children with a new child
129:     public boolean replaceChild(RBTNode currentChild, RBTNode newChild)
130:     {
131:         if (left == currentChild)
132:         {
133:             return setChild(Child.LEFT, newChild);
134:         }
135:         else if (right == currentChild)
136:         {
137:             return setChild(Child.RIGHT, newChild);
138:         }
139:         return false;
140:     }

142:     // Sets either the left or right child of this node
143:     public boolean setChild(Child whichChild, RBTNode child)
144:     {
145:         if (whichChild == Child.LEFT)
146:         {
147:             left = child;
148:         }
149:         else
150:         {
151:             right = child;
152:         }

154:         if (child != null)
155:         {
156:             child.parent = this;
157:         }

159:         return true;
160:     }
161: }