1. Концепция
Дерево бинарного поиска также становится бинарным деревом сортировки. Он имеет характерную характеристику, что если у узла есть два дочерних узла, он должен быть удовлетворен. Значение левого дочернего узла должно быть меньше значения узла, а значение правого дочернего узла должно быть больше, чем значение узла. Для сравнения не базовых типов можно реализовать интерфейс компаратора. В этой статье данные типа int используются для работы.
Чтобы реализовать бинарное дерево, вы должны начать с его увеличения. Только создание дерева, вы можете использовать другие операции.
2. Строительство бинарного дерева поиска
Говоря о увеличении бинарных деревьев, мы должны сначала построить класс, представляющий узел. Класс узла имеет несколько атрибутов, значение узла, родительского узла, левого узла и правого узла узла. Код выглядит следующим образом
Статический класс узел {узел родитель; Узел левый; Узел Rightchild; int val; Публичный узел (родитель узла, левый узел, узел Rightchild, int val) {super (); this.parent = родитель; this.leftChild = LeftChild; this.rightChild = RightChild; this.val = val; } public node (int val) {this (null, null, null, val); } public node (Node Node, int val) {this (node, null, null, val); }}Здесь мы используем метод внутреннего написания класса. После построения значения узла мы построим все дерево. Дерево должно сначала иметь корневой узел, а затем распространяться на оставшиеся дочерние узлы. В этом дереве есть также некоторые атрибуты, такие как основной корень корневого узла и размер элемента в дереве. Если эти два атрибута используются, может быть добавлен атрибут компаратора, или может быть предоставлена реализация по умолчанию. Конкретный код выглядит следующим образом
открытый класс SearchBinaryTree {Private Node Root; частный размер Int; public searchbinarytree () {super (); }}3. Добавить
При добавлении элементов вы должны рассмотреть инициализацию корневого узла. Как правило, существует два типа: когда конструктор этого класса инициализируется, корень корневого узла будет инициализирован. Второе - добавить корневой узел при добавлении первого элемента. Оба они работают в теории, но обычно используют вторую ленивую форму загрузки.
При добавлении элементов есть несколько ситуаций, которые необходимо учитывать
1. При добавлении определите, инициализируется ли корень. Если он не инициализирован, он будет инициализирован. Назначьте значение корневому узлу и добавьте один размер.
2. Поскольку дерево поиска двоичного дерева удовлетворяет, что значение корневого узла больше, чем левый узел, и меньше правого узла, вставленное значение должно сравниваться с корневым узлом в первую очередь. Если он большой, найдите в правом поддере. Если он маленький, найдите в левом поддерере. Пока детский узел.
Реализация вставки здесь может принять два типа: один, рекурсия, два, итеративные (то есть через режим петли).
3.1. Рекурсивная вставка версий
public boolean add (int val) {if (root == null) {root = new Node (val); размер ++; вернуть истину; } Node node = getAdapternode (root, val); Node newnode = new Node (val); if (node.val> val) {node.leftchild = newNode; newnode.parent = node; } else if (node.val <val) {node.rightchild = newNode; newnode.parent = node; } else {// Нет обработки для времени} size ++; 19 вернуть true; } /*** Получить родительский узел узла, который будет вставлен. Родительский узел удовлетворяет одному из следующих состояний* 1. Родительский узел - это дочерний узел* 2. Значение вставленного узла меньше, чем родительский узел, но родительский узел не имеет левого дочернего узла* 3. Значение вставленного узла больше, чем родительский узел, но родительский узел не имеет правого детского узла* 4. Значение взинания. * 5. Родительский узел пуст* Если один из 5 выше 5 случаев будет выполнен, он остановится рекурсивно. * @param node * @param val * @return */ private node getAdapternode (node node, int val) {if (node == null) {return node; } // Вставьте в левый поддерек, но нет левого поддерева, if (node.val> val && node.leftchild == null) {return node; } // Вставьте в правый поддерек, но нет правого поддерева, также вернуть if (node.val <val && node.rightchild == null) {return node; } // Вставьте в правый поддерек, но нет правого поддерева, также вернуть if (node.val <val && node.rightchild == null) {return node; } // Вставьте в правый поддерек, но нет правого поддерева, также вернуть if (node.val <val && node.rightchild == null) {return node; } // Вставить в правый поддерек, но нет правого подтерека, также верните if (node.leftchild == null && node.rightchild == null) {return node; } if (node.val> val && node.leftchild! = null) {return getAdaptarnode (node.leftchild, val); } else if (node.val <val && node.rightchild! = null) {return getAdaptarnode (node.rightchild, val); } else {return node; }}Используйте рекурсию, сначала найдите конечную точку рекурсии, а затем превратите всю проблему в подпрограмму. В приведенном выше коде логика примерно такая: сначала определите, инициализируется ли корневой узел, и если он не инициализируется, он инициализируется, и после завершения он возвращает, а затем используйте функцию для получения адаптированного узла. Затем вставьте значение.
3.2. Итеративная версия
Public Boolean Put (int val) {return putval (root, val); } private boolean putval (узлы узла, int val) {if (node == null) {// инициализировать root node node = new Node (val); root = node; размер ++; вернуть истину; } Узел temp = node; Узел P; int t; / ** * Получите лучший узел через DO, пока итерация цикла, */ do {p = temp; t = temp.val-val; if (t> 0) {temp = temp.leftchild; } else if (t <0) {temp = temp.rightChild; } else {temp.val = val; вернуть ложь; }} while (temp! = null); Node newnode = new Node (p, val); if (t> 0) {p.leftchild = newNode; } else if (t <0) {p.rightChild = newNode; } size ++; вернуть истину; }Принцип на самом деле такой же, как рекурсия, который состоит в том, чтобы получить лучший узел и работать на этом узле.
С точки зрения производительности, это определенно лучшая итеративная версия, поэтому в целом это итеративная версия для работы в данных.
4. Удалить
Можно сказать, что при работе бинарного дерева поиска удаление является наиболее сложным, и есть относительно много ситуаций, которые следует рассмотреть. По обычным способом, если вы удалите узел в бинарном дереве поиска, вы обязательно подумаете о следующих четырех ситуациях.
1. Узел, который должен быть удален, не имеет левых и правых узлов дочерних узлов, как показано в узлах D, E и G на рисунке выше
2. Узел, который должен быть удален, - это только левый детский узел, такой как узел B
3. Узел, который должен быть удален, - это только правильный дочерний узел, такой как узел F
4. Узел, который должен быть удален
В первых трех ситуациях можно сказать, что это относительно просто, а четвертый сложный. Давайте проанализируем первый
Если это так, например, если узел D удален, левый дочерний узел узла B может быть установлен на NULL, и если узел G удален, правый дочерний узел узла F может быть установлен на NULL. Какая сторона должна быть установлена, и посмотрите, какую сторону находится удаленный узел.
Второй способ удалить узел B, вам просто нужно установить левый узел узла A до узла D, а родительский узел узла D - A. Какая сторона установлена, зависит от того, какая сторона удаленного узла расположена на родительском узле.
Третий тип такой же, как у второго типа.
Четвертый тип, который немного сложный, как упоминалось ранее, является, например, для удаления узла C, установить родительский узел узла F в узел A, установите левый узел F -узла E, установите правый узел A в узле F, установите родительский узел E на узел F (то есть замените F -узлы C), и есть другой тип, непосредственно. Итак, какой из них следует использовать? Если узел удаления является корневым узлом, как мне удалить его?
Для четвертого случая вы можете подумать об этом так: найти узел преемника C или узла, удалить узел преемника и установить значение узла преемника на значение C или узла. Давайте сначала добавим концепцию узлов преемников.
Узел преемника узла во всем дереве должен быть удовлетворен. Узел с наименьшим значением в наборе узлов, стоимостью узла, является узлом преемника. Конечно, не может быть никаких узлов преемника.
Однако, для четвертого случая, узел преемника должен существовать и должен находиться в его правом поддерею, а также соответствует одному из случаев, когда существует только один узел дочернего узела или нет узел детей. Конкретная причина можно подумать об этом, потому что узел преемника больше, чем у узла C, а также, поскольку должны существовать левые и правые подразделы C-узла, он должен существовать в левом подразделе в правом подрисе. Например, узел преемника C - это F, а узел преемника A IS E.
При вышеуказанном анализе реализация относительно проста, код выглядит следующим образом
public boolean delete (int val) {node node = getNode (val); if (node == null) {вернуть false; } Node parent = node.parent; Node Leatschild = node.leftChild; Node RightChild = node.rightChild; // Все следующие родительские узлы пусты, это означает, что удаленный узел является корневым узлом if (LeftChild == null && rightchild == null) {// Нет дочерних узлов if (parent! = Null) {if (parent.leftchild == node) {parent.leftchild = null; } else if (parent.rightchild == node) {parent.rightchild = null; }} else {// родительский узел не существует, что означает, что удаленный узел является корневым узлом root = null; } node = null; вернуть истину; } else if (LeatHild == null && rightchild! = null) {// только правый узел if (parent! = null && parent.val> val) {// Существует родительский узел, а положение узла - левая сторона родительского узла. } else if (parent! = null && parent.val <val) {// Существует родительский узел, а положение узла - правая сторона родительского узла Parent.rightChild = RightChild; } else {root = RightChild; } node = null; вернуть истину; } else if (LeatsChild! = null && rightChild == null) {// только левый узел if (parent! = null && parent.val> val) {// Существует родительский узел, а положение узела - левая сторона родительского узла parent.leftchild = LeftChild; } else if (parent! = null && parent.val <val) {// Существует родительский узел, а положение узела - правая сторона родительского узла Parent.rightChild = LeftChild; } else {root = LeftChild; } вернуть true; } else if (Leatschild! = null && rightchild! = null) {// Оба дочерних узла имеют преемник узла = getSuccessor (node); // В этом случае должен быть узел преемника int temp = custor.val; логическое удаление = delete (temp); if (delete) {node.val = temp; } преемник = null; вернуть истину; } вернуть false; } /*** Найдите узел преемника узла узла* 1. Сначала определите, имеет ли узел правый поддерек. Если так, ищите узел преемника из левого поддерево правого узла. Если нет, перейдите к следующему шагу* 2. Найдите родительский узел узла. Если правый узел родительского узла равен узлу, продолжайте искать родительский узел * до тех пор, пока родительский узел не станет нулевым или не найдет правый узел, который не равн узлу. * Причина, узел преемника должен быть больше, чем узел. Если есть правый поддерево, узел преемника должен существовать в правом поддерере. Это является причиной первого шага* Если нет правильного поддерева, может также быть узел дедушки узела (то есть родительский узел узла или родительский узел над родительским узлом). * Итеративно ищите его, если есть, он возвращает узел, и если нет, он возвращает null * @param node * @return */ private node getCcessor (узлы узла) {if (node.rightchild! = Null) {node rightchild = node.rightchild; while (rightchild.leftchild! = null) {rightchild = rightchild.leftchild; } вернуть RightChild; } Node parent = node.parent; while (parent! = null && (node == parent.rightchild)) {node = parent; parent = parent.parent; } вернуть родитель; }Для конкретной логики, пожалуйста, обратитесь к вышеуказанному анализу. Я не буду описать текст здесь.
В дополнение к этой реализации, представлена другая реализация во введении в алгоритм.
public boolean remove (int val) {node node = getNode (val); if (node == null) {вернуть false; } if (node.leftchild == null) {// 1.. Левый узел не существует, может существовать правого узла, включая две ситуации. Оба узла не существуют, и только правый узел существует трансплантат (узел, node.rightchild); } else if (node.rightchild == null) {// 2. Левый ребенок существует, и правый узел не существует пересадки (узел, node.leftchild); } else {// 3. Оба узла имеют Node Custoror = getSuccessor (node); // Получить узлом преемника узла if (custcortor.parent! = node) {// Узел преемника существует в правом подтерянии узла. трансплантат (преемник, преемник пересадка (узел, преемник); преемник.leftchild = node.leftchild; преемник.leftchild.parent = преемник; } вернуть true; } /*** Заменить узел дочернего узла узлом узла* @param root root node* @param Узел узла узла дочернего узла дочернего узла дочернего узела дочернего узела дочернего узела (узел узла, узел, ребенок) { /*** 1. Сначала определяет, что у узла нет узел. step* 2. Determine that the node node is the child of the parent node (that is, determine whether the node is a right node or a left node), * After obtaining the result, replace the child node with node node, that is, if the node node is a left node, child will also be the left node after being replaced, otherwise it is the right node* 3. Set the parent node of the node node as the parent node of the child узел*/ if (node.parent == null) {this.root = ребенок; } else if (node.parent.leftchild == node) {node.parent.leftchild = child; } else if (node.parent.rightChild == node) {node.parent.rightChild = ребенок; } if (ребенок! = null) {child.parent = node.parent; }}5. Поиск
Поиск также относительно прост, но на самом деле он был реализован, когда он добавлен. В реальных ситуациях эта часть может быть извлечена из отдельного метода. Код выглядит следующим образом
public node getNode (int val) {node temp = root; int t; do {t = temp.val-val; if (t> 0) {temp = temp.leftchild; } else if (t <0) {temp = temp.rightChild; } else {return temp; }} while (temp! = null); вернуть ноль; }6. Двуичное поисковое дерево
После понимания свойств бинарного дерева поиска ясно, что его промежуточный порядок расположен в последовательности от малого до большого. Вот промежуточный код обходов, предоставленный здесь
public void print () {print (root); } private void print (node root) {if (root! = null) {print (root.leftchild); System.out.println (root.val); // Если положение находится в середине, то порядок находится в середине. Если это спереди, он находится в прецеденте, в противном случае это последующий отпечаток (root.rightchild); }} Суммировать
Выше приведено внедрение Java функции бинарного поиска, представленной редактором. Я надеюсь, что это будет полезно для всех. Если у вас есть какие -либо вопросы, пожалуйста, оставьте мне сообщение. Редактор ответит всем вовремя!