Бинарное дерево поиска на PHP
Этот пост явился следствием прочтения вот этого перевода статьи о структурах данных для PHP-прогрммистов. В посте было рассказано о некоторых структурах данных, в том числе о бинарном дереве поиска, но самую интересную часть, то есть удаление узлов бинарного дерева, автор обошел стороной.
После прочтения перевода у меня появилось жгучее желание реализовать это дерево на PHP полнофункционально, то есть, включая удаление узлов из него, что я и сделал ниже по тексту:)
Обратите внимание, что я не призываю использовать бинарное дерево поиска написанное на PHP в реальном коде, реализация носит исключительно образовательный характер).
И так, реализация дерева и операции вставки нового узла, я думаю, в комментариях не нуждаются, так как практически ничем не отличаются от реализации в переводе:
class BinaryNode < public $value; public $left = NULL; public $right = NULL; public function __construct ($value) < $this->value = $value; > > class BinaryTree < protected $root = NULL; public function isEmpty () < return is_null($this->root); > public function insert ($value) < $node = new BinaryNode($value); $this->insertNode($node, $this->root); > protected function insertNode (BinaryNode $node, &$subtree) < if (is_null($subtree)) < $subtree = $node; >else < if ($node->value < $subtree->value) < $this->insertNode($node, $subtree->left); > elseif ($node->value > $subtree->value) < $this->insertNode($node, $subtree->right); > > return $this; > > Что бы удалить узел дерева, нам сначала понадобится его найти. Для этого напишем рекурсивную функцию поиска узла в нашем дереве:
protected function &findNode ($value, &$subtree) < // Если элемент не найден, возвращаем FALSE if (is_null($subtree)) < return FALSE; >// Для искомого значения меньшего, чем значение узла, продолжаем искать в левом поддереве if ($subtree->value > $value) < return $this->findNode($value, $subtree->left); > // Для искомого значения большего, чем значение узла, продолжаем искать в правом поддереве elseif ($subtree->value < $value) < return $this->findNode($value, $subtree->right); > // Если искомое значение равно значению узла, то возвращаем этот узел else < return $subtree; >> Приступим к реализации алгоритма удаления узла из дерева. Суть алгоритма такова:
- если у узла нет потомков (поддеревьев), то смело его удаляем;
- если есть один потомок (только правое или левое поддерево), то заменяем удаляемый узел потомком;
- если есть оба потомка, то:
- если у правого поддерева нет левого потомка, то заменяем удаляемый узел правым потомком, сохраняя левую ветвь удаляемого узла;
- если у правого поддерева есть левый потомок, то копируем его значение в удаляемый узел и рекурсивно удаляем.
Непосредственно метод удаления узла:
public function delete ($value) < // Выьрасываем исключение при попытке удаления элемента из пустого дерева if ($this->isEmpty()) < throw new UnderflowException('Tree is empty!'); >// Ищем нод в дереве $node = &$this->findNode($value, $this->root); // Если нод найден в дереве, то рекурсивно удаляем его if ($node) < $this->deleteNode($node); > return $this; > // Метод рекурсивного удаления, найденого нода из дерева protected function deleteNode (BinaryNode &$node) < // Если у узла нет потомков, удаляем его if (is_null($node->left) && is_null($node->right)) < $node = NULL; >// Если у узла нет левого поддерева, заменяем его правым поддеревом elseif (is_null($node->left)) < $node = $node->right; > // Если у узла нет правого поддерева, заменяем его левым поддеревом elseif (is_null($node->right)) < $node = $node->left; > // Если у узла есть оба потомка else < // Если у правого поддерева нет левого потомка, то заменяем удаляемый узел правым потомком, сохраняя левую ветвь удаляемого узла if (is_null($node->right->left)) < $node->right->left = $node->left; $node = $node->right; > // если у правого поддерева есть левый потомок, то копируем его значение в удаляемый узел и рекурсивно удаляем else < $node->value = $node->right->left->value; $this->deleteNode($node->right->left); > > >Бинарное дерево поиска готово.
P.S.: В листингах кода, я намеренно вырезал phpdoc-комментарии и не использовал пространства имен, чтобы их не загромождать.
Полные версии исходных кодов бинарного дерева поиска (а так же реализации еще нескольких структур данных, — одно/двухсвязные списков и стека/очереди, реализованных с помощью этих списков) можно посмотреть на githubе.Читайте также
Cлучайные числа с плавающей точкой в PHP Стандартные библиотеки PHP умеют генерировать только целые случайные числа. Однако, возникают задачи где нужно не целое рандомное число с максимально…
Как установить библиотеку ncurses для PHP yum install ncurses-devel phpize —clean phpize ./configure (./configure —with-php-config=/usr/bin/php-config —enable-ncursesw=autodetect —with-ncurses) make make install ls /usr/lib/php/modules/ncurses.so nano /etc/php.d/ncurses.ini extension=ncurses.so php…
Почему стоит перейти с Drupal на Laravel Когда приходит понимание того, что технология, любимая многими, тебя настолько устарела, что ты готов к кардинальным изменениям. Многие разработчики крутили…
Источник
Бинарное дерево поиска на PHP
Этот пост явился следствием прочтения вот этого перевода статьи о структурах данных для PHP-прогрммистов. В посте было рассказано о некоторых структурах данных, в том числе о бинарном дереве поиска, но самую интересную часть, то есть удаление узлов бинарного дерева, автор обошел стороной.
После прочтения перевода у меня появилось жгучее желание реализовать это дерево на PHP полнофункционально, то есть, включая удаление узлов из него, что я и сделал ниже по тексту:)
Обратите внимание, что я не призываю использовать бинарное дерево поиска написанное на PHP в реальном коде, реализация носит исключительно образовательный характер).И так, реализация дерева и операции вставки нового узла, я думаю, в комментариях не нуждаются, так как практически ничем не отличаются от реализации в переводе:
class BinaryNode < public $value; public $left = NULL; public $right = NULL; public function __construct ($value) < $this->value = $value; > > class BinaryTree < protected $root = NULL; public function isEmpty () < return is_null($this->root); > public function insert ($value) < $node = new BinaryNode($value); $this->insertNode($node, $this->root); > protected function insertNode (BinaryNode $node, &$subtree) < if (is_null($subtree)) < $subtree = $node; >else < if ($node->value < $subtree->value) < $this->insertNode($node, $subtree->left); > elseif ($node->value > $subtree->value) < $this->insertNode($node, $subtree->right); > > return $this; > >Что бы удалить узел дерева, нам сначала понадобится его найти. Для этого напишем рекурсивную функцию поиска узла в нашем дереве:
protected function &findNode ($value, &$subtree) < // Если элемент не найден, возвращаем FALSE if (is_null($subtree)) < return FALSE; >// Для искомого значения меньшего, чем значение узла, продолжаем искать в левом поддереве if ($subtree->value > $value) < return $this->findNode($value, $subtree->left); > // Для искомого значения большего, чем значение узла, продолжаем искать в правом поддереве elseif ($subtree->value < $value) < return $this->findNode($value, $subtree->right); > // Если искомое значение равно значению узла, то возвращаем этот узел else < return $subtree; >>Приступим к реализации алгоритма удаления узла из дерева. Суть алгоритма такова:
- если у узла нет потомков (поддеревьев), то смело его удаляем;
- если есть один потомок (только правое или левое поддерево), то заменяем удаляемый узел потомком;
- если есть оба потомка, то:
- если у правого поддерева нет левого потомка, то заменяем удаляемый узел правым потомком, сохраняя левую ветвь удаляемого узла;
- если у правого поддерева есть левый потомок, то копируем его значение в удаляемый узел и рекурсивно удаляем.
Непосредственно метод удаления узла:
public function delete ($value) < // Выьрасываем исключение при попытке удаления элемента из пустого дерева if ($this->isEmpty()) < throw new UnderflowException('Tree is empty!'); >// Ищем нод в дереве $node = &$this->findNode($value, $this->root); // Если нод найден в дереве, то рекурсивно удаляем его if ($node) < $this->deleteNode($node); > return $this; > // Метод рекурсивного удаления, найденого нода из дерева protected function deleteNode (BinaryNode &$node) < // Если у узла нет потомков, удаляем его if (is_null($node->left) && is_null($node->right)) < $node = NULL; >// Если у узла нет левого поддерева, заменяем его правым поддеревом elseif (is_null($node->left)) < $node = $node->right; > // Если у узла нет правого поддерева, заменяем его левым поддеревом elseif (is_null($node->right)) < $node = $node->left; > // Если у узла есть оба потомка else < // Если у правого поддерева нет левого потомка, то заменяем удаляемый узел правым потомком, сохраняя левую ветвь удаляемого узла if (is_null($node->right->left)) < $node->right->left = $node->left; $node = $node->right; > // если у правого поддерева есть левый потомок, то копируем его значение в удаляемый узел и рекурсивно удаляем else < $node->value = $node->right->left->value; $this->deleteNode($node->right->left); > > >Бинарное дерево поиска готово.
P.S.: В листингах кода, я намеренно вырезал phpdoc-комментарии и не использовал пространства имен, чтобы их не загромождать.
Полные версии исходных кодов бинарного дерева поиска (а так же реализации еще нескольких структур данных, — одно/двухсвязные списков и стека/очереди, реализованных с помощью этих списков) можно посмотреть на githubе.Источник
PHP Binary Tree implementation
You can view it here. I’m using the Frank Mich jQuery Binary Tree plugin to display the data, but as I said before I believe I need a binary tree in order to display it correctly. If there’s a better way, or I’m just doing it wrong? What would the solution be?
Perhaps I should rephrase, the labels are incorrect even though I’m iterating through them in order. The bracket display itself is great.
The expected output would be each column is a round in order of 0 1 2 3, and the matches are displayed in order in each column.
Further research has led me to believe that I need a BST with in-order traversal. How to get my data in the BST properly is beyond me. I’ve built this array in accordance to en.wikipedia.org/wiki/Binary_tree array(4, 2, 6, 1, 3, 5, 7); This is with the number of matches lowered to 7 (4 participants).
2 Answers 2
This is the code for implementing binary tree(data structure) in php:
data = $data; $this->leftChild = null; $this->rightChild = null; > public function disp_data() < echo $this->data; > > class BinaryTree < public $root; public function __construct() < $this->root = null; > /** * function to display the tree */ public function display() < $this->display_tree($this->root); > public function display_tree($local_root) < if ($local_root == null) < return; >$this->display_tree($local_root->leftChild); echo $local_root->data."
"; $this->display_tree($local_root->rightChild); > /** * function to insert a new node */ public function insert($key) < $newnode = new Node($key); if ($this->root == null) < $this->root = $newnode; return; > else < $parent = $this->root; $current = $this->root; while (true) < $parent = $current; if ($key == ($this->find_order($key, $current->data))) < $current = $current->leftChild; if ($current == null) < $parent->leftChild = $newnode; return; >//end if2 > else < $current = $current->rightChild; if ($current == null) < $parent->rightChild = $newnode; return; > > > > > /** * function to search a particular Node */ public function find($key) < $current = $this->root; while ($current->data != $key) < if ($key == $this->find_order($key, $current->data)) < $current = $current->leftChild; > else < $current = $current->rightChild; > if ($current == null) < return (null); >> return ($current->data); > public function delete1($key) < $current = $this->root; $parent = $this->root; $isLeftChild = true; while ($current->data != $key) < $parent = $current; if ($key == ($this->find_order($key, $current->data))) < $current = $current->leftChild; $isLeftChild = true; > else < $current = $current->rightChild; $isLeftChild = false; > if ($current == null) < return (null); >> echo "
Node to delete:".$current->data; //to delete a leaf node if ($current->leftChild == null && $current->rightChild == null) < if ($current == $this->root) < $this->root = null; > else < if ($isLeftChild == true) < $parent->leftChild = null; > else < $parent->rightChild = null; > > return ($current); > else < //to delete a node having a leftChild if ($current->rightChild == null) < if ($current == $this->root) < $this->root = $current->leftChild; > else < if ($isLeftChild == true) < $parent->leftChild = $current->leftChild; > else < $parent->rightChild = $current->leftChild; > > return ($current); > else < //to delete a node having a rightChild if ($current->leftChild == null) < if ($current == $this->root) < $this->root = $current->rightChild; > else < if ($isLeftChild == true) < $parent->leftChild = $current->rightChild; > else < $parent->rightChild = $current->rightChild; > > return ($current); > else < //to delete a node having both childs $successor = $this->get_successor($current); if ($current == $this->root) < $this->root = $successor; > else < if ($isLeftChild == true) < $parent->leftChild = $successor; > else < $parent->rightChild = $successor; > > $successor->leftChild = $current->leftChild; return ($current); > > > > /** * Function to find the successor node */ public function get_successor($delNode) < $succParent = $delNode; $successor = $delNode; $temp = $delNode->rightChild; while ($temp != null) < $succParent = $successor; $successor = $temp; $temp = $temp->leftChild; > if ($successor != $delNode->rightChild) < $succParent->leftChild = $successor->rightChild; $successor->rightChild = $delNode->rightChild; > return ($successor); > /** * function to find the order of two strings */ public function find_order($str1, $str2) < $str1 = strtolower($str1); $str2 = strtolower($str2); $i = 0; $j = 0; $p1 = $str1[$i]; $p2 = $str2[$j]; while (true) < if (ord($p1) < ord($p2) || ($p1 == '' && $p2 == '')) < return ($str1); >else < if (ord($p1) == ord($p2)) < $p1 = $str1[++$i]; $p2 = $str2[++$j]; continue; >return ($str2); > > > public function is_empty() < return $this->root === null; > >You need to learn how to use the formatting tools in the editor so your code can display properly. See here.
Источник