algorithm
Деревья двоичного поиска

Вступление

Дерево двоичного поиска - Вставка (Python)

Это простая реализация вставки двоичного дерева поиска с использованием Python.

Пример показан ниже:

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

class Node:
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.data = val

def insert(root, node):
    if root is None:
        root = node
    else:
        if root.data > node.data:
            if root.l_child is None:
                root.l_child = node
            else:
                insert(root.l_child, node)
        else:
            if root.r_child is None:
                root.r_child = node
            else:
                insert(root.r_child, node)

def in_order_print(root):
    if not root:
        return
    in_order_print(root.l_child)
    print root.data
    in_order_print(root.r_child)

def pre_order_print(root):
    if not root:
        return        
    print root.data
    pre_order_print(root.l_child)
    pre_order_print(root.r_child)    

Двоичное дерево поиска - удаление (C ++)

Прежде чем начать с удаления, я просто хочу поместить некоторые огни на то, что является бинарным деревом поиска (BST). Каждый узел в BST может иметь максимум два узла (левый и правый дочерние элементы). Левое поддерево узла имеет ключ меньше или равен ключу его родительского узла. В правом поддереве узла есть ключ, который больше, чем ключ его родительского узла.

Удаление узла в дереве при сохранении его свойства двоичного дерева поиска.

При удалении узла необходимо учитывать три случая.

• Случай 1: Узел, подлежащий удалению, является листовым узлом (Узел со значением 22).
• Случай 2: Узел, который нужно удалить, имеет один ребенок. (Узел со значением 26).
• Случай 3: Узел, который нужно удалить, имеет обоих детей. (Узел со значением 49).

Объяснение случаев:

1. Когда удаляемый узел является листовым узлом, просто удалите узел и передайте nullptr в его родительский узел.
2. Когда удаляемый узел имеет только один дочерний элемент, затем копируйте дочернее значение в значение узла и удалите дочерний элемент (преобразованный в случай 1)
3. Когда узел, который должен быть удален, имеет два дочерних элемента, то минимальный из его правого поддерева может быть скопирован в узел, а затем минимальное значение может быть удалено из правого поддерева узла (преобразовано в случай 2)

Примечание . Минимальное значение в правом подэлементе может содержать максимум один ребенок, а слишком правильный ребенок, если он имеет левый дочерний элемент, означает, что это не минимальное значение или оно не соответствует свойству BST.

Структура узла в дереве и код для удаления:

struct node
{
    int data;
    node *left, *right;
};

node* delete_node(node *root, int data)
{
  if(root == nullptr) return root;
  else if(data < root->data) root->left  = delete_node(root->left, data);
  else if(data > root->data) root->right = delete_node(root->right, data);

  else
  {
    if(root->left == nullptr && root->right == nullptr) // Case 1
    {
      free(root);
      root = nullptr;
    }
    else if(root->left == nullptr)       // Case 2
    {
       node* temp = root;
       root= root->right;
       free(temp);
    }
    else if(root->right == nullptr)      // Case 2
    {
       node* temp = root;
       root = root->left;
       free(temp);
    }
    else                                 // Case 3
    {
       node* temp = root->right;

       while(temp->left != nullptr) temp = temp->left;

       root->data = temp->data;
       root->right = delete_node(root->right, temp->data);
    }
  }
  return root;
}

Сложность времени выше кода равна O ( h ), где h - высота дерева.

Самый низкий общий предок в BST

Рассмотрим BST:

Самый низкий общий предок 22 и 26 составляет 24

Самый низкий общий предок 26 и 49 составляет 46

Самый низкий общий предок 22 и 24 составляет 24

Свойство дерева двоичного поиска может использоваться для нахождения узлов нижнего предка

Код Псевдоэ:

lowestCommonAncestor(root,node1, node2){

if(root == NULL)    
return NULL;



 else if(node1->data == root->data || node2->data== root->data)    
    return root;
    
    else if((node1->data <= root->data && node2->data > root->data)
              || (node2->data <= root->data && node1->data > root->data)){
        
             return root;
    }
    
    else if(root->data > max(node1->data,node2->data)){
            return lowestCommonAncestor(root->left, node1, node2);
    }
        
        else {
            return lowestCommonAncestor(root->right, node1, node2);
      }
        }

Дерево двоичного поиска - Python

class Node(object):
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.val = val


class BinarySearchTree(object):
    def insert(self, root, node):
        if root is None:
            return node

        if root.val < node.val:
            root.r_child = self.insert(root.r_child, node)
        else:
            root.l_child = self.insert(root.l_child, node)

        return root


    def in_order_place(self, root):
        if not root:
            return None
        else:
            self.in_order_place(root.l_child)
            print root.val
            self.in_order_place(root.r_child)

    def pre_order_place(self, root):
        if not root:
            return None
        else:
            print root.val
            self.pre_order_place(root.l_child)
            self.pre_order_place(root.r_child)

    def post_order_place(self, root):
        if not root:
            return None
        else:
            self.post_order_place(root.l_child)
            self.post_order_place(root.r_child)
            print root.val

"" Создать другой узел и вставить в него данные "" "

r = Node(3)
node = BinarySearchTree()
nodeList = [1, 8, 5, 12, 14, 6, 15, 7, 16, 8]

for nd in nodeList:
    node.insert(r, Node(nd))

print "------In order ---------"
print (node.in_order_place(r))
print "------Pre order ---------"
print (node.pre_order_place(r))
print "------Post order ---------"
print (node.post_order_place(r))