//----------------------------------------------------------------------------- Binary Search Tree Algorithms: Chapter 12 of CLRS //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- InOrderTreeWalk(x) if x != NIL InOrderTreeWalk(x.left) print(x.key) InOrderTreeWalk(x.right) //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- PreOrderTreeWalk(x) if x != NIL print(x.key) PreOrderTreeWalk(x.left) PreOrderTreeWalk(x.right) //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- PostOrderTreeWalk(x) if x != NIL PostOrderTreeWalk(x.left) PostOrderTreeWalk(x.right) print(x.key) //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- TreeSearch(x, k) if x == NIL or k == x.key return x else if k < x.key return TreeSearch(x.left, k) else // k > x.key return TreeSearch(x.right, k) //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- TreeMinimum(x) Pre: x != NIL while x.left != NIL x = x.left return x //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- TreeMaximum(x) Pre: x != NIL while x.right != NIL x = x.right return x //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- TreeSuccessor(x) if x.right != NIL // case 1 return TreeMinimum(x.right) y = x.parent // case 2 while y != NIL and x == y.right x = y y = y.parent return y //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- Exercise: Write TreePredecessor(x) //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- TreeInsert(T, z) y = NIL x = T.root while x != NIL y = x if z.key < x.key x = x.left else x = x.right z.parent = y if y == NIL T.root = z // tree T was empty else if z.key < y.key y.left = z else y.right = z //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- Transplant(T, u, v) if u.parent == NIL T.root = v else if u == u.parent.left u.parent.left = v else u.parent.right = v if v != NIL v.parent = u.parent //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- Delete(T, z) if z.left == NIL // case 1 or case 2.1 (right only) Transplant(T, z, z.right) else if z.right == NIL // case 2.2 (left only) Transplant(T, z, z.left) else // case 3 y = TreeMinimum(z.right) if y.parent != z Transplant(T, y, y.right) y.right = z.right y.right.parent = y Transplant(T, z, y) y.left = z.left y.left.parent = y //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- Red-Black Tree Algorithms: Chapter 13 of CLRS //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- LeftRotate(T, x) // set y y = x.right // turn y's left subtree into x's right subtree x.right = y.left if y.left != T.nil // not necessary if using sentinal nil node y.left.parent = x // link y's parent to x y.parent = x.parent if x.parent == T.nil T.root = y else if x == x.parent.left x.parent.left = y else x.parent.right = y // put x on y's left y.left = x x.parent = y //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- RotateRight(T, x) // set y y = x.left // turn y's right subtree into x's left subtree x.left = y.right if y.right != T.nil // not necessary if using sentinal nil node y.right.parent = x // link y's parent to x y.parent = x.parent if x.parent == T.nil T.root = y else if x == x.parent.right x.parent.right = y else x.parent.left = y // put x on y's right y.right = x x.parent = y //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- RB_Insert(T, z) y = T.nil x = T.root while x != T.nil y = x if z.key < x.key x = x.left else x = x.right z.parent = y if y == T.nil T.root = z else if z.key < y.key y.left = z else y.right = z z.left = T.nil z.right = T.nil z.color = RED RB_InsertFixUp(T, z) //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- RB_InsertFixUp(T, z) while z.parent.color == RED if z.parent == z.parent.parent.left y = z.parent.parent.right if y.color == RED z.parent.color = BLACK // case 1 y.color = BLACK // case 1 z.parent.parent.color = RED // case 1 z = z.parent.parent // case 1 else if z == z.parent.right z = z.parent // case 2 LeftRotate(T, z) // case 2 z.parent.color = BLACK // case 3 z.parent.parent.color = RED // case 3 RightRotate(T, z.parent.parent) // case 3 else y = z.parent.parent.left if y.color == RED z.parent.color = BLACK // case 4 y.color = BLACK // case 4 z.parent.parent.color = RED // case 4 z = z.parent.parent // case 4 else if z == z.parent.left z = z.parent // case 5 RightRotate(T, z) // case 5 z.parent.color = BLACK // case 6 z.parent.parent.color = RED // case 6 LeftRotate(T, z.parent.parent) // case 6 T.root.color = BLACK //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- RB_Transplant(T, u, v) if u.parent == T.nil T.root = v else if u == u.parent.left u.parent.left = v else u.parent.right = v v.parent = u.parent //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- RB_Delete(T, z) y = z y_original_color = y.color if z.left == T.nil x = z.right RB_Transplant(T, z, z.right) else if z.right == T.nil x = z.left RB_Transplant(T, z, z.left) else y = TreeMinimum(z.right) y_original_color = y.color x = y.right if y.parent == z x.parent = y else RB_Transplant(T, y, y.right) y.right = z.right y.right.parent = y RB_Transplant(T, z, y) y.left = z.left y.left.parent = y y.color = z.color if y_original_color == BLACK RB_DeleteFixUp(T, x) //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- RB_DeleteFixUp(T, x) while x != T.root and x.color == BLACK if x == x.parent.left w = x.parent.right if w.color == RED w.color = BLACK // case 1 x.parent.color = RED // case 1 LeftRotate(T, x.parent) // case 1 w = x.parent.right // case 1 if w.left.color == BLACK and w.right.color == BLACK w.color = RED // case 2 x = x.parent // case 2 else if w.right.color == BLACK w.left.color = BLACK // case 3 w.color = RED // case 3 RightRotate(T, w) // case 3 w = x.parent.right // case 3 w.color = x.parent.color // case 4 x.parent.color = BLACK // case 4 w.right.color = BLACK // case 4 LeftRotate(T, x.parent) // case 4 x = T.root // case 4 else w = x.parent.left if w.color == RED w.color = BLACK // case 5 x.parent.color = RED // case 5 RightRotate(T, x.parent) // case 5 w = x.parent.left // case 5 if w.right.color == BLACK and w.left.color == BLACK w.color = RED // case 6 x = x.parent // case 6 else if w.left.color == BLACK w.right.color = BLACK // case 7 w.color = RED // case 7 LeftRotate(T, w) // case 7 w = x.parent.left // case 7 w.color = x.parent.color // case 8 x.parent.color = BLACK // case 8 w.left.color = BLACK // case 8 RightRotate(T, x.parent) // case 8 x = T.root // case 8 x.color = BLACK //----------------------------------------------------------------------------- //-----------------------------------------------------------------------------