JavaScript: структуры данных и алгоритмы. Часть 3

import Comparator from '../../utils/comparator' import HashTable from '../hash-table'  export default class BinaryTreeNode {   constructor(value = null) {     // Значение     this.value = value     // Левый потомок     this.left = null     // Правый потомок     this.right = null     // Предок     this.parent = null      // Дополнительная информация об узле     this.meta = new HashTable()      // Функция сравнения узлов     this.nodeComparator = new Comparator()   }    // Геттер высоты (глубины) левого поддерева   get leftHeight() {     if (!this.left) {       return 0     }      return this.left.height + 1   }    // Геттер высоты правого поддерева   get rightHeight() {     if (!this.right) {       return 0     }      return this.right.height + 1   }    // Геттер максимальной высоты   get height() {     return Math.max(this.leftHeight, this.rightHeight)   }    // Геттер разницы между высотой левого и правого поддеревьев   // (фактор балансировки)   get balanceFactor() {     return this.leftHeight - this.rightHeight   }    // Геттер дяди   get uncle() {     // Если нет предка, то нет и дяди     if (!this.parent) {       return null     }      // Если нет дедушки, то нет и дяди     if (!this.parent.parent) {       return null     }      // Если у дедушки нет двух потомков, то нет и дяди     if (!this.parent.parent.left || !this.parent.parent.right) {       return null     }      // Выясняем, кто является дядей     // путем сравнения предка с потомком дедушки     if (this.nodeComparator.equal(this.parent, this.parent.parent.left)) {       // Дядя - правый узел       return this.parent.parent.right     }      // Дядя - левый узел     return this.parent.parent.left   }    // Устанавливает значение   setValue(value) {     this.value = value      return this   }    // Устанавливает левого потомок   setLeft(node) {     // Сбрасываем предка левого узла     if (this.left) {       this.left.parent = null     }      // Обновляем левый узел     this.left = node      // Делаем текущий узел предком нового левого узла     if (this.left) {       this.left.parent = this     }      return this   }    // Устанавливает правого потомка   setRight(node) {     // Сбрасываем предка правого узла     if (this.right) {       this.right.parent = null     }      // Обновляем правый узел     this.right = node      // Делаем текущий узел предком нового правого узла     if (this.right) {       this.right.parent = this     }      return this   }    // Удаляет потомка   removeChild(nodeToRemove) {     // Если удаляется левый потомок     if (this.left && this.nodeComparator.equal(this.left, nodeToRemove)) {       this.left = null       return true     }      // Если удаляется правый потомок     if (this.right && this.nodeComparator.equal(this.right, nodeToRemove)) {       this.right = null       return true     }      return false   }    // Заменяет потомка   replaceChild(nodeToReplace, replacementNode) {     if (!nodeToReplace || !replacementNode) {       return false     }      // Если заменяется левый потомок     if (this.left && this.nodeComparator.equal(this.left, nodeToReplace)) {       this.left = replacementNode       return true     }      // Если заменяется правый потомок     if (this.right && this.nodeComparator.equal(this.right, nodeToReplace)) {       this.right = replacementNode       return true     }      return false   }    // Обходит дерево в порядке возрастания ключей (inorder, infix traverse):   // сначала обходится левое поддерево, затем корень, затем правое поддерево   traverseInOrder() {     let result = []      if (this.left) {       result = result.concat(this.left.traverseInOrder())     }      result.push(this.value)      if (this.right) {       result = result.concat(this.right.traverseInOrder())     }      return result   }    // Статический метод копирования узла   static copyNode(sourceNode, targetNode) {     targetNode.setValue(sourceNode.value)     targetNode.setLeft(sourceNode.left)     targetNode.setRight(sourceNode.right)   }    // Преобразует дерево в строку   toString() {     return this.traverseInOrder().toString()   } }

// data-structures/tree/__tests__/binary-tree-node.test.js import BinaryTreeNode from '../binary-tree-node'  describe('BinaryTreeNode', () => {   it('должен создать узел', () => {     const node = new BinaryTreeNode()      expect(node).toBeDefined()      expect(node.value).toBeNull()     expect(node.left).toBeNull()     expect(node.right).toBeNull()      const leftNode = new BinaryTreeNode(1)     const rightNode = new BinaryTreeNode(3)     const rootNode = new BinaryTreeNode(2)      rootNode.setLeft(leftNode).setRight(rightNode)      expect(rootNode.value).toBe(2)     expect(rootNode.left.value).toBe(1)     expect(rootNode.right.value).toBe(3)   })    it('должен установить предка', () => {     const leftNode = new BinaryTreeNode(1)     const rightNode = new BinaryTreeNode(3)     const rootNode = new BinaryTreeNode(2)      rootNode.setLeft(leftNode).setRight(rightNode)      expect(rootNode.parent).toBeNull()     expect(rootNode.left.parent.value).toBe(2)     expect(rootNode.right.parent.value).toBe(2)     expect(rootNode.right.parent).toEqual(rootNode)   })    it('должен обойти дерево', () => {     const leftNode = new BinaryTreeNode(1)     const rightNode = new BinaryTreeNode(3)     const rootNode = new BinaryTreeNode(2)      rootNode.setLeft(leftNode).setRight(rightNode)      expect(rootNode.traverseInOrder()).toEqual([1, 2, 3])      expect(rootNode.toString()).toBe('1,2,3')   })    it('должен удалить потомков', () => {     const leftNode = new BinaryTreeNode(1)     const rightNode = new BinaryTreeNode(3)     const rootNode = new BinaryTreeNode(2)      rootNode.setLeft(leftNode).setRight(rightNode)      expect(rootNode.traverseInOrder()).toEqual([1, 2, 3])      expect(rootNode.removeChild(rootNode.left)).toBe(true)     expect(rootNode.traverseInOrder()).toEqual([2, 3])      expect(rootNode.removeChild(rootNode.right)).toBe(true)     expect(rootNode.traverseInOrder()).toEqual([2])      expect(rootNode.removeChild(rootNode.right)).toBe(false)     expect(rootNode.traverseInOrder()).toEqual([2])   })    it('должен заменить потомков', () => {     const leftNode = new BinaryTreeNode(1)     const rightNode = new BinaryTreeNode(3)     const rootNode = new BinaryTreeNode(2)      rootNode.setLeft(leftNode).setRight(rightNode)      expect(rootNode.traverseInOrder()).toEqual([1, 2, 3])      const replacementNode = new BinaryTreeNode(5)     rightNode.setRight(replacementNode)      expect(rootNode.traverseInOrder()).toEqual([1, 2, 3, 5])      expect(rootNode.replaceChild(rootNode.right, rootNode.right.right)).toBe(       true,     )     expect(rootNode.right.value).toBe(5)     expect(rootNode.right.right).toBeNull()     expect(rootNode.traverseInOrder()).toEqual([1, 2, 5])      expect(rootNode.replaceChild(rootNode.right, rootNode.right.right)).toBe(       false,     )     expect(rootNode.traverseInOrder()).toEqual([1, 2, 5])      expect(rootNode.replaceChild(rootNode.right, replacementNode)).toBe(true)     expect(rootNode.traverseInOrder()).toEqual([1, 2, 5])      expect(rootNode.replaceChild(rootNode.left, replacementNode)).toBe(true)     expect(rootNode.traverseInOrder()).toEqual([5, 2, 5])      expect(       rootNode.replaceChild(new BinaryTreeNode(), new BinaryTreeNode()),     ).toBe(false)   })    it('должен вычислить высоту узлов', () => {     const root = new BinaryTreeNode(1)     const left = new BinaryTreeNode(3)     const right = new BinaryTreeNode(2)     const grandLeft = new BinaryTreeNode(5)     const grandRight = new BinaryTreeNode(6)     const grandGrandLeft = new BinaryTreeNode(7)      expect(root.height).toBe(0)     expect(root.balanceFactor).toBe(0)      root.setLeft(left).setRight(right)      expect(root.height).toBe(1)     expect(left.height).toBe(0)     expect(root.balanceFactor).toBe(0)      left.setLeft(grandLeft).setRight(grandRight)      expect(root.height).toBe(2)     expect(left.height).toBe(1)     expect(grandLeft.height).toBe(0)     expect(grandRight.height).toBe(0)     expect(root.balanceFactor).toBe(1)      grandLeft.setLeft(grandGrandLeft)      expect(root.height).toBe(3)     expect(left.height).toBe(2)     expect(grandLeft.height).toBe(1)     expect(grandRight.height).toBe(0)     expect(grandGrandLeft.height).toBe(0)     expect(root.balanceFactor).toBe(2)   })    it('должен также вычислить высоту правых узлов', () => {     const root = new BinaryTreeNode(1)     const right = new BinaryTreeNode(2)      root.setRight(right)      expect(root.height).toBe(1)     expect(right.height).toBe(0)     expect(root.balanceFactor).toBe(-1)   })    it('должен обнулить левый и правый узлы', () => {     const root = new BinaryTreeNode(2)     const left = new BinaryTreeNode(1)     const right = new BinaryTreeNode(3)      root.setLeft(left)     root.setRight(right)      expect(root.left.value).toBe(1)     expect(root.right.value).toBe(3)      root.setLeft(null)     root.setRight(null)      expect(root.left).toBeNull()     expect(root.right).toBeNull()   })    it('должен добавить объекты', () => {     const obj1 = { key: 'object_1', toString: () => 'object_1' }     const obj2 = { key: 'object_2' }      const node1 = new BinaryTreeNode(obj1)     const node2 = new BinaryTreeNode(obj2)      node1.setLeft(node2)      expect(node1.value).toEqual(obj1)     expect(node2.value).toEqual(obj2)     expect(node1.left.value).toEqual(obj2)      node1.removeChild(node2)      expect(node1.value).toEqual(obj1)     expect(node2.value).toEqual(obj2)     expect(node1.left).toBeNull()      expect(node1.toString()).toBe('object_1')     expect(node2.toString()).toBe('[object Object]')   })    it('должен добавить дополнительную информацию в узлы', () => {     const redNode = new BinaryTreeNode(1)     const blackNode = new BinaryTreeNode(2)      redNode.meta.set('color', 'red')     blackNode.meta.set('color', 'black')      expect(redNode.meta.get('color')).toBe('red')     expect(blackNode.meta.get('color')).toBe('black')   })    it('должен найти правильного дядю', () => {     const grandParent = new BinaryTreeNode('grand-parent')     const parent = new BinaryTreeNode('parent')     const uncle = new BinaryTreeNode('uncle')     const child = new BinaryTreeNode('child')      expect(grandParent.uncle).toBeNull()     expect(parent.uncle).toBeNull()      grandParent.setLeft(parent)      expect(parent.uncle).toBeNull()     expect(child.uncle).toBeNull()      parent.setLeft(child)      expect(child.uncle).toBeNull()      grandParent.setRight(uncle)      expect(parent.uncle).toBeNull()     expect(child.uncle).toBeDefined()     expect(child.uncle).toEqual(uncle)   })    it('должен найти левого дядю', () => {     const grandParent = new BinaryTreeNode('grand-parent')     const parent = new BinaryTreeNode('parent')     const uncle = new BinaryTreeNode('uncle')     const child = new BinaryTreeNode('child')      expect(grandParent.uncle).toBeNull()     expect(parent.uncle).toBeNull()      grandParent.setRight(parent)      expect(parent.uncle).toBeNull()     expect(child.uncle).toBeNull()      parent.setRight(child)      expect(child.uncle).toBeNull()      grandParent.setLeft(uncle)      expect(parent.uncle).toBeNull()     expect(child.uncle).toBeDefined()     expect(child.uncle).toEqual(uncle)   })    it('должен установить значения узла', () => {     const node = new BinaryTreeNode('initial_value')      expect(node.value).toBe('initial_value')      node.setValue('new_value')      expect(node.value).toBe('new_value')   })    it('должен копировать узел', () => {     const root = new BinaryTreeNode('root')     const left = new BinaryTreeNode('left')     const right = new BinaryTreeNode('right')      root.setLeft(left).setRight(right)      expect(root.toString()).toBe('left,root,right')      const newRoot = new BinaryTreeNode('new_root')     const newLeft = new BinaryTreeNode('new_left')     const newRight = new BinaryTreeNode('new_right')      newRoot.setLeft(newLeft).setRight(newRight)      expect(newRoot.toString()).toBe('new_left,new_root,new_right')      BinaryTreeNode.copyNode(root, newRoot)      expect(root.toString()).toBe('left,root,right')     expect(newRoot.toString()).toBe('left,root,right')   }) })

// data-structures/tree/__tests__/binary-search-tree-node.test.js import { BinarySearchTreeNode } from '../binary-search-tree'  describe('BinarySearchTreeNode', () => {   it('должен создать узел', () => {     const bstNode = new BinarySearchTreeNode(2)      expect(bstNode.value).toBe(2)     expect(bstNode.left).toBeNull()     expect(bstNode.right).toBeNull()   })    it('должен установить значение узла', () => {     const bstNode = new BinarySearchTreeNode()     bstNode.insert(1)      expect(bstNode.value).toBe(1)     expect(bstNode.left).toBeNull()     expect(bstNode.right).toBeNull()   })    it('должен добавить узлы в правильном порядке', () => {     const bstNode = new BinarySearchTreeNode(2)     const insertedNode1 = bstNode.insert(1)      expect(insertedNode1.value).toBe(1)     expect(bstNode.toString()).toBe('1,2')     expect(bstNode.contains(1)).toBe(true)     expect(bstNode.contains(3)).toBe(false)      const insertedNode2 = bstNode.insert(3)      expect(insertedNode2.value).toBe(3)     expect(bstNode.toString()).toBe('1,2,3')     expect(bstNode.contains(3)).toBe(true)     expect(bstNode.contains(4)).toBe(false)      bstNode.insert(7)      expect(bstNode.toString()).toBe('1,2,3,7')     expect(bstNode.contains(7)).toBe(true)     expect(bstNode.contains(8)).toBe(false)      bstNode.insert(4)      expect(bstNode.toString()).toBe('1,2,3,4,7')     expect(bstNode.contains(4)).toBe(true)     expect(bstNode.contains(8)).toBe(false)      bstNode.insert(6)      expect(bstNode.toString()).toBe('1,2,3,4,6,7')     expect(bstNode.contains(6)).toBe(true)     expect(bstNode.contains(8)).toBe(false)   })    it('не должен добавлять дубликаты', () => {     const bstNode = new BinarySearchTreeNode(2)     bstNode.insert(1)      expect(bstNode.toString()).toBe('1,2')     expect(bstNode.contains(1)).toBe(true)     expect(bstNode.contains(3)).toBe(false)      bstNode.insert(1)      expect(bstNode.toString()).toBe('1,2')     expect(bstNode.contains(1)).toBe(true)     expect(bstNode.contains(3)).toBe(false)   })    it('должен найти минимальный узел', () => {     const node = new BinarySearchTreeNode(10)      node.insert(20)     node.insert(30)     node.insert(5)     node.insert(40)     node.insert(1)      expect(node.findMin()).not.toBeNull()     expect(node.findMin().value).toBe(1)   })    it('должен добавить дополнительную информацию к узлам', () => {     const node = new BinarySearchTreeNode(10)      node.insert(20)     const node1 = node.insert(30)     node.insert(5)     node.insert(40)     const node2 = node.insert(1)      node.meta.set('color', 'red')     node1.meta.set('color', 'black')     node2.meta.set('color', 'white')      expect(node.meta.get('color')).toBe('red')      expect(node.findMin()).not.toBeNull()     expect(node.findMin().value).toBe(1)     expect(node.findMin().meta.get('color')).toBe('white')     expect(node.find(30).meta.get('color')).toBe('black')   })    it('должен найти узлы', () => {     const node = new BinarySearchTreeNode(10)      node.insert(20)     node.insert(30)     node.insert(5)     node.insert(40)     node.insert(1)      expect(node.find(6)).toBeNull()     expect(node.find(5)).not.toBeNull()     expect(node.find(5).value).toBe(5)   })    it('должен удалить листовые узлы', () => {     const bstRootNode = new BinarySearchTreeNode()      bstRootNode.insert(10)     bstRootNode.insert(20)     bstRootNode.insert(5)      expect(bstRootNode.toString()).toBe('5,10,20')      const removed1 = bstRootNode.remove(5)     expect(bstRootNode.toString()).toBe('10,20')     expect(removed1).toBe(true)      const removed2 = bstRootNode.remove(20)     expect(bstRootNode.toString()).toBe('10')     expect(removed2).toBe(true)   })    it('должен удалить узлы с одним потомком', () => {     const bstRootNode = new BinarySearchTreeNode()      bstRootNode.insert(10)     bstRootNode.insert(20)     bstRootNode.insert(5)     bstRootNode.insert(30)      expect(bstRootNode.toString()).toBe('5,10,20,30')      bstRootNode.remove(20)     expect(bstRootNode.toString()).toBe('5,10,30')      bstRootNode.insert(1)     expect(bstRootNode.toString()).toBe('1,5,10,30')      bstRootNode.remove(5)     expect(bstRootNode.toString()).toBe('1,10,30')   })    it('должен удалить узлы с двумя потомками', () => {     const bstRootNode = new BinarySearchTreeNode()      bstRootNode.insert(10)     bstRootNode.insert(20)     bstRootNode.insert(5)     bstRootNode.insert(30)     bstRootNode.insert(15)     bstRootNode.insert(25)      expect(bstRootNode.toString()).toBe('5,10,15,20,25,30')     expect(bstRootNode.find(20).left.value).toBe(15)     expect(bstRootNode.find(20).right.value).toBe(30)      bstRootNode.remove(20)     expect(bstRootNode.toString()).toBe('5,10,15,25,30')      bstRootNode.remove(15)     expect(bstRootNode.toString()).toBe('5,10,25,30')      bstRootNode.remove(10)     expect(bstRootNode.toString()).toBe('5,25,30')     expect(bstRootNode.value).toBe(25)      bstRootNode.remove(25)     expect(bstRootNode.toString()).toBe('5,30')      bstRootNode.remove(5)     expect(bstRootNode.toString()).toBe('30')   })    it('должен удалить узел без предка', () => {     const bstRootNode = new BinarySearchTreeNode()     expect(bstRootNode.toString()).toBe('')      bstRootNode.insert(1)     bstRootNode.insert(2)     expect(bstRootNode.toString()).toBe('1,2')      bstRootNode.remove(1)     expect(bstRootNode.toString()).toBe('2')      bstRootNode.remove(2)     expect(bstRootNode.toString()).toBe('')   })    it('должен удалить несуществующий узел', () => {     const bstRootNode = new BinarySearchTreeNode()      bstRootNode.insert(10)     bstRootNode.insert(20)      const removedNode = bstRootNode.remove(30)      expect(removedNode).toBeNull()   })    it('должен добавить объекты', () => {     const nodeValueComparatorCallback = (a, b) => {       const normalizedA = a || { value: null }       const normalizedB = b || { value: null }        if (normalizedA.value === normalizedB.value) {         return 0       }        return normalizedA.value < normalizedB.value ? -1 : 1     }      const obj1 = { key: 'obj1', value: 1, toString: () => 'obj1' }     const obj2 = { key: 'obj2', value: 2, toString: () => 'obj2' }     const obj3 = { key: 'obj3', value: 3, toString: () => 'obj3' }      const bstNode = new BinarySearchTreeNode(obj2, nodeValueComparatorCallback)     bstNode.insert(obj1)      expect(bstNode.toString()).toBe('obj1,obj2')     expect(bstNode.contains(obj1)).toBe(true)     expect(bstNode.contains(obj3)).toBe(false)      bstNode.insert(obj3)      expect(bstNode.toString()).toBe('obj1,obj2,obj3')     expect(bstNode.contains(obj3)).toBe(true)      expect(bstNode.findMin().value).toEqual(obj1)   })    it('должен обнулить предка удаленного узла', () => {     const rootNode = new BinarySearchTreeNode('foo')     rootNode.insert('bar')     const childNode = rootNode.find('bar')     rootNode.remove('bar')      expect(childNode.parent).toBeNull()   }) })

import BinaryTreeNode from './binary-tree-node' import Comparator from '../../utils/comparator'  export class BinarySearchTreeNode extends BinaryTreeNode {   constructor(value = null, fn) {     super(value)      this.compareFn = fn     this.nodeValueComparator = new Comparator(fn)   }    // Добавляет значение (узел)   insert(value) {     // Если значение отсутствует     if (this.nodeValueComparator.equal(this.value, null)) {       this.value = value        return this     }      // Если новое значение меньше текущего     if (this.nodeValueComparator.lessThan(value, this.value)) {       // Если имеется левый потомок,       if (this.left) {         // добавляем значение в него         return this.left.insert(value)       }        // Создаем новый узел       const newNode = new BinarySearchTreeNode(value, this.compareFn)       // и делаем его левым потомком       this.setLeft(newNode)        return newNode     }      // Если новое значение больше текущего     if (this.nodeValueComparator.greaterThan(value, this.value)) {       // Если имеется правый потомок,       if (this.right) {         // добавляем значение в него         return this.right.insert(value)       }        // Создаем новый узел       const newNode = new BinarySearchTreeNode(value, this.compareFn)       // и делаем его правым потомком       this.setRight(newNode)        return newNode     }      return this   }    // Удаляет узел по значению   remove(value) {     // Ищем удаляемый узел     const nodeToRemove = this.find(value)      if (!nodeToRemove) {       return null     }      // Извлекаем предка     const { parent } = nodeToRemove      if (!nodeToRemove.left && !nodeToRemove.right) {       // Узел является листовым, т.е. не имеет потомков       if (parent) {         // У узла есть предок. Просто удаляем указатель на этот узел у предка         parent.removeChild(nodeToRemove)       } else {         // У узла нет предка. Обнуляем значение текущего узла         nodeToRemove.setValue(null)       }     } else if (nodeToRemove.left && nodeToRemove.right) {       // Узел имеет двух потомков.       // Находим следующее большее значение (минимальное значение в правом поддереве)       // и заменяем им значение текущего узла       const nextBiggerNode = nodeToRemove.right.findMin()       if (!this.nodeComparator.equal(nextBiggerNode, nodeToRemove.right)) {         this.remove(nextBiggerNode.value)         nodeToRemove.setValue(nextBiggerNode.value)       } else {         // В случае, когда следующее правое значение является следующим большим значением,         // и этот узел не имеет левого потомка,         // просто заменяем удаляемый узел правым         nodeToRemove.setValue(nodeToRemove.right.value)         nodeToRemove.setRight(nodeToRemove.right.right)       }     } else {       // Узел имеет одного потомка.       // Делаем этого потомка прямым потомком предка текущего узла       const childNode = nodeToRemove.left || nodeToRemove.right        if (parent) {         parent.replaceChild(nodeToRemove, childNode)       } else {         BinaryTreeNode.copyNode(childNode, nodeToRemove)       }     }      // Обнуляем предка удаленного узла     nodeToRemove.parent = null      return true   }    // Ищет узел по значению   find(value) {     // Проверяем корень     if (this.nodeValueComparator.equal(this.value, value)) {       return this     }      if (this.nodeValueComparator.lessThan(value, this.value) && this.left) {       // Проверяем левое поддерево       return this.left.find(value)     }      if (this.nodeValueComparator.greaterThan(value, this.value) && this.right) {       // Проверяем правое поддерево       return this.right.find(value)     }      return null   }    // Определяет наличие узла   contains(value) {     return Boolean(this.find(value))   }    // Ищет узел с минимальным значением (нижний левый)   findMin() {     if (!this.left) {       return this     }      return this.left.findMin()   } }  export default class BinarySearchTree {   constructor(compareFn) {     // Корневой узел     this.root = new BinarySearchTreeNode(null, compareFn)     // Функция сравнения узлов     this.nodeComparator = this.root.nodeComparator   }    // Добавляет значение   insert(value) {     return this.root.insert(value)   }    // Удаляет узел по значению   remove(value) {     return this.root.remove(value)   }    // Определяет наличие узла   contains(value) {     return this.root.contains(value)   }    // Возвращает строковое представление дерева   toString() {     return this.root.toString()   } }

// data-structures/tree/__tests__/binary-search-tree.test.js import BinarySearchTree from '../binary-search-tree'  describe('BinarySearchTree', () => {   it('должен создать дерево', () => {     const bst = new BinarySearchTree()      expect(bst).toBeDefined()     expect(bst.root).toBeDefined()     expect(bst.root.value).toBeNull()     expect(bst.root.left).toBeNull()     expect(bst.root.right).toBeNull()   })    it('должен добавить значения', () => {     const bst = new BinarySearchTree()      const insertedNode1 = bst.insert(10)     const insertedNode2 = bst.insert(20)     bst.insert(5)      expect(bst.toString()).toBe('5,10,20')     expect(insertedNode1.value).toBe(10)     expect(insertedNode2.value).toBe(20)   })    it('должен определить наличие значений', () => {     const bst = new BinarySearchTree()      bst.insert(10)     bst.insert(20)     bst.insert(5)      expect(bst.contains(20)).toBe(true)     expect(bst.contains(40)).toBe(false)   })    it('должен удалить узлы', () => {     const bst = new BinarySearchTree()      bst.insert(10)     bst.insert(20)     bst.insert(5)      expect(bst.toString()).toBe('5,10,20')      const removed1 = bst.remove(5)     expect(bst.toString()).toBe('10,20')     expect(removed1).toBe(true)      const removed2 = bst.remove(20)     expect(bst.toString()).toBe('10')     expect(removed2).toBe(true)   })    it('должен добавить объекты', () => {     const nodeValueCompareFunction = (a, b) => {       const normalizedA = a || { value: null }       const normalizedB = b || { value: null }        if (normalizedA.value === normalizedB.value) {         return 0       }        return normalizedA.value < normalizedB.value ? -1 : 1     }      const obj1 = { key: 'obj1', value: 1, toString: () => 'obj1' }     const obj2 = { key: 'obj2', value: 2, toString: () => 'obj2' }     const obj3 = { key: 'obj3', value: 3, toString: () => 'obj3' }      const bst = new BinarySearchTree(nodeValueCompareFunction)      bst.insert(obj2)     bst.insert(obj3)     bst.insert(obj1)      expect(bst.toString()).toBe('obj1,obj2,obj3')   })    it('должен обойти дерево и вернуть отсортированный массив', () => {     const bst = new BinarySearchTree()      bst.insert(10)     bst.insert(-10)     bst.insert(20)     bst.insert(-20)     bst.insert(25)     bst.insert(6)      expect(bst.toString()).toBe('-20,-10,6,10,20,25')     expect(bst.root.height).toBe(2)      bst.insert(4)      expect(bst.toString()).toBe('-20,-10,4,6,10,20,25')     expect(bst.root.height).toBe(3)   }) })

import BinarySearchTree from './binary-search-tree'  // АВЛ-дерево расширяет двоичное дерево поиска export default class AvlTree extends BinarySearchTree {   // Добавляет значение (узел)   insert(value) {     // Обычная вставка     super.insert(value)      // Поднимаемся к корню, выполняя балансировку дерева     let currentNode = this.root.find(value)     while (currentNode) {       this.balance(currentNode)       currentNode = currentNode.parent     }   }    // Удаляет узел по значению   remove(value) {     // Обычное удаление     super.remove(value)      // Балансируем дерево, начиная с корня     this.balance(this.root)   }    // Балансирует дерево   balance(node) {     if (node.balanceFactor > 1) {       // Левый поворот       if (node.left.balanceFactor > 0) {         // Левый-левый поворот         this.rotateLeftLeft(node)       } else if (node.left.balanceFactor < 0) {         // Левый-правый поворот         this.rotateLeftRight(node)       }     } else if (node.balanceFactor < -1) {       // Правый поворот       if (node.right.balanceFactor < 0) {         // Правый-правый поворот         this.rotateRightRight(node)       } else if (node.right.balanceFactor > 0) {         // Правый-левый поворот         this.rotateRightLeft(node)       }     }   }    // Выполняет левый-левый поворот   rotateLeftLeft(rootNode) {     // Удаляем левого потомка     const leftNode = rootNode.left     rootNode.setLeft(null)      // Делаем левый узел потомком предка `rootNode`     if (rootNode.parent) {       rootNode.parent.setLeft(leftNode)     } else if (rootNode === this.root) {       // Если `rootNode` является корнем, делаем левый узел новым корнем       this.root = leftNode     }      // Если левый узел имеет правого потомка,     // делаем его левым потомком `rootNode`     if (leftNode.right) {       rootNode.setLeft(leftNode.right)     }      // Делаем `rootNode` правым потомком левого узла     leftNode.setRight(rootNode)   }    // Выполняет левый-правый поворот   rotateLeftRight(rootNode) {     // Удаляем левого потомка     const leftNode = rootNode.left     rootNode.setLeft(null)      // Удаляем правого потомка левого узла     const leftRightNode = leftNode.right     leftNode.setRight(null)      // Сохраняем левое поддерево `leftRightNode`     if (leftRightNode.left) {       leftNode.setRight(leftRightNode.left)       leftRightNode.setLeft(null)     }      rootNode.setLeft(leftRightNode)     leftRightNode.setLeft(leftNode)      // Выполняем левый-левый поворот     this.rotateLeftLeft(rootNode)   }    // Выполняет правый-правый поворот   rotateRightRight(rootNode) {     // Удаляем правого потомка     const rightNode = rootNode.right     rootNode.setRight(null)      // Делаем правый узел потомком предка `rootNode`     if (rootNode.parent) {       rootNode.parent.setRight(rightNode)     } else if (rootNode === this.root) {       // Если `rootNode` является корнем, делаем правый узел новым корнем       this.root = rightNode     }      // Если правый узел имеет левого потомка,     // делаем его правым потомком `rootNode`     if (rightNode.left) {       rootNode.setRight(rightNode.left)     }      // Делаем `rootNode` левым потомком правого узла     rightNode.setLeft(rootNode)   }    // Выполняет правый-левый поворот   rotateRightLeft(rootNode) {     // Удаляем правого потомка     const rightNode = rootNode.right     rootNode.setRight(null)      // Удаляем левого потомка правого узла     const rightLeftNode = rightNode.left     rightNode.setLeft(null)      // Сохраняем правое поддерево `rightLeftNode`     if (rightLeftNode.right) {       rightNode.setLeft(rightLeftNode.right)       rightLeftNode.setRight(null)     }      rootNode.setRight(rightLeftNode)     rightLeftNode.setRight(rightNode)      // Выполняем правый-правый поворот     this.rotateRightRight(rootNode)   } }

// data-structures/tree/__tests__/avl-tree.test.js import AvlTree from '../avl-tree'  describe('AvlTree', () => {   it('должен выполнить простой левый-левый поворот', () => {     const tree = new AvlTree()      tree.insert(4)     tree.insert(3)     tree.insert(2)      expect(tree.toString()).toBe('2,3,4')     expect(tree.root.value).toBe(3)     expect(tree.root.height).toBe(1)      tree.insert(1)      expect(tree.toString()).toBe('1,2,3,4')     expect(tree.root.value).toBe(3)     expect(tree.root.height).toBe(2)      tree.insert(0)      expect(tree.toString()).toBe('0,1,2,3,4')     expect(tree.root.value).toBe(3)     expect(tree.root.left.value).toBe(1)     expect(tree.root.height).toBe(2)   })    it('должен выполнить сложный левый-левый поворот', () => {     const tree = new AvlTree()      tree.insert(30)     tree.insert(20)     tree.insert(40)     tree.insert(10)      expect(tree.root.value).toBe(30)     expect(tree.root.height).toBe(2)     expect(tree.toString()).toBe('10,20,30,40')      tree.insert(25)     expect(tree.root.value).toBe(30)     expect(tree.root.height).toBe(2)     expect(tree.toString()).toBe('10,20,25,30,40')      tree.insert(5)     expect(tree.root.value).toBe(20)     expect(tree.root.height).toBe(2)     expect(tree.toString()).toBe('5,10,20,25,30,40')   })    it('должен выполнить простой правый-правый поворот', () => {     const tree = new AvlTree()      tree.insert(2)     tree.insert(3)     tree.insert(4)      expect(tree.toString()).toBe('2,3,4')     expect(tree.root.value).toBe(3)     expect(tree.root.height).toBe(1)      tree.insert(5)      expect(tree.toString()).toBe('2,3,4,5')     expect(tree.root.value).toBe(3)     expect(tree.root.height).toBe(2)      tree.insert(6)      expect(tree.toString()).toBe('2,3,4,5,6')     expect(tree.root.value).toBe(3)     expect(tree.root.right.value).toBe(5)     expect(tree.root.height).toBe(2)   })    it('должен выполнить сложный правый-правый поворот', () => {     const tree = new AvlTree()      tree.insert(30)     tree.insert(20)     tree.insert(40)     tree.insert(50)      expect(tree.root.value).toBe(30)     expect(tree.root.height).toBe(2)     expect(tree.toString()).toBe('20,30,40,50')      tree.insert(35)     expect(tree.root.value).toBe(30)     expect(tree.root.height).toBe(2)     expect(tree.toString()).toBe('20,30,35,40,50')      tree.insert(55)     expect(tree.root.value).toBe(40)     expect(tree.root.height).toBe(2)     expect(tree.toString()).toBe('20,30,35,40,50,55')   })    it('должен выполнить левый-правый поворот', () => {     const tree = new AvlTree()      tree.insert(30)     tree.insert(20)     tree.insert(25)      expect(tree.root.height).toBe(1)     expect(tree.root.value).toBe(25)     expect(tree.toString()).toBe('20,25,30')   })    it('должен выполнить правый-левый поворот', () => {     const tree = new AvlTree()      tree.insert(30)     tree.insert(40)     tree.insert(35)      expect(tree.root.height).toBe(1)     expect(tree.root.value).toBe(35)     expect(tree.toString()).toBe('30,35,40')   })    it('должен создать сбалансированное дерево: кейс #1', () => {     // @see: https://www.youtube.com/watch?v=rbg7Qf8GkQ4&t=839s     const tree = new AvlTree()      tree.insert(1)     tree.insert(2)     tree.insert(3)      expect(tree.root.value).toBe(2)     expect(tree.root.height).toBe(1)     expect(tree.toString()).toBe('1,2,3')      tree.insert(6)      expect(tree.root.value).toBe(2)     expect(tree.root.height).toBe(2)     expect(tree.toString()).toBe('1,2,3,6')      tree.insert(15)      expect(tree.root.value).toBe(2)     expect(tree.root.height).toBe(2)     expect(tree.toString()).toBe('1,2,3,6,15')      tree.insert(-2)      expect(tree.root.value).toBe(2)     expect(tree.root.height).toBe(2)     expect(tree.toString()).toBe('-2,1,2,3,6,15')      tree.insert(-5)      expect(tree.root.value).toBe(2)     expect(tree.root.height).toBe(2)     expect(tree.toString()).toBe('-5,-2,1,2,3,6,15')      tree.insert(-8)      expect(tree.root.value).toBe(2)     expect(tree.root.height).toBe(3)     expect(tree.toString()).toBe('-8,-5,-2,1,2,3,6,15')   })    it('должен создать сбалансированное дерево: кейс #2', () => {     // @see https://www.youtube.com/watch?v=7m94k2Qhg68     const tree = new AvlTree()      tree.insert(43)     tree.insert(18)     tree.insert(22)     tree.insert(9)     tree.insert(21)     tree.insert(6)      expect(tree.root.value).toBe(18)     expect(tree.root.height).toBe(2)     expect(tree.toString()).toBe('6,9,18,21,22,43')      tree.insert(8)      expect(tree.root.value).toBe(18)     expect(tree.root.height).toBe(2)     expect(tree.toString()).toBe('6,8,9,18,21,22,43')   })    it('должен выполнить левый-правый поворот с сохранением левого поддерева: кейс #1', () => {     const tree = new AvlTree()      tree.insert(30)     tree.insert(15)     tree.insert(40)     tree.insert(10)     tree.insert(18)     tree.insert(35)     tree.insert(45)     tree.insert(5)     tree.insert(12)      expect(tree.toString()).toBe('5,10,12,15,18,30,35,40,45')     expect(tree.root.height).toBe(3)      tree.insert(11)      expect(tree.toString()).toBe('5,10,11,12,15,18,30,35,40,45')     expect(tree.root.height).toBe(3)   })    it('должен выполнить левый-правый поворот с сохранением левого поддерева: кейс #2', () => {     const tree = new AvlTree()      tree.insert(30)     tree.insert(15)     tree.insert(40)     tree.insert(10)     tree.insert(18)     tree.insert(35)     tree.insert(45)     tree.insert(42)     tree.insert(47)      expect(tree.toString()).toBe('10,15,18,30,35,40,42,45,47')     expect(tree.root.height).toBe(3)      tree.insert(43)      expect(tree.toString()).toBe('10,15,18,30,35,40,42,43,45,47')     expect(tree.root.height).toBe(3)   })    it('должен удалить значения из дерева с правым-правым поворотом', () => {     const tree = new AvlTree()      tree.insert(10)     tree.insert(20)     tree.insert(30)     tree.insert(40)      expect(tree.toString()).toBe('10,20,30,40')      tree.remove(10)      expect(tree.toString()).toBe('20,30,40')     expect(tree.root.value).toBe(30)     expect(tree.root.left.value).toBe(20)     expect(tree.root.right.value).toBe(40)     expect(tree.root.balanceFactor).toBe(0)   })    it('должен удалить значения из дерева с левым-левым поворотом', () => {     const tree = new AvlTree()      tree.insert(10)     tree.insert(20)     tree.insert(30)     tree.insert(5)      expect(tree.toString()).toBe('5,10,20,30')      tree.remove(30)      expect(tree.toString()).toBe('5,10,20')     expect(tree.root.value).toBe(10)     expect(tree.root.left.value).toBe(5)     expect(tree.root.right.value).toBe(20)     expect(tree.root.balanceFactor).toBe(0)   })    it('должен выполнять балансировку дерева после удаления значений', () => {     const tree = new AvlTree()      tree.insert(1)     tree.insert(2)     tree.insert(3)     tree.insert(4)     tree.insert(5)     tree.insert(6)     tree.insert(7)     tree.insert(8)     tree.insert(9)      expect(tree.toString()).toBe('1,2,3,4,5,6,7,8,9')     expect(tree.root.value).toBe(4)     expect(tree.root.height).toBe(3)     expect(tree.root.balanceFactor).toBe(-1)      tree.remove(8)      expect(tree.root.value).toBe(4)     expect(tree.root.balanceFactor).toBe(-1)      tree.remove(9)      expect(tree.contains(8)).toBeFalsy()     expect(tree.contains(9)).toBeFalsy()     expect(tree.toString()).toBe('1,2,3,4,5,6,7')     expect(tree.root.value).toBe(4)     expect(tree.root.height).toBe(2)     expect(tree.root.balanceFactor).toBe(0)   }) })

import BinarySearchTree from './binary-search-tree'  // Цвета const COLORS = {   red: 'red',   black: 'black', }  // Название поля, в котором хранится цвет const PROP = 'color'  // Красно-черное дерево расширяет двоичное дерево поиска export default class RedBlackTree extends BinarySearchTree {   // Вставляет значение (узел)   insert(value) {     // Обычная вставка     const insertedNode = super.insert(value)      // Если добавляется корень,     // if (!this.root.left && !this.root.right) {     if (this.nodeComparator.equal(this.root, insertedNode)) {       // делаем его черным       this.makeNodeBlack(insertedNode)     } else {       // Делаем новый узел красным       this.makeNodeRed(insertedNode)     }      // Выполняем балансировку дерева     this.balance(insertedNode)      // Возвращаем добавленный узел     return insertedNode   }    // Удаляет узел   remove(value) {     throw new Error(`Невозможно удалить ${value}. Метод удаления не реализован`)   }    // Выполняет балансировку дерева   balance(node) {     // В случае корневого узла балансировать нечего     if (this.nodeComparator.equal(this.root, node)) return      // В случае черного предка балансировать нечего     if (this.isNodeBlack(node.parent)) return      const grandParent = node.parent.parent      // Если у узла есть красный дядя, то нужно выполнить перекрашивание     if (node.uncle && this.isNodeRed(node.uncle)) {       // Перекрашиваем предка и дядю в черный       this.makeNodeBlack(node.parent)       this.makeNodeBlack(node.uncle)        if (!this.nodeComparator.equal(this.root, grandParent)) {         // Перекрашиваем дедушку в красный, если он не является корнем         this.makeNodeRed(grandParent)       } else {         // Если дедушка - черный корень, ничего не делаем,         // поскольку корень уже имеет двух черных потоков,         // которых мы только что перекрасили         return       }        // Выполняем балансировку для перекрашенного дедушки       this.balance(grandParent)       // Если дядя узла черный или отсутствует, нужно выполнить повороты     } else if (!node.uncle || this.isNodeBlack(node.uncle)) {       if (grandParent) {         // Дедушка, которого мы получим после вращений         let newGrandParent          if (this.nodeComparator.equal(node.parent, grandParent.left)) {           // Левый поворот           if (this.nodeComparator.equal(node, grandParent.left.left)) {             // Левый-левый поворот             newGrandParent = this.leftLeftRotation(grandParent)           } else {             // Левый-правый поворот             newGrandParent = this.leftRightRotation(grandParent)           }         } else {           // Правый поворот           if (this.nodeComparator.equal(node, grandParent.right.right)) {             // Правый-правый поворот             newGrandParent = this.rightRightRotation(grandParent)           } else {             // Правый-левый поворот             newGrandParent = this.rightLeftRotation(grandParent)           }         }          // Если `newGrandParent` не имеет предка, делаем его корнем         // и красим в черный         if (newGrandParent && !newGrandParent.parent) {           this.root = newGrandParent           this.makeNodeBlack(this.root)         }          // Выполняем балансировку для нового дедушки         this.balance(newGrandParent)       }     }   }    // Выполняет левый-левый поворот   leftLeftRotation(grandParentNode) {     // Сохраняем предка дедушки     const grandGrandParent = grandParentNode.parent      // Определяем тип дедушки (левый или правый)     let grandParentNodeIsLeft     if (grandGrandParent) {       grandParentNodeIsLeft = this.nodeComparator.equal(         grandGrandParent.left,         grandParentNode,       )     }      // Сохраняем левого потомка дедушки     const parentNode = grandParentNode.left      // Сохраняем правого потомка предка     const parentRightNode = parentNode.right      // Делаем дедушку правым потомком предка     parentNode.setRight(grandParentNode)      // Делаем правого потомка предка левым потомком дедушки     grandParentNode.setLeft(parentRightNode)      // Заменяем дедушку предком     if (grandGrandParent) {       if (grandParentNodeIsLeft) {         grandGrandParent.setLeft(parentNode)       } else {         grandGrandParent.setRight(parentNode)       }     } else {       // Делаем предка корнем       parentNode.parent = null     }      // Перекрашиваем дедушку и предка     this.swapNodeColors(parentNode, grandParentNode)      // Возвращаем новый корень     return parentNode   }    // Выполняет левый-правый поворот   leftRightRotation(grandParentNode) {     // Сохраняем левый и левый правый узлы     const parentNode = grandParentNode.left     const childNode = parentNode.right      // Сохраняем левый узел потомка во избежание потери     // левого поддерева. Позже он будет перемещен в     // правое поддерево предка     const childLeftNode = childNode.left      // Делаем предка левым узлом потомка     childNode.setLeft(parentNode)      // Делаем левый узел потомка правым узлом предка     parentNode.setRight(childLeftNode)      // Помещаем левый правый узел на место левого     grandParentNode.setLeft(childNode)      // Выполняем левый-левый поворот     return this.leftLeftRotation(grandParentNode)   }    // Выполняет правый-правый поворот   rightRightRotation(grandParentNode) {     // Сохраняем предка дедушки     const grandGrandParent = grandParentNode.parent      // Определяем тип дедушки (левый или правый)     let grandParentNodeIsLeft     if (grandGrandParent) {       grandParentNodeIsLeft = this.nodeComparator.equal(         grandGrandParent.left,         grandParentNode,       )     }      // Сохраняем правого потомка дедушки     const parentNode = grandParentNode.right      // Сохраняем левого потомка предка     const parentLeftNode = parentNode.left      // Делаем дедушку левым потомком предка     parentNode.setLeft(grandParentNode)      // Делаем левого потомка предка правым потомком дедушки     grandParentNode.setRight(parentLeftNode)      // Заменяем дедушку предком     if (grandGrandParent) {       if (grandParentNodeIsLeft) {         grandGrandParent.setLeft(parentNode)       } else {         grandGrandParent.setRight(parentNode)       }     } else {       // Делаем предка корнем       parentNode.parent = null     }      // Перекрашиваем дедушку и предка     this.swapNodeColors(parentNode, grandParentNode)      // Возвращаем новый корень     return parentNode   }    // Выполняет правый-левый поворот   rightLeftRotation(grandParentNode) {     // Сохраняем правый и правый левый узлы     const parentNode = grandParentNode.right     const childNode = parentNode.left      // Сохраняем правый узел потомка во избежание потери     // правого поддерева. Позже он будет перемещен в     // левое поддерево предка     const childRightNode = childNode.right      // Делаем предка правым узлом потомка     childNode.setRight(parentNode)      // Делаем правый узел потомка левым узлом предка     parentNode.setLeft(childRightNode)      // Помещаем потомка на место предка     grandParentNode.setRight(childNode)      // Выполняем правый-правый поворот     return this.rightRightRotation(grandParentNode)   }    // Делает узел красным   makeNodeRed(node) {     node.meta.set(PROP, COLORS.red)      return node   }    // Делает узел черным   makeNodeBlack(node) {     node.meta.set(PROP, COLORS.black)      return node   }    // Проверяет, является ли узел красным   isNodeRed(node) {     return node.meta.get(PROP) === COLORS.red   }    // Проверяет, является ли узел черным   isNodeBlack(node) {     return node.meta.get(PROP) === COLORS.black   }    // Проверяет, покрашен ли узел   isNodeColored(node) {     return this.isNodeBlack(node) || this.isNodeRed(node)   }    // Перекрашивает узлы   swapNodeColors(node1, node2) {     const node1Color = node1.meta.get(PROP)     const node2Color = node2.meta.get(PROP)      node1.meta.set(PROP, node2Color)     node2.meta.set(PROP, node1Color)   } }

// data-structures/tree/__tests__/red-black-tree.test.js import RedBlackTree from '../red-black-tree'  describe('RedBlackTree', () => {   it('должен покрасить первый узел в черный', () => {     const tree = new RedBlackTree()      const firstInsertedNode = tree.insert(10)      expect(tree.isNodeColored(firstInsertedNode)).toBe(true)     expect(tree.isNodeBlack(firstInsertedNode)).toBe(true)     expect(tree.isNodeRed(firstInsertedNode)).toBe(false)      expect(tree.toString()).toBe('10')     expect(tree.root.height).toBe(0)   })    it('должен окрасить новые листовые узлы в красный', () => {     const tree = new RedBlackTree()      const firstInsertedNode = tree.insert(10)     const secondInsertedNode = tree.insert(15)     const thirdInsertedNode = tree.insert(5)      expect(tree.isNodeBlack(firstInsertedNode)).toBe(true)     expect(tree.isNodeRed(secondInsertedNode)).toBe(true)     expect(tree.isNodeRed(thirdInsertedNode)).toBe(true)      expect(tree.toString()).toBe('5,10,15')     expect(tree.root.height).toBe(1)   })    it('должен выполнить балансировку дерева', () => {     const tree = new RedBlackTree()      tree.insert(5)     tree.insert(10)     tree.insert(15)     tree.insert(20)     tree.insert(25)     tree.insert(30)      expect(tree.toString()).toBe('5,10,15,20,25,30')     expect(tree.root.height).toBe(3)   })    it('должен выполнить балансировку в случае черного предка', () => {     const tree = new RedBlackTree()      const node1 = tree.insert(10)      expect(tree.isNodeBlack(node1)).toBe(true)      const node2 = tree.insert(-10)      expect(tree.isNodeBlack(node1)).toBe(true)     expect(tree.isNodeRed(node2)).toBe(true)      const node3 = tree.insert(20)      expect(tree.isNodeBlack(node1)).toBe(true)     expect(tree.isNodeRed(node2)).toBe(true)     expect(tree.isNodeRed(node3)).toBe(true)      const node4 = tree.insert(-20)      expect(tree.isNodeBlack(node1)).toBe(true)     expect(tree.isNodeBlack(node2)).toBe(true)     expect(tree.isNodeBlack(node3)).toBe(true)     expect(tree.isNodeRed(node4)).toBe(true)      const node5 = tree.insert(25)      expect(tree.isNodeBlack(node1)).toBe(true)     expect(tree.isNodeBlack(node2)).toBe(true)     expect(tree.isNodeBlack(node3)).toBe(true)     expect(tree.isNodeRed(node4)).toBe(true)     expect(tree.isNodeRed(node5)).toBe(true)      const node6 = tree.insert(6)      expect(tree.isNodeBlack(node1)).toBe(true)     expect(tree.isNodeBlack(node2)).toBe(true)     expect(tree.isNodeBlack(node3)).toBe(true)     expect(tree.isNodeRed(node4)).toBe(true)     expect(tree.isNodeRed(node5)).toBe(true)     expect(tree.isNodeRed(node6)).toBe(true)      expect(tree.toString()).toBe('-20,-10,6,10,20,25')     expect(tree.root.height).toBe(2)      const node7 = tree.insert(4)      expect(tree.root.left.value).toEqual(node2.value)      expect(tree.toString()).toBe('-20,-10,4,6,10,20,25')     expect(tree.root.height).toBe(3)      expect(tree.isNodeBlack(node1)).toBe(true)     expect(tree.isNodeRed(node2)).toBe(true)     expect(tree.isNodeBlack(node3)).toBe(true)     expect(tree.isNodeBlack(node4)).toBe(true)     expect(tree.isNodeBlack(node4)).toBe(true)     expect(tree.isNodeRed(node5)).toBe(true)     expect(tree.isNodeBlack(node6)).toBe(true)     expect(tree.isNodeRed(node7)).toBe(true)   })    it('должен выполнить балансировку в случае красного дяди', () => {     const tree = new RedBlackTree()      const node1 = tree.insert(10)     const node2 = tree.insert(-10)     const node3 = tree.insert(20)     const node4 = tree.insert(-20)     const node5 = tree.insert(6)     const node6 = tree.insert(15)     const node7 = tree.insert(25)     const node8 = tree.insert(2)     const node9 = tree.insert(8)      expect(tree.toString()).toBe('-20,-10,2,6,8,10,15,20,25')     expect(tree.root.height).toBe(3)      expect(tree.isNodeBlack(node1)).toBe(true)     expect(tree.isNodeRed(node2)).toBe(true)     expect(tree.isNodeBlack(node3)).toBe(true)     expect(tree.isNodeBlack(node4)).toBe(true)     expect(tree.isNodeBlack(node5)).toBe(true)     expect(tree.isNodeRed(node6)).toBe(true)     expect(tree.isNodeRed(node7)).toBe(true)     expect(tree.isNodeRed(node8)).toBe(true)     expect(tree.isNodeRed(node9)).toBe(true)      const node10 = tree.insert(4)      expect(tree.toString()).toBe('-20,-10,2,4,6,8,10,15,20,25')     expect(tree.root.height).toBe(3)      expect(tree.root.value).toBe(node5.value)      expect(tree.isNodeBlack(node5)).toBe(true)     expect(tree.isNodeRed(node1)).toBe(true)     expect(tree.isNodeRed(node2)).toBe(true)     expect(tree.isNodeRed(node10)).toBe(true)     expect(tree.isNodeRed(node6)).toBe(true)     expect(tree.isNodeRed(node7)).toBe(true)     expect(tree.isNodeBlack(node4)).toBe(true)     expect(tree.isNodeBlack(node8)).toBe(true)     expect(tree.isNodeBlack(node9)).toBe(true)     expect(tree.isNodeBlack(node3)).toBe(true)   })    it('должен выполнить левый-левый поворот', () => {     const tree = new RedBlackTree()      const node1 = tree.insert(10)     const node2 = tree.insert(-10)     const node3 = tree.insert(20)     const node4 = tree.insert(7)     const node5 = tree.insert(15)      expect(tree.toString()).toBe('-10,7,10,15,20')     expect(tree.root.height).toBe(2)      expect(tree.isNodeBlack(node1)).toBe(true)     expect(tree.isNodeBlack(node2)).toBe(true)     expect(tree.isNodeBlack(node3)).toBe(true)     expect(tree.isNodeRed(node4)).toBe(true)     expect(tree.isNodeRed(node5)).toBe(true)      const node6 = tree.insert(13)      expect(tree.toString()).toBe('-10,7,10,13,15,20')     expect(tree.root.height).toBe(2)      expect(tree.isNodeBlack(node1)).toBe(true)     expect(tree.isNodeBlack(node2)).toBe(true)     expect(tree.isNodeBlack(node5)).toBe(true)     expect(tree.isNodeRed(node4)).toBe(true)     expect(tree.isNodeRed(node6)).toBe(true)     expect(tree.isNodeRed(node3)).toBe(true)   })    it('должен выполнить левый-правый поворот', () => {     const tree = new RedBlackTree()      const node1 = tree.insert(10)     const node2 = tree.insert(-10)     const node3 = tree.insert(20)     const node4 = tree.insert(7)     const node5 = tree.insert(15)      expect(tree.toString()).toBe('-10,7,10,15,20')     expect(tree.root.height).toBe(2)      expect(tree.isNodeBlack(node1)).toBe(true)     expect(tree.isNodeBlack(node2)).toBe(true)     expect(tree.isNodeBlack(node3)).toBe(true)     expect(tree.isNodeRed(node4)).toBe(true)     expect(tree.isNodeRed(node5)).toBe(true)      const node6 = tree.insert(17)      expect(tree.toString()).toBe('-10,7,10,15,17,20')     expect(tree.root.height).toBe(2)      expect(tree.isNodeBlack(node1)).toBe(true)     expect(tree.isNodeBlack(node2)).toBe(true)     expect(tree.isNodeBlack(node6)).toBe(true)     expect(tree.isNodeRed(node4)).toBe(true)     expect(tree.isNodeRed(node5)).toBe(true)     expect(tree.isNodeRed(node3)).toBe(true)   })    it('должен выполнить перекрашивание, левый-левый и левый-правый повороты', () => {     const tree = new RedBlackTree()      const node1 = tree.insert(10)     const node2 = tree.insert(-10)     const node3 = tree.insert(20)     const node4 = tree.insert(-20)     const node5 = tree.insert(6)     const node6 = tree.insert(15)     const node7 = tree.insert(30)     const node8 = tree.insert(1)     const node9 = tree.insert(9)      expect(tree.toString()).toBe('-20,-10,1,6,9,10,15,20,30')     expect(tree.root.height).toBe(3)      expect(tree.isNodeBlack(node1)).toBe(true)     expect(tree.isNodeRed(node2)).toBe(true)     expect(tree.isNodeBlack(node3)).toBe(true)     expect(tree.isNodeBlack(node4)).toBe(true)     expect(tree.isNodeBlack(node5)).toBe(true)     expect(tree.isNodeRed(node6)).toBe(true)     expect(tree.isNodeRed(node7)).toBe(true)     expect(tree.isNodeRed(node8)).toBe(true)     expect(tree.isNodeRed(node9)).toBe(true)      tree.insert(4)      expect(tree.toString()).toBe('-20,-10,1,4,6,9,10,15,20,30')     expect(tree.root.height).toBe(3)   })    it('должен выполнить правый-левый поворот', () => {     const tree = new RedBlackTree()      const node1 = tree.insert(10)     const node2 = tree.insert(-10)     const node3 = tree.insert(20)     const node4 = tree.insert(-20)     const node5 = tree.insert(6)     const node6 = tree.insert(30)      expect(tree.toString()).toBe('-20,-10,6,10,20,30')     expect(tree.root.height).toBe(2)      expect(tree.isNodeBlack(node1)).toBe(true)     expect(tree.isNodeBlack(node2)).toBe(true)     expect(tree.isNodeBlack(node3)).toBe(true)     expect(tree.isNodeRed(node4)).toBe(true)     expect(tree.isNodeRed(node5)).toBe(true)     expect(tree.isNodeRed(node6)).toBe(true)      const node7 = tree.insert(25)      const rightNode = tree.root.right     const rightLeftNode = rightNode.left     const rightRightNode = rightNode.right      expect(rightNode.value).toBe(node7.value)     expect(rightLeftNode.value).toBe(node3.value)     expect(rightRightNode.value).toBe(node6.value)      expect(tree.toString()).toBe('-20,-10,6,10,20,25,30')     expect(tree.root.height).toBe(2)      expect(tree.isNodeBlack(node1)).toBe(true)     expect(tree.isNodeBlack(node2)).toBe(true)     expect(tree.isNodeBlack(node7)).toBe(true)     expect(tree.isNodeRed(node4)).toBe(true)     expect(tree.isNodeRed(node5)).toBe(true)     expect(tree.isNodeRed(node3)).toBe(true)     expect(tree.isNodeRed(node6)).toBe(true)   })    it('должен выполнить левый-левый поворот с левым дедушкой', () => {     const tree = new RedBlackTree()      tree.insert(20)     tree.insert(15)     tree.insert(25)     tree.insert(10)     tree.insert(5)      expect(tree.toString()).toBe('5,10,15,20,25')     expect(tree.root.height).toBe(2)   })    it('должен выполнить правый-правый поворот с левым дедушкой', () => {     const tree = new RedBlackTree()      tree.insert(20)     tree.insert(15)     tree.insert(25)     tree.insert(17)     tree.insert(19)      expect(tree.toString()).toBe('15,17,19,20,25')     expect(tree.root.height).toBe(2)   })    it('должен выбросить исключение при попытке удалить узел', () => {     const removeNodeFromRedBlackTree = () => {       const tree = new RedBlackTree()        tree.remove(1)     }      expect(removeNodeFromRedBlackTree).toThrowError()   }) })