Предположим, что вы хотите удалить узел, содержащий наибольшее значение, меньшее некоторого целевого значения t , где t само по себе не обязательно является значением какого-либо узла в дереве, подумайте, какие результаты вы можете получить, выполнив поиск в BST для значения t . Есть три варианта:
- Вы найдете т . Это сводится к вашему предыдущему вопросу - вы просто должны выполнить то же отслеживание, что и в этом случае.
- Вы попадаете на узел N , значение которого больше t , и у которого нет левого потомка. В этом случае дерево не содержит t или любое значение между t и значением N . Поэтому вы хотите удалить предшественник N , если он есть, поэтому он снова сводится к ситуации предыдущего вопроса.
- Вы попадаете на узел M , значение которого меньше t , и у которого нет правого потомка. В этом случае дерево не содержит t или любое значение между M и t , поэтому M - это узел, который вы хотите удалить.