En sucesor de orden en árbol de búsqueda binaria

Dado un nodo en una BST, ¿cómo se puede encontrar la siguiente clave más alta?

La forma general depende de si tienes un enlace principal en tus nodos o no.

Si almacena el enlace principal

Entonces eliges:

  1. El hijo más a la izquierda del hijo correcto, si su nodo actual tiene un hijo correcto. Si el niño correcto no tiene un hijo abandonado, el niño correcto es su sucesor inorder.
  2. Desplácese hacia arriba en los nodos padre antecesor, y cuando encuentre un padre cuyo hijo izquierdo es el nodo en el que se encuentra actualmente, el padre es el sucesor inorder de su nodo original.

Si tiene el hijo correcto, haga este enfoque (caso 1 anterior):

inorder-when-right-child

Si no tiene un hijo adecuado, haga este enfoque (caso 2 anterior):

inorder-when-no-right-child

Si no almacena el enlace principal

Luego debe ejecutar un escaneo completo del árbol, haciendo un seguimiento de los nodos, generalmente con una stack, para que tenga la información necesaria para básicamente hacer lo mismo que el primer método que se basó en el enlace principal.

Código de Python a la respuesta de Lasse:

 def findNext(node): if node.rightChild != None: return findMostLeft(node.rightChild) else: parent = node.parent while parent != None: if parent.leftChild == node: break node = parent parent = node.parent return parent 

Consulte aquí: sucesor de InOrder en un árbol de búsqueda binaria

En Binary Tree, el sucesor de Inorder de un nodo es el siguiente nodo en Inorder transversal del árbol binario. Inorder Successor es NULL para el último nodo en Inoorder transversal. En el Árbol de búsqueda binaria, el Sucesor de entrada de un nodo de entrada también se puede definir como el nodo con la clave más pequeña que la clave del nodo de entrada.

Aquí hay una implementación sin la necesidad de enlaces principales o estructuras intermedias (como una stack). Esta función sucesora en orden es un poco diferente de lo que podría estar buscando, ya que opera en la tecla en lugar de en el nodo. Además, encontrará un sucesor de una clave incluso si no está presente en el árbol. Sin embargo, no es difícil cambiarlo si es necesario.

 public class Node> { private T data; private Node left; private Node right; public Node(T data, Node left, Node right) { this.data = data; this.left = left; this.right = right; } /* * Returns the left-most node of the current node. If there is no left child, the current node is the left-most. */ private Node getLeftMost() { Node curr = this; while(curr.left != null) curr = curr.left; return curr; } /* * Returns the right-most node of the current node. If there is no right child, the current node is the right-most. */ private Node getRightMost() { Node curr = this; while(curr.right != null) curr = curr.right; return curr; } /** * Returns the in-order successor of the specified key. * @param key The key. * @return */ public T getSuccessor(T key) { Node curr = this; T successor = null; while(curr != null) { // If this.data < key, search to the right. if(curr.data.compareTo(key) < 0 && curr.right != null) { curr = curr.right; } // If this.data > key, search to the left. else if(curr.data.compareTo(key) > 0) { // If the right-most on the left side has bigger than the key, search left. if(curr.left != null && curr.left.getRightMost().data.compareTo(key) > 0) { curr = curr.left; } // If there's no left, or the right-most on the left branch is smaller than the key, we're at the successor. else { successor = curr.data; curr = null; } } // this.data == key... else { // so get the right-most data. if(curr.right != null) { successor = curr.right.getLeftMost().data; } // there is no successor. else { successor = null; } curr = null; } } return successor; } public static void main(String[] args) { Node one, three, five, seven, two, six, four; one = new Node(Integer.valueOf(1), null, null); three = new Node(Integer.valueOf(3), null, null); five = new Node(Integer.valueOf(5), null, null); seven = new Node(Integer.valueOf(7), null, null); two = new Node(Integer.valueOf(2), one, three); six = new Node(Integer.valueOf(6), five, seven); four = new Node(Integer.valueOf(4), two, six); Node head = four; for(int i = 0; i <= 7; i++) { System.out.println(head.getSuccessor(i)); } } } 

Con el árbol de búsqueda binaria, el algoritmo para encontrar el próximo nodo más alto de un nodo determinado es básicamente encontrar el nodo más bajo del subárbol correcto de ese nodo.

El algoritmo puede ser simplemente:

  1. Comience con el hijo correcto del nodo dado (conviértalo en el nodo actual temporal)
  2. Si el nodo actual no tiene hijo izquierdo, es el próximo nodo más alto.
  3. Si el nodo actual tiene un elemento secundario izquierdo, conviértalo en el nodo actual.

Repite 2 y 3 hasta que encontremos el próximo nodo más alto.

Solución C ++ suponiendo que los nodos tienen punteros izquierdo, derecho y padres:

Esto ilustra la función Node* getNextNodeInOrder(Node) que devuelve la siguiente clave del árbol de búsqueda binaria en orden.

 #include  #include  using namespace std; struct Node{ int data; Node *parent; Node *left, *right; }; Node *createNode(int data){ Node *node = new Node(); node->data = data; node->left = node->right = NULL; return node; } Node* getFirstRightParent(Node *node){ if (node->parent == NULL) return NULL; while (node->parent != NULL && node->parent->left != node){ node = node->parent; } return node->parent; } Node* getLeftMostRightChild(Node *node){ node = node->right; while (node->left != NULL){ node = node->left; } return node; } Node *getNextNodeInOrder(Node *node){ //if you pass in the last Node this will return NULL if (node->right != NULL) return getLeftMostRightChild(node); else return getFirstRightParent(node); } void inOrderPrint(Node *root) { if (root->left != NULL) inOrderPrint(root->left); cout << root->data << " "; if (root->right != NULL) inOrderPrint(root->right); } int main(int argc, char** argv) { //Purpose of this program is to demonstrate the function getNextNodeInOrder //of a binary tree in-order. Below the tree is listed with the order //of the items in-order. 1 is the beginning, 11 is the end. If you //pass in the node 4, getNextNode returns the node for 5, the next in the //sequence. //test tree: // // 4 // / \ // 2 11 // / \ / // 1 3 10 // / // 5 // \ // 6 // \ // 8 // / \ // 7 9 Node *root = createNode(4); root->parent = NULL; root->left = createNode(2); root->left->parent = root; root->right = createNode(11); root->right->parent = root; root->left->left = createNode(1); root->left->left->parent = root->left; root->right->left = createNode(10); root->right->left->parent = root->right; root->left->right = createNode(3); root->left->right->parent = root->left; root->right->left->left = createNode(5); root->right->left->left->parent = root->right->left; root->right->left->left->right = createNode(6); root->right->left->left->right->parent = root->right->left->left; root->right->left->left->right->right = createNode(8); root->right->left->left->right->right->parent = root->right->left->left->right; root->right->left->left->right->right->left = createNode(7); root->right->left->left->right->right->left->parent = root->right->left->left->right->right; root->right->left->left->right->right->right = createNode(9); root->right->left->left->right->right->right->parent = root->right->left->left->right->right; inOrderPrint(root); //UNIT TESTING FOLLOWS cout << endl << "unit tests: " << endl; if (getNextNodeInOrder(root)->data != 5) cout << "failed01" << endl; else cout << "passed01" << endl; if (getNextNodeInOrder(root->right) != NULL) cout << "failed02" << endl; else cout << "passed02" << endl; if (getNextNodeInOrder(root->right->left)->data != 11) cout << "failed03" << endl; else cout << "passed03" << endl; if (getNextNodeInOrder(root->left)->data != 3) cout << "failed04" << endl; else cout << "passed04" << endl; if (getNextNodeInOrder(root->left->left)->data != 2) cout << "failed05" << endl; else cout << "passed05" << endl; if (getNextNodeInOrder(root->left->right)->data != 4) cout << "failed06" << endl; else cout << "passed06" << endl; if (getNextNodeInOrder(root->right->left->left)->data != 6) cout << "failed07" << endl; else cout << "passed07" << endl; if (getNextNodeInOrder(root->right->left->left->right)->data != 7) cout << "failed08 it came up with: " << getNextNodeInOrder(root->right->left->left->right)->data << endl; else cout << "passed08" << endl; if (getNextNodeInOrder(root->right->left->left->right->right)->data != 9) cout << "failed09 it came up with: " << getNextNodeInOrder(root->right->left->left->right->right)->data << endl; else cout << "passed09" << endl; return 0; } 

Que impresiones:

 1 2 3 4 5 6 7 8 9 10 11 unit tests: passed01 passed02 passed03 passed04 passed05 passed06 passed07 passed08 passed09 

Si realizamos un cruce en orden, entonces visitamos el subárbol izquierdo, luego el nodo raíz y finalmente el subárbol derecho para cada nodo en el árbol. Realizar un recorrido en orden nos dará las claves de un árbol de búsqueda binaria en orden ascendente, por lo que cuando nos referimos a recuperar el sucesor en orden de un nodo perteneciente a un árbol de búsqueda binaria queremos decir cuál sería el siguiente nodo en la secuencia de el nodo dado.

Digamos que tenemos un nodo R y queremos su sucesor en orden tendremos los siguientes casos.

[1] La raíz R tiene un nodo derecho, por lo que todo lo que tenemos que hacer es atravesar el nodo más a la izquierda de R-> derecha.

[2] La raíz R no tiene ningún nodo derecho, en este caso cruzamos el árbol siguiendo los enlaces padres hasta que el nodo R es un elemento secundario izquierdo de su elemento primario, cuando esto ocurre, tenemos el nodo primario P como el sucesor sucesor .

[3] Estamos en el nodo extremo derecho del árbol, en este caso no hay un sucesor en orden.

La implementación se basa en la siguiente definición de nodo

 class node { private: node* left; node* right; node* parent int data; public: //public interface not shown, these are just setters and getters ....... }; //go up the tree until we have our root node a left child of its parent node* getParent(node* root) { if(root->parent == NULL) return NULL; if(root->parent->left == root) return root->parent; else return getParent(root->parent); } node* getLeftMostNode(node* root) { if(root == NULL) return NULL; node* left = getLeftMostNode(root->left); if(left) return left; return root; } //return the in order successor if there is one. //parameters - root, the node whose in order successor we are 'searching' for node* getInOrderSucc(node* root) { //no tree, therefore no successor if(root == NULL) return NULL; //if we have a right tree, get its left most node if(root->right) return getLeftMostNode(root->right); else //bubble up so the root node becomes the left child of its //parent, the parent will be the inorder successor. return getParent(root); } 

no necesitamos el enlace principal o la stack para encontrar el sucesor en orden en O (log n) (asumiendo el árbol balanceado). Mantenga una variable temporal con el valor más reciente encontrado en el cruce interno que sea más grande que la clave. si inorder transversal encuentra que el nodo no tiene un hijo derecho, entonces este sería el sucesor inorder. de lo contrario, el descendiente más a la izquierda del niño correcto.

Puede leer información adicional aquí (Rus lung)

 Node next(Node x) if x.right != null return minimum(x.right) y = x.parent while y != null and x == y.right x = y y = y.parent return y Node prev(Node x) if x.left != null return maximum(x.left) y = x.parent while y != null and x == y.left x = y y = y.parent return y 

Todas estas respuestas me parecen demasiado complicadas. Realmente no necesitamos punteros padres o cualquier estructura de datos auxiliar como una stack. Todo lo que tenemos que hacer es atravesar el árbol desde la raíz en orden, establecer un marcador tan pronto como encontremos el nodo objective, y el siguiente nodo en el árbol que visitamos será el nodo sucesor en orden. Aquí hay una rutina rápida y sucia que escribí.

 Node* FindNextInorderSuccessor(Node* root, int target, bool& done) { if (!root) return NULL; // go left Node* result = FindNextInorderSuccessor(root->left, target, done); if (result) return result; // visit if (done) { // flag is set, this must be our in-order successor node return root; } else { if (root->value == target) { // found target node, set flag so that we stop at next node done = true; } } // go right return FindNextInorderSuccessor(root->right, target, done); } 

Solución de JavaScript: si el nodo dado tiene un nodo derecho, devuelve el nodo más pequeño en el subárbol derecho. De lo contrario, hay 2 posibilidades: – El nodo dado es un elemento secundario izquierdo del nodo primario. Si es así, devuelve el nodo padre. De lo contrario, el nodo dado es un elemento secundario correcto del nodo principal. Si es así, devuelve el hijo correcto del nodo padre

 function nextNode(node) { var nextLargest = null; if (node.right != null) { // Return the smallest item in the right subtree nextLargest = node.right; while (nextLargest.left !== null) { nextLargest = nextLargest.left; } return nextLargest; } else { // Node is the left child of the parent if (node === node.parent.left) return node.parent; // Node is the right child of the parent nextLargest = node.parent; while (nextLargest.parent !== null && nextLargest !== nextLargest.parent.left) { nextLargest = nextLargest.parent } return nextLargest.parent; } } 

Haciendo esto en Java

 TreeNode getSuccessor(TreeNode treeNode) { if (treeNode.right != null) { return getLeftMostChild(treeNode.right); } else { TreeNode p = treeNode.parent; while (p != null && treeNode == p.right) { // traverse upwards until there is no parent (at the last node of BST and when current treeNode is still the parent's right child treeNode = p; p = p.parent; // traverse upwards } return p; // returns the parent node } } TreeNode getLeftMostChild(TreeNode treeNode) { if (treeNode.left == null) { return treeNode; } else { return getLeftMostChild(treeNode.left); } } 

Podemos dividir esto en 3 casos:

  1. Si el nodo es primario: en este caso, encontramos si tiene un nodo derecho y atraviesa el elemento secundario más a la izquierda del nodo derecho. En caso de que el nodo derecho no tenga hijos, entonces el nodo derecho es su sucesor inorden. Si no hay ningún nodo derecho, tenemos que movernos hacia arriba para encontrar el sucesor inorder.

  2. Si el nodo es un hijo izquierdo: en este caso, el padre es el sucesor inorder.

  3. Si el nodo (llámelo x) es un hijo derecho (de su padre inmediato): atravesamos el árbol hasta que encontramos un nodo cuyo subárbol izquierdo tiene x.

Caso extremo: si el nodo es el nodo de la esquina más a la derecha, no hay ningún sucesor en orden.

Cada “tutorial” que revisé en google y todas las respuestas en este hilo usa la siguiente lógica: ” Si el nodo no tiene un hijo derecho, entonces su sucesor en orden será uno de sus antepasados. Usando el enlace padre, siga viajando hasta obtienes el nodo que es el hijo izquierdo de su padre. Entonces este nodo padre será el sucesor en orden.

Esto es lo mismo que pensar ” si mi padre es más grande que yo, entonces yo soy el hijo de la izquierda ” (propiedad de un árbol de búsqueda binario). Esto significa que simplemente puede subir la cadena principal hasta que la propiedad anterior sea verdadera. Lo cual en mi opinión resulta en un código más elegante.

Supongo que la razón por la que todo el mundo está comprobando “¿ soy el hijo de la izquierda ” al buscar sucursales en lugar de valores en la ruta del código que utiliza enlaces principales proviene de la lógica de “préstamo” del algoritmo de no enlace a padre.

También a partir del código incluido a continuación podemos ver que no hay necesidad de estructura de datos de stack como lo sugieren otras respuestas.

A continuación se muestra una función simple de C ++ que funciona para ambos casos de uso (con y sin utilizar el enlace para el elemento principal).

 Node* nextInOrder(const Node *node, bool useParentLink) const { if (!node) return nullptr; // when has a right sub-tree if (node->right) { // get left-most node from the right sub-tree node = node->right; while (node->left) node = node->left; return node; } // when does not have a right sub-tree if (useParentLink) { Node *parent = node->parent; while (parent) { if (parent->value > node->value) return parent; parent = parent->parent; } return nullptr; } else { Node *nextInOrder = nullptr; // 'root' is a class member pointing to the root of the tree Node *current = root; while (current != node) { if (node->value < current->value) { nextInOrder = current; current = current->left; } else { current = current->right; } } return nextInOrder; } } Node* previousInOrder(const Node *node, bool useParentLink) const { if (!node) return nullptr; // when has a left sub-tree if (node->left) { // get right-most node from the left sub-tree node = node->left; while (node->right) node = node->right; return node; } // when does not have a left sub-tree if (useParentLink) { Node *parent = node->parent; while (parent) { if (parent->value < node->value) return parent; parent = parent->parent; } return nullptr; } else { Node *prevInOrder = nullptr; // 'root' is a class member pointing to the root of the tree Node *current = root; while (current != node) { if (node->value < current->value) { current = current->left; } else { prevInOrder = current; current = current->right; } } return prevInOrder; } } 

Implementación C # (¡no recursiva!) Para encontrar el ‘siguiente’ nodo de un nodo dado en un árbol binario de búsqueda donde cada nodo tiene un enlace a su padre.

  public static Node WhoIsNextInOrder(Node root, Node node) { if (node.Right != null) { return GetLeftMost(node.Right); } else { Node p = new Node(null,null,-1); Node Next = new Node(null, null, -1); bool found = false; p = FindParent(root, node); while (found == false) { if (p.Left == node) { Next = p; return Next; } node = p; p = FindParent(root, node); } return Next; } } public static Node FindParent(Node root, Node node) { if (root == null || node == null) { return null; } else if ( (root.Right != null && root.Right.Value == node.Value) || (root.Left != null && root.Left.Value == node.Value)) { return root; } else { Node found = FindParent(root.Right, node); if (found == null) { found = FindParent(root.Left, node); } return found; } } public static Node GetLeftMost (Node node) { if (node.Left == null) { return node; } return GetLeftMost(node.Left); } 

Podemos encontrar el sucesor en O (log n) sin utilizar punteros padres (para un árbol equilibrado).

La idea es muy similar a cuando tienes punteros de padres.

Podemos definir una función recursiva que logre esto de la siguiente manera:

  • Si el nodo actual es el objective, devuelve el nodo más a la izquierda o el más pequeño de su subárbol derecho, si existe.
  • Recurse a la izquierda si el objective es más pequeño que el nodo actual, y a la derecha si es mayor.
  • Si el objective está a la izquierda y aún no hemos encontrado un sucesor, devuelva el nodo actual.

Pseudo-código:

 Key successor(Node current, Key target): if current == null return null if target == current.key if current.right != null return leftMost(current.right).key else return specialKey else if target < current.key s = successor(current.left, target) if s == specialKey return current.key else return s else return successor(current.right, target) Node leftMost(Node current): while current.left != null current = current.left return current 

Demostración en vivo de Java .