Реализация и применение бинарного дерева и бинарного дерева поиска в JavaScript

JavaScript

Давайте рассмотрим дерево в структуре данных JS. Дерево здесь аналогично дереву в реальной жизни, с стволом и ветвями. В программе дерево - это структура данных, которая не полезна для хранения данных, которые необходимо быстро искать. Это абстрактная модель иерархических данных. Отказ Структура дерева состоит из серии узлов в родительских отношениях. Каждый узел имеет родительский узел и ноль или более детских узлов. Как следует так, чтобы это древовидная структура :)

Понятия, связанные с деревьями: 1.поддерево: состоит из узла и его потомков, как показано на рисунке выше. 2.глубина: Глубина узла зависит от количества его узлов-предков, например, узел 5 имеет 2 узла-предка, а его глубина равна 2,3.высоко: Высота дерева зависит от максимальной глубины всех узлов.

Введение в бинарные деревья и бинарные деревья поиска

Узел в двоичном дереве может иметь не более 2 дочерних узлов, один из которых является левым дочерним узлом, а другой - правым дочерним узлом.Преимущество этого определения заключается в том, что нам полезно писать более эффективные алгоритмы для вставки, поиск и удаление узлов.

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

1. Создайте класс BinarySearchTree.

Здесь мы будем использовать конструктор для создания класса:

function BinarySearchTree(){
    // 用于创建节点的类
    let Node = function(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
    // 根节点
    let root = null;
}

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

2. Вставьте ключ

// 插入一个键
this.insert = function(key) {
    let newNode = new Node(key);
    root === null ? (root = newNode) : (insertNode(root, newNode))
}

Вставка нового узла в дерево в основном состоит из следующих трех частей: 1. Создайте экземпляр класса Node нового узла --> 2. Определите, является ли операция вставки корневым узлом, и если это корневой узел, укажите его. к корневому узлу --> 3. Присоединитесь к узлу в другом месте, кроме корневого узла.

Конкретная реализация insertNode выглядит следующим образом:

function insertNode(node, newNode){
    if(newNode.key < node.key) {
        node.left === null ? (node.left = newNode) : (insertNode(node.left, newNode))
    }else {
        node.right === null ? (node.right = newNode) : (insertNode(node.right, newNode))
    }
}

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

let tree = new BinarySearchTree();
tree.insert(20);
tree.insert(21);
tree.insert(520);
tree.insert(521);

Вставленная структура будет вставлена ​​в соответствии с правилами бинарного дерева поиска, и структура аналогична первой диаграмме дерева выше.

обход дерева

Есть три способа обойти все узлы дерева: по порядку, по предварительному порядку и по порядку.

  • Неупорядоченный обход: посещение всех узлов в порядке от наименьшего к наибольшему
  • Обход в предварительном порядке: посещение каждого узла в порядке, который имеет приоритет над узлами-потомками.
  • Обход в обратном порядке: сначала посетите узлы-потомки узла, а затем посетите сам узел.

Согласно приведенному выше введению, у нас может быть следующий код реализации.

  1. Сортировка по порядку
this.inOrderTraverse = function(cb){
    inOrderTraverseNode(root, cb);
}

// 辅助函数
function inOrderTraverseNode(node, cb){
    if(node !== null){
        inOrderTraverseNode(node.left, cb);
        cb(node.key);
        inOrderTraverseNode(node.right, cb);
    }
}

Использование обхода по порядку может реализовать функцию сортировки дерева от меньшего к большему.

  1. предварительный заказ
// 先序排序 --- 优先于后代节点的顺序访问每个节点
   this.preOrderTraverse = function(cb) {
     preOrderTraverseNode(root, cb);
   }

   // 先序排序辅助方法
   function preOrderTraverseNode(node, cb) {
     if(node !== null) {
       cb(node.key);
       preOrderTraverseNode(node.left, cb);
       preOrderTraverseNode(node.right, cb);
     }
   }

С помощью сортировки по предварительному заказу можно реализовать функцию структурированного вывода.

  1. пост-заказ
// 后续遍历 --- 先访问后代节点，再访问节点本身
   this.postOrderTraverse = function(cb) {
     postOrderTraverseNode(root, cb);
   }

   // 后续遍历辅助方法
   function postOrderTraverseNode(node, cb) {
     if(node !== null){
       postOrderTraverseNode(node.left, cb);
       postOrderTraverseNode(node.right, cb);
       cb(node.key);
     }
   }

Обход в обратном порядке можно использовать для вычисления размера всех элементов в иерархическом отношении.

значение в дереве поиска

Существует три типа поиска, которые часто выполняются в дереве: максимальное значение, минимальное значение и конкретное значение.

  1. минимум

По определению минимальное значение может быть известно как нижний узел левого дерева.Конкретный код реализации выглядит следующим образом:

// 最小值
   this.min = function(){
     return minNode(root)
   }

    function minNode(node) {
     if(node) {
       while(node && node.left !== null){
         node = node.left;
       }
       return node.key
     }
     return null
   }

Точно так же способ достижения максимального значения выглядит следующим образом:

// 最大值
   this.max = function() {
     return maxNode(root)
   }

   function maxNode(node) {
     if(node){
       while(node && node.right !== null){
         node = node.right;
       }
       return node.key
     }
     return null
   }

2. Поиск определенного значения

// 搜索树中某个值
this.search = function(key) {
    return searchNode(root, key)
}

// 搜索辅助方法
function searchNode(node, key){
    if(node === null) {
        return false
    }
    if(key < node.key) {
        return searchNode(node.left, key)
    } else if(key > node.key) {
        return searchNode(node.right, key)
    }else {
        return true
    }
}
  1. удалить узел
this.remove = function(key){
    root = removeNode(root, key);
}

// 发现最小节点
function findMinNode(node) {
    if(node) {
    while(node && node.left !== null){
        node = node.left;
    }
    return node
    }
    return null
}

// 移除节点辅助方法
function removeNode(node, key) {
    if(node === null) {
    return null
    }

    if(key < node.key){
    node.left = removeNode(node.left, key);
    return node
    } else if( key > node.key){
    node.right = removeNode(node.right, key);
    return node
    } else {
    // 一个页节点
    if(node.left === null && node.right === null) {
        node = null;
        return node
    }

    // 只有一个子节点的节点
    if(node.left === null) {
        node = node.right;
        return node
    }else if(node.right === null) {
        node = node.left;
        return node
    }

    // 有两个子节点的节点
    let aux = findMinNode(node.right);
    node.key = aux.key;
    node.right = removeNode(node.right, aux.key);
    return node
    }
}

Есть много ситуаций, которые следует учитывать при удалении узла.Здесь мы будем использовать реализацию, аналогичную min, чтобы написать функцию для поиска наименьшего узла.Когда удаляемый узел имеет два дочерних узла, нам нужно заменить удаляемый узел с дочерним узлом Значение самого большого узла в , а затем удалить этот дочерний узел.

На данный момент реализовано бинарное дерево поиска, но все еще есть проблема.Если один проход дерева будет очень глубоким, будут определенные проблемы с производительностью.Для решения этой проблемы мы можем использоватьАВЛ-дерево, самобалансирующееся бинарное дерево, то есть разница между высотами левого и правого поддеревьев любого узла не превосходит 1.

Если вы хотите узнать больше об алгоритмах js и структурах данных, вы можете долго нажимать и следовать~

больше рекомендаций

Категории