Пока я занимался проблемами структур данных, я наткнулся на проблему, как найти высоту дерева и проверить, является ли дерево сбалансированным. Зачем нужна эта балансировка? Что мы понимаем под балансом?

Во-первых, многие структуры данных имеют инвариант баланса. В зависимости от структуры данных достижение баланса будет достигаться разными средствами. Рассмотрим перекошенное двоичное дерево поиска, в котором все узлы (кроме листьев) имеют только правый дочерний элемент, а левый дочерний элемент всегда равен нулю. Сложность выполнения find() в этом дереве будет O(n).

Для достижения лучшей производительности вам необходимо сбалансировать дерево. Согласно определению, идеально сбалансированное дерево — это когда левое и правое поддеревья любого узла имеют одинаковую высоту. Мы говорим о почти идеально сбалансированном дереве, если высота поддеревьев отличается не более чем на 1. Балансировка BST гарантирует время поиска O(log n).

Проблема: проверка того, является ли BST сбалансированным деревом.

// Having Node definition
function Node(val, left, right) {
  return {val, left, right}
}
// Build a sample tree
let BSTtree = Node(1, Node(2, Node(3, null, null), Node(4, null, null)), Node(5, null, Node(6, null, null)))
  1. Чтобы проверить, соответствует ли данное дерево свойству баланса, сначала вам понадобится логика для получения высоты дерева.
const height = function (root) {
  if (root === null) {
   return 0
  }
  let leftHeight = height(root.left)
  let rightHeight = height(root.right)
  return Math.max(leftHeight, rightHeight) + 1
}
//A tree node’s height is defined as the number of edges on the longest path to a leaf. A leaf node’s height is 0.

2. Когда у вас есть высота, проверьте, сбалансированы ли ветви дерева.

//A tree is balanced if for every node, height difference for left and right child is at most 1
// an empty tree is balanced
const isBalanced = function (root) {
// step 1 - empty tree is balanced!
  if (root === null) {
    return true
  }
// step 2 - verify is children are balanced and if not return it immediately
let areChildrenBalanced = isBalanced(root.left) &&      isBalanced(root.right)
  if (!areChildrenBalanced) return false;
  // step 3 - we know children are balanced, time to verify if   current node is balanced
  let leftHeight = height(root.left)
  let rightHeight = height(root.right)
  let diff = Math.abs(leftHeight — rightHeight)
  return Math.abs(leftHeight — rightHeight) <= 1
}