import java.lang.Exception

var rootNode: Treee? = null

fun main(args: Array<String>) {

    val count = readLine()!!.toLong()
    for (i in 1..count) {
        val order = readLine()!!
        when {
            order.contains("insert") -> {
                insert(order.split(" ")[1].toInt())
            }
            order.contains("find") -> {
                printFind(order.split(" ")[1].toInt())
            }
            order.contains("delete") -> {
                delete(order.split(" ")[1].toInt())
            }
            order.contains("print") -> {
                printByInorder(rootNode!!)
                println()
                printByPreorder(rootNode!!)
                println()
            }
        }
    }
}


fun find(searchKey: Int): Treee? {
    if (rootNode == null) return null

    var x = rootNode!!

    while (true) {
        if (searchKey == x.key) {
            return x
        }

        if (x.key < searchKey) {
            if (x.right == null) {
                return null
            }
            x = x.right!!
        }

        if (x.key > searchKey) {
            if (x.left == null) {
                return null
            }
            x = x.left!!
        }
    }
}


fun printFind(index: Int) {
    val node = find(index)
    println(if (node != null) "yes" else "no")
}


fun delete(searchKey: Int) {

    val node = find(searchKey) ?: return

    var count = 0
    if (node.left == null) {
        count++
    }
    if (node.right == null) {
        count++
    }

    when (count) {
        // とりあえず消して終わり。ひも付きなくなる
        2 -> {
            if (node.parent!!.left?.key == node.key) {
                node.parent!!.left = null
            }

            if (node.parent!!.right?.key == node.key) {
                node.parent!!.right = null
            }
        }
        1 -> {
            // 子で代用する
            // 子を取得
            var childNode: Treee? = null
            if (node.left != null) {
                childNode = node.left
            }

            if (node.right != null) {
                childNode = node.right
            }

            // 親にくっつける
            if (node.parent!!.right?.key == node.key) {
                node.parent!!.right = childNode
                childNode!!.parent = node.parent
            }

            if (node.parent!!.left?.key == node.key) {
                node.parent!!.left = childNode
                childNode!!.parent = node.parent
            }
        }
        0 -> {

//            val maxNodeInLeft = getMaxNode(node.left!!)
//
//            // 左側の最大値からコピー
//            node.key = maxNodeInLeft.key
//
//            // すげ替え1
//            if (node.left != maxNodeInLeft) {
//                maxNodeInLeft.parent!!.right = maxNodeInLeft.left
//            } else {
//                maxNodeInLeft.parent!!.left = maxNodeInLeft.left
//            }
//
//            // すげ替え2
//            if (maxNodeInLeft.left != null) {
//                maxNodeInLeft.left!!.parent = maxNodeInLeft.parent
//            }

            val minNodeInRight = getMinNode(node.right!!)
            // 右の最小値からコピー
            node.key = minNodeInRight.key

            // すげ替え1
            if (node.right?.key != minNodeInRight.key) {
                minNodeInRight.parent!!.left = minNodeInRight.right
            } else {
                minNodeInRight.parent!!.right = minNodeInRight.right
            }

            // すげ替え2
            if (minNodeInRight.right != null) {
                minNodeInRight.right!!.parent = minNodeInRight.parent
            }
        }
    }
}

fun getMaxNode(node: Treee): Treee {
    var maxNode = node
    while (maxNode.right != null) {
        maxNode = maxNode.right!!
    }

    return maxNode
}

fun getMinNode(node: Treee): Treee {
    var minNode = node
    while (minNode.left != null) {
        minNode = minNode.left!!
    }

    return minNode
}


fun insert(addedKey: Int) {
    val addedNode = Treee(key = addedKey)

    if (rootNode == null) {
        rootNode = addedNode
        return
    }

    // ルートノーのから開始
    var x = rootNode!!
    while (true) {
        if (x.key < addedKey) {

            // 右に配置
            if (x.right == null) {
                x.right = addedNode
                addedNode.parent = x
                break

            } else {
                x = x.right!!
            }
        } else if (x.key > addedKey) {

            // 左に配置
            if (x.left == null) {
                x.left = addedNode
                addedNode.parent = x
                break

            } else {
                x = x.left!!
            }

        } else {
            throw Exception("key is duplicated!!!")
        }
    }
}

fun printByPreorder(node: Treee) {

    print(" ${node.key}")

    if (node.left != null) {
        printByPreorder(node.left!!)
    }

    if (node.right != null) {
        printByPreorder(node.right!!)
    }
}


fun printByInorder(node: Treee) {

    if (node.left != null) {
        printByInorder(node.left!!)
    }

    print(" ${node.key}")

    if (node.right != null) {
        printByInorder(node.right!!)
    }
}

data class Treee(
    var parent: Treee? = null,
    var left: Treee? = null,
    var right: Treee? = null,
    var key: Int
)
