Блог

Главная - Вопросы по программированию - Операция удаления дерева 2-3-4

Операция удаления дерева 2-3-4

#data-structures #tree #b-tree

#структуры данных #дерево #b-дерево

Вопрос:

Как я могу удалить узел 1 из дерева 2-3-4, если структура дерева такая, как показано ниже:

             4      10
        /       |       
      2        6,8      12,14 
    /       /  |     /   |   
   1   3    5   7  9  11  13   15

Ответ №1:

Мне нравится думать об этом так: вы удаляете только листья или внутренние узлы, у которых есть один дочерний элемент, а дочерние элементы всего, что вы удаляете, должны оставаться на том же уровне.

Для их удержания требуется переместить ключ вниз с уровня выше, который объединяется с родственным ключом.

Если родительский элемент имеет только один ключ, это вызовет каскадное удаление.

 Deleting 1 by pulling down 2 causes a cascaded delete:
     
      4 ,  10
  /     |      
 X     6,8      12,14
 |    / |      / |  
2,3  5  7  9  11  13  15

The cascaded delete pulls down the 4:
     
           10
         /    
    4,6,8      12,14
   / | |      / |  
2,3  5 7  9  11  13  15

Если дочерний элемент слишком велик для объединения, возможно, вам придется перераспределить его из дочернего элемента. Это потребовалось бы, если бы это было дерево 2-3, например:

 Redistributing a key from 6,8
     
        6  ,  10
     /     |      
    4      8      12,14
   /     /      / |  
2,3   5  7   9  11  13  15