luckydenis · luckydenis · Mar 12, 2021 · Mar 12, 2021
diff --git a/README.md b/README.md
@@ -43,7 +43,9 @@
 * [Система непересекающихся множеств](./notes/ru/structure/union_find.md)
 * [Дерево отрезков](./notes/ru/structure/segment_tree.md)
 * [Префиксный массив сумм](./notes/ru/structure/prefix_sum_array.md)
-* [Двоичная куча (min)](notes/ru/structure/binary_heap_min.md)
+* [Двоичная куча (min)](./notes/ru/structure/binary_heap_min.md)
+* [Бинарное дерево поиска](./notes/ru/structure/binary_search_tree.md)
+* [Декартовое дерево](./notes/ru/structure/treap.md)
 
 #### Алгоритмы на последовательностях
 * [Поиск подмассива с максимальной суммой. Алгоритм Джея Кадане](./notes/ru/sequentia/maximum_subarray_problem.md)

diff --git a/notes/ru/graph/lca.md b/notes/ru/graph/lca.md
@@ -20,53 +20,29 @@ _LCA_ от англ. _lowest (least) common ancestor_.
 |O(n log n)   |O(log n)|
 
 ```python
-
-class Node:
-    def __init__(self, data):
-        self.data = data
-        self.left = None
-        self.right = None
-
-
-bin_tree_root = Node(1)
-bin_tree_root.left = Node(2)
-bin_tree_root.left.left = Node(3)
-bin_tree_root.left.left.left = Node(5)
-bin_tree_root.left.right = Node(4)
-bin_tree_root.right = Node(6)
-bin_tree_root.right.left = Node(7)
-bin_tree_root.right.right = Node(8)
-bin_tree_root.right.right.left = Node(9)
-
-
-def dfs(start):
+def dfs(graph, start):
     stack = [start]
-    dist = dict()
-    parent = dict()
-    dist[start.data] = 0
-    parent[start.data] = start.data
+    dist = dict().fromkeys(graph, -1)
+    parent = dict().fromkeys(graph, -1)
+    dist[start] = 0
+    parent[start] = start
     n = 0
     max_h = 0
     while stack:
         n += 1
         v = stack.pop()
-        if max_h < dist[v.data]:
-            max_h = dist[v.data]
-
-        if v.left:
-            stack.append(v.left)
-            dist[v.left.data] = dist[v.data] + 1
-            parent[v.left.data] = v.data
-        if v.right:
-            stack.append(v.right)
-            dist[v.right.data] = dist[v.data] + 1
-            parent[v.right.data] = v.data
+        if max_h < dist[v]:
+            max_h = dist[v]
+        for u in graph[v]:
+            stack.append(u)
+            dist[u] = dist[v] + 1
+            parent[u] = v
 
     return parent, dist, n, max_h
 
 
-def preprocess(root):
-    p, d, n, max_h = dfs(root)
+def preprocess(graph, start):
+    p, d, n, max_h = dfs(graph, start)
 
     dp = dict()
     for i in range(1, n + 1):
@@ -100,5 +76,25 @@ def lca(v, u, dp, d, p, max_h):
     return p[v]
 
 
-print(lca(5, 4, *preprocess(bin_tree_root))) # 2
+def main():
+    g = {
+        1: [2, 6],
+        2: [3, 4],
+        3: [5],
+        4: [],
+        5: [],
+        6: [7, 8, 9],
+        7: [],
+        8: [10],
+        9: [],
+        10: []
+    }
+    dp, d, p, max_h = preprocess(g, 1)
+
+    queries = [(5, 4), (7, 9), (5, 10)]
+    for v, u in queries:
+        print(lca(v, u, dp, d, p, max_h)) # 2, 6, 1
+
+
+main()
 ```
diff --git a/notes/ru/structure/binary_search_tree.md b/notes/ru/structure/binary_search_tree.md
@@ -0,0 +1,185 @@
+Бинарное дерево поиска
+-------------
+| [Главная](../../../README.md#Список-алгоритмов-[russian])
+| [Структуры данных](../../../README.md#Структуры-данных)
+|
+
+> **Бинарное дерево поиска** (англ. _binary search tree_, _BST_) — 
+структура данных для работы с упорядоченными множествами. Бинарное 
+дерево поиска обладает следующим свойством: 
+если x — узел бинарного дерева с ключом k, 
+то все узлы в левом поддереве должны иметь ключи, меньшие k, 
+а в правом поддереве большие k.
+
+
+
+Реализация
+----------
+* #### Без рекурсии
+|Время (insert)|Время (search)|Время (delete) |Время (search_parent)|Время (search_min)|Время (search_max)|
+|:------------:|:------------:|:-------------:|:-------------------:|:----------------:|:----------------:|
+|O(log n)      |O(log n)      |O(log n)       |O(log n)             |O(log n)          |O(log n)          |
+```python
+class Node:
+    def __init__(self, value, left=None, right=None):
+        self.value = value
+        self.left = left
+        self.right = right
+
+
+def insert(node, value):
+    if not node:
+        return Node(value)
+
+    current = node
+    while current:
+        if current.value < value:
+            if not current.right:
+                current.right = Node(value)
+                return node
+            current = current.right
+        else:
+            if not current.left:
+                current.left = Node(value)
+                return node
+            current = current.left
+
+
+def search(node, value, fail_value=-1):
+    current = node
+    while current:
+        if current.value == value:
+            return current
+        if current.value < value:
+            current = current.right
+        else:
+            current = current.left
+    return Node(fail_value)
+
+
+def search_min(node):
+    current = node
+    while current.left:
+        current = current.left
+    return current
+
+
+def search_max(node):
+    current = node
+    while current.right:
+        current = current.right
+    return current
+
+
+def search_parent(node, value, fail_value=-1):
+    current = node
+    fail_node = Node(fail_value)
+    successes = fail_node
+    while current:
+        if current.value == value:
+            return successes
+
+        successes = current
+        if current.value < value:
+            current = current.right
+        else:
+            current = current.left
+
+    return fail_node
+
+
+def delete_node_has_not_children(p, d):
+    if d.left or d.right:
+        return False
+
+    if p.left is d:
+        p.left = None
+
+    if p.right is d:
+        p.right = None
+    return True
+
+
+def delete_node_has_one_child(p, d):
+    if d.left and d.right:
+        return False
+    if not d.left and not d.right:
+        return False
+
+    if not d.left:
+        if p.left is d:
+            p.left = d.right
+        else:
+            p.right = d.right
+    else:
+        if p.left is d:
+            p.left = d.left
+        else:
+            p.right = d.left
+    return True
+
+
+def delete_node_has_two_children(d):
+    if not d.left and not d.right:
+        return False
+    if d.left and not d.right:
+        return False
+    if d.right and not d.left:
+        return False
+
+    current = d.right
+    current_p = d
+    while current.left:
+        current_p = current
+        current = current.left
+
+    d.value = current.value
+    if delete_node_has_not_children(current_p, current):
+        return True
+    if delete_node_has_one_child(current_p, current):
+        return True
+    return False
+
+
+def delete(node, d):
+    p = search_parent(node, d.value)
+
+    if delete_node_has_not_children(p, d):
+        return True
+    if delete_node_has_one_child(p, d):
+        return True
+    if delete_node_has_two_children(d):
+        return True
+    return False
+
+
+root = insert(None, 8)
+insert(root, 3)
+insert(root, 1)
+insert(root, 6)
+insert(root, 4)
+insert(root, 7)
+insert(root, 10)
+insert(root, 14)
+insert(root, 13)
+
+
+parent = search_parent(root, 7) # 6
+print(parent.value)
+parent = search_parent(root, 8) # -1
+print(parent.value)
+parent = search_parent(root, 23) # -1
+print(parent.value)
+
+min_node = search_min(root)
+print(min_node.value) # 1
+max_node = search_max(root)
+print(max_node.value) # 14
+
+find_node = search(root, 7)
+print(find_node.value) # 7
+
+not_find_node = search(root, 23) 
+print(not_find_node.value) # -1
+delete(root, search(root, 8))
+```
diff --git a/notes/ru/structure/segment_tree.md b/notes/ru/structure/segment_tree.md
@@ -78,5 +78,4 @@ print(segment_tree.tree)  # [42, 20, 22, 7, 13, 12, 10, 5, 2, 6, 7, 8, 4, 4, 6,
 segment_tree.set(1, 100)
 print(segment_tree.tree)  # [140, 118, 22, 105, 13, 12, 10, 5, 100, 6, 7, 8, 4, 4, 6, 9]
 print(segment_tree.query_sum(2, 8))  # 35
-
 ```