Имам леко объркване по поводнаследник / предшественик, ако BST е обърнат. Това, което имах предвид, когато BST е обърнато / обърнато е, че когато всички елементи в дясното поддърво са по-малки и всички елементи в лявото поддърво е по-голямо. Обикновено дясното поддърво има по-голяма стойност. Какво ще стане, ако това е обърната, дали дефиницията за наследник / предшественик все още остава същата?
За нормалното дърво наследникът на реда би бил най-лявото дете на дясното поддърво, нали?
За обърнато BST като примера по-долу:
8
/
15 4
/ /
20 10 6 2
Наследникът на 8 е 10? Или е 6, ако следваме "обичайната" дефиниция за наследник?
Благодаря!
Отговори:
0 за отговор № 1Ако направите обръщане в обратна посока на обърната BST, ще получите номера, подредени в низходящ поръчка. Така в този случай редът на вашите стойности ще бъде: 20, 15, 10, 8, 6, 4, 2. Така че наследникът на 8 ще бъде 6.