Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Алгоритми та структури даних, технології → Маніпуляції з деревом елементів
Для відправлення відповіді ви повинні увійти або зареєструватися
Користувачі не бачать дерево. Користувачі бачать пікселі на екрані.
А які іще операції з деревом, окрім показати на екрані, бувають?
Користувачі не бачать дерево. Користувачі бачать пікселі на екрані.
А які іще операції з деревом, окрім показати на екрані, бувають?
розкрити/згорнути секцію
розкрити/згорнути всі існуючі секції
додати/видалити елемент з дерева
перетягнути секцію/елемент в інше місце/секцію дерева, при цьому необхідно показти індикатор, куди саме перетягується елемент, або секція з елементами
Тобто є масив, він усюди працює і редагується як масив, а в одному місці має бути представлений як дерево. Але при цьому треба дерево часто (?) синхронізувати з масивом, у той чи інший бік, правильно?
Тоді лишається тільки локалізувати та оптимізувати функції перетворення. Створення дерева - перетворення. Відправка даних з дерева - перетворення. Все решта - працює як дерево. І зі слайсами щось зробіть.
Тобто є масив, він усюди працює і редагується як масив, а в одному місці має бути представлений як дерево. Але при цьому треба дерево часто (?) синхронізувати з масивом, у той чи інший бік, правильно?
Тоді лишається тільки локалізувати та оптимізувати функції перетворення. Створення дерева - перетворення. Відправка даних з дерева - перетворення. Все решта - працює як дерево. І зі слайсами щось зробіть.
та я вже ті слайси прибрав.
Тоді - підписант 1 отримує масив зі сховища, трансформує його в дерево, і далі використовує його, як дерево. Решта підписантів отримують масив зі сховища, і використовують його, як масив. Якщо дерево змінюється, то ми перетворюємо його в масив, і зберігаємо в сховища, аби решта підписантів синхронізувались. А коли інші підписанти змінюють масив, то вони теж зберігають його до сховища, і тоді підписант 1 отримує нову версію масиву, і перетворює її в дерево, аби воно оновилось?
Тоді підписант 1 повинен чекати лише на першу версію масиву, і ігнорувати решту? Тому що при зміні дерева - ми оновлюємо масив в сховищі, і підписант 1 автоматично отримуватиме нову версію масиву, і це буде запускати процес побудови дерева.
здається, я тілько зараз зрозумів, наскілько то зручно - працювати з деревом.
От раніше, для пошуку найнижчої секції, я перевертав масив з ніг на голову, а потім робив перебір елементів, допоки не знайду першу секцію.
Я думав, а як то зробити з деревом отим, адже останнім елементом може бути як і простий елемент, і тоді доведеться все одно перебирати, а може й бути секція, котра має дітей, серед котрих є секція, котра теж має дітей, і серед тих дітей десь може бути секція. Тобто це треба було б перебирати дітей, і хто-зна, скільки їх там буде, допоки ми доберемось до найнижчої секції, в найгіршому випадку, мабуть, це буде O(n).
Але тут мені в голову прийшла проста і файна думка! Я ж можу при першій побудові дерева запам'ятати останній елемент, і також я можу кожному елементи прикріпити посилання на його батьківський елемент.
І тоді, для пошуку найнижчої секції, мені просто треба глянути на останній елемент - якщо це секція, то вона і є останньою, а якщо простий елемент - то треба просто глянути на батька цього останнього елементу, і все, ми знайшли. Тобто, це ж виходе O(1), правильно?
єдине, що я не врахував, то це те, що при маніпуляціях з деревом останній елемент може змінитись, і з цим треба щось робити ото
Виникла ще одна проблєма.
Зараз працює так - якщо ми перетягуємо елемент знизу на елемент, що знаходиться вище в списку, то ми перетягуємо попереду другого елементу, а не перед ним. Але якщо ми перетягуємо елемент, що знаходиться вище того елементу, на котрий ми пертягуємо, то тоді елемент поміщається за тим елементом, на котрий пертягуємо.
Аби це працювало, до кожного елементи дерева я додав індекс, і порівнюючи ці індекси можна зрозуміти, який елемент зверху, а який знизу.
Проблема в тому, що ці індекси проставляються при побудові дерева. І якщо я просто перетягую елементи з місця на місце і не встановлюю нові індекси, то потім пертягування може працювати некоректно.
Тепер розглянемо ситуацію, нехай у нас є 4 елементи
[0, 1, 2, 3]ми хочемо перетягнути четвертий елемент на початок, і після перетягування матимемо таке (значення елементів відповідають їх індексам)
[3, 0, 1, 2]тепер кожен елемент має неправильний індекс, і ці індекси потрібно прерахувати.
Враховуючи, що оті елементи можуть бути секціями з дітьми, то це мені треба пройтись по кожному елементу, враховуючи дітей, і дітей дітей, і заново проставити індекси.
Це єдиний варіянт вирішення проблеми? Чи можна зробити якось розумніше?
А нащо дітям міняти індекси? Припустимо, в елементу №2 є троє дітей, тоді запишемо (індекс, діти) для кожного елементу, було:
[(0,[]), (1,[]), (2,[0,1,2]), (3,[])]
Стало
[(3,[]), (0,[]), (1,[]), (2,[0,1,2])]
А нащо дітям міняти індекси? Припустимо, в елементу №2 є троє дітей, тоді запишемо (індекс, діти) для кожного елементу, було:
[(0,[]), (1,[]), (2,[0,1,2]), (3,[])]
Стало
[(3,[]), (0,[]), (1,[]), (2,[0,1,2])]
Тому що коли ми перетягуємо елементи, то нам все одно, чи це батько, чи дитина, адже перетягувати можна всі елементи, і коли ми тягнемо один елемент на другий - то нам необхідні індекси, аби зрозуміти - чи елемент, на котрий ми перетягуємо, знаходиться нижче, чи вижче в дереві, відносно того елементу, котрий ми тягаємо. Ну і ще треба знати, в яку саме позицію переміщувати той елемент, який тягаємо, адже дерево-деревом, але по суті у нас є масив з елементів, котрі можуть мати дітей, і коли ми розгортаємо якусь секцію, то діти цієї секції додаються в масив, котрі ми потім повертаємо і котрого потім інший елемент показує на сторінці
В мене ще одне питання з'явилось.
Скажімо, ми рухаємо останній елемент в дереві кудись наперед, або всередину дерева. Раніше я створив змінну, котра тримає посилання на останній елемент в дереві, і її потрібно оновлювати, аби вона постійно вказувала на останній елемент. Тобто, якщо я рухаю останній елемент кудись в інакше місце, то передостанній елемент стає останнім, і його потрібно загнати в змінну, що посилається на останній елемент.
Але як отримати посилання на передостанній елемент? Адже передостаннім елементом може бути згорнута секція, що має дітей, тоді справжнім передостаннім елементом буде остання дитина тої секції (але ця остання дитина теж може бути секцією з дітьми). Я можу створити пошук по секціям і їх дітям, а можу зробити зв'язний список, аби кожен елемент мав посилання на наступний, та попердній елемент в дереві.
Як гадаєте, як буде краще зробити?
ну, я зробив першим методом, а не через список.
Тому що вкладенність обмежена до 4, тобто, в найгіршому варіанті, мені просто треба буде 4 рази глянути на елемент.
Тобто, беремо передостанній в списку, якщо в нього є діти, то дивимось на останню дитину, і перевіряємо, чи в неї дітей немає, і т.д. І коли у елемента немає дітей - то він є передостаннім. На мою думку, це є O(n), де n <= 4, тобто, виходе O(1).
А якби я ліпив список, то після кожної зміни позиції елементів доводилося б фіксити всі ті посилання.
Для відправлення відповіді ви повинні увійти або зареєструватися