Самостоятельная работа-3 Студент: 2 курс Группа: ди-13-20

САМОСТОЯТЕЛЬНАЯ РАБОТА-3


Студент: 2 - курс
Группа: ДИ-13-20
Подготовил: Д . Дустмуродов Принял: Р.АБДУЛЛАЕВ

Темы:

• 
  Древоведная структура данных и операции с ними
  
• 
  Сбалансированные бинарные деревъя
  
• 
  Работа с бинарнами деревъям
  

Основные термины

• 
  Дерево — это, по сути, один из частных случаев графа. Древовидная модель может быть весьма эффективна в случае представления динамических данных, особенно тогда, когда у разработчика стоит цель быстрого поиска информации, в тех же базах данных, к примеру.
  

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

• 
  Каждый элемент — это вершина или узел дерева. Узлы соединенные направленными дугами, называются ветвями. Начальный узел — это корень дерева (корневой узел). Листья — это узлы, в которые входит 1 ветвь, причем не выходит ни одной.
  
• 
  Общую терминологию можно посмотреть на левой и правой части картинки ниже:
  

• 
  Какие свойства есть у каждого древа:
  
• 
  — существует узел, в который не входит ни одна ветвь;
  
• 
  — в каждый узел, кроме корневого узла, входит 1 ветвь.
  

Понятия

• 
  Бинарное дерево поиска — дерево в котором узлы располагаются таким образом, что каждый узел с меньшим значением (относительно родителя) находится в левой части дерева, соответственно с большим — в правой.
  
• 
  Дерево поиска с минимальной высотой как раз и называется сбалансированным, т.е. таким, в котором высота левого и правого поддеревьев отличаются не более чем на единицу.
  
• 
  Сбалансированное оно, видимо, потому что в таком дереве в среднем требуется наименьшее количество операций для поиска.
  
• 
  Чтобы дерево имело минимальную высоту, количество узлов левого и правого поддеревьев должны максимально приближаться друг к другу. Построим дерево по этому принципу: середина каждого подраздела массива становится корневым узлом, а левая и правая части — соответствующими для него поддеревьями. Т.к. массив отсортирован, то полученное дерево соответствует определению бинарного дерева поиска.
  

Каким образом реализовать алгоритм?

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

1. 
   /**
   
2. 
   * Рекурсивно проходится по бинарному дереву от корня,
   
3. 
   * пока не найдет подходящее место для нового узла.
   
4. 
   * Каждая вставка требует обход дерева, т.е. O(log N),
   
5. 
   * поэтому время работы для создания бинарного дерева O(n * log N)
   
6. 
   */
   
7. 
   function insertNodeIntoBST(root, node) {
   
8. 
   if (root.data < node.data) {
   
9. 
   if (root.right === null) {
   
10. 
    root.right = node;
    
11. 
    } else {
    
12. 
    insertNodeIntoBST(root.right, node);
    
13. 
    }
    
14. 
    } else {
    
15. 
    if (root.left === null) {
    
16. 
    root.left = node;
    
17. 
    } else {
    
18. 
    insertNodeIntoBST(root.left, node);
    
19. 
    }
    
20. 
    }
    
21. 
    }
    

• 
  Этот способ не слишком эффективен — обход дерева требует O(log N) операций, чтобы вставить каждый узел потребуется O(n * log N) времени.