Двоичные деревья поиска. Декартово дерево
Декартово дерево — это двоичное дерево, в узлах которого хранятся: ссылки на правое и левое поддерево, ссылка на родительский узел (необязательно), ключи x и y, которые являются двоичным деревом поиска по ключу x и двоичной кучей по ключу y. А именно, для любого узла дерева n ключи x узлов правого (левого) поддерева больше (меньше либо равны) ключа x узла n, ключи y узлов правого и левого детей меньше либо равны ключу y узла n.
Ссылка на родительский узел не обязательна, она желательна только для линейного алгоритма построения дерева.
Декартово дерево - это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: treap (tree+heap) и дерамида (дерево+пирамида).
type
Treap = ^TNode;
TNode = record
x,y : Integer; { x - ключ, y - приоритет (произвольные сравнимые типы данных) }
Left,Right : Treap; { Левое и правое поддерево }
end;
Merge (склеивание)
{ Слияние декартовых деревьев }
function Merge( L,R : Treap ):Treap;
begin
if L = nil then { Левого поддерева нет }
Result := R { => результат - правое поддерево }
else if R = nil then { Правого поддерева нет }
Result := L { => результат - левое поддерево }
else if L.y > R.y then begin { У левого приоритет выше }
{ => левое становится корнем }
{ Левое поддерево у него сохраняется }
L.Right := Merge(L.Right,R);
Result := L;
end else begin { У правого приоритет выше или равен }
{ Правое поддерево сохраняется }
{ Левое поддерево = результат слияния левого с
левым сыном правого поддерева }
R.Left := Merge(L,R.Left);
Result := R;
end;
end;
Реализация на Python
# Склеивание декартовых деревьев (merge): O(log n) в среднем, где n - число вершин.
class Node:
def __init__(self, key, prio):
self.key = key
self.prio = prio # приоритет: у родителя он не меньше, чем у детей (куча)
self.left = None
self.right = None
def merge(left, right):
# Все ключи left не больше ключей right; корнем становится вершина с большим приоритетом
if left is None:
return right
if right is None:
return left
if left.prio > right.prio:
left.right = merge(left.right, right)
return left
right.left = merge(left, right.left)
return right
def keys_in_order(node, keys):
# Обход по возрастанию ключей
if node is None:
return
keys_in_order(node.left, keys)
keys.append(node.key)
keys_in_order(node.right, keys)
def main():
# Склеиваем одиночные вершины в порядке возрастания ключей
root = None
for key, prio in [(1, 30), (2, 50), (3, 10), (4, 40)]:
root = merge(root, Node(key, prio))
keys = []
keys_in_order(root, keys)
print(keys, root.key) # [1, 2, 3, 4] 2
if __name__ == "__main__":
main()
Реализация на Rust
// Склеивание декартовых деревьев (merge): O(log n) в среднем, где n - число вершин.
pub struct Node {
pub key: i32,
pub prio: i32, // приоритет: у родителя он не меньше, чем у детей (куча)
pub left: Tree,
pub right: Tree,
}
pub type Tree = Option<Box<Node>>;
// Все ключи left не больше ключей right; корнем становится вершина с большим приоритетом.
pub fn merge(left: Tree, right: Tree) -> Tree {
match (left, right) {
(None, right) => right,
(left, None) => left,
(Some(mut l), Some(mut r)) => {
if l.prio > r.prio {
l.right = merge(l.right.take(), Some(r));
Some(l)
} else {
r.left = merge(Some(l), r.left.take());
Some(r)
}
}
}
}
// Обход по возрастанию ключей.
pub fn keys_in_order(node: &Tree, keys: &mut Vec<i32>) {
if let Some(current) = node {
keys_in_order(¤t.left, keys);
keys.push(current.key);
keys_in_order(¤t.right, keys);
}
}
fn main() {
// Склеиваем одиночные вершины в порядке возрастания ключей
let mut root: Tree = None;
for (key, prio) in [(1, 30), (2, 50), (3, 10), (4, 40)] {
root = merge(root, Some(Box::new(Node { key, prio, left: None, right: None })));
}
let mut keys = Vec::new();
keys_in_order(&root, &mut keys);
println!("{:?} {}", keys, root.as_ref().map_or(0, |n| n.key)); // [1, 2, 3, 4] 2
}Реализация на C++
// Склеивание декартовых деревьев (merge): O(log n) в среднем, где n - число вершин.
#include <iostream>
#include <memory>
#include <utility>
#include <vector>
struct Node {
int key;
int prio; // приоритет: у родителя он не меньше, чем у детей (куча)
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
Node(int k, int p) : key(k), prio(p) {}
};
using Tree = std::unique_ptr<Node>;
// Все ключи left не больше ключей right; корнем становится вершина с большим приоритетом.
Tree merge(Tree left, Tree right) {
if (!left) return right;
if (!right) return left;
if (left->prio > right->prio) {
left->right = merge(std::move(left->right), std::move(right));
return left;
}
right->left = merge(std::move(left), std::move(right->left));
return right;
}
// Обход по возрастанию ключей.
void keys_in_order(const Node* node, std::vector<int>& keys) {
if (!node) return;
keys_in_order(node->left.get(), keys);
keys.push_back(node->key);
keys_in_order(node->right.get(), keys);
}
int main() {
// Склеиваем одиночные вершины в порядке возрастания ключей
Tree root;
for (auto [key, prio] : {std::pair{1, 30}, std::pair{2, 50}, std::pair{3, 10}, std::pair{4, 40}}) {
root = merge(std::move(root), std::make_unique<Node>(key, prio));
}
std::vector<int> keys;
keys_in_order(root.get(), keys);
for (int key : keys) std::cout << key << ' ';
std::cout << "корень " << root->key << '\n'; // 1 2 3 4 корень 2
return 0;
}
Split (разрезание)
{ Операция разрезания дерева T по ключу x на 2 поддерева L и R }
procedure Split( T:Treap; x:Integer; var L,R:Treap);
var Temp : Treap; { Временное дерево }
begin
Temp := nil;
if T = nil then begin { Если дерево пустое }
L := nil; { то результат разрезания пустой }
R := nil;
end else
if T.x <= x then begin
if T.Right = nil then
R := nil
else
Split(T.Right,x,Temp,R);
L := T;
L.Right := Temp;
end else begin
if T.Left = nil then
L := nil
else
Split(T.Left,x,L,Temp);
R := T;
R.Left := Temp;
end;
end;
Реализация на Python
# Разрезание декартова дерева по ключу (split): O(log n) в среднем, где n - число вершин.
class Node:
def __init__(self, key, prio):
self.key = key
self.prio = prio # приоритет: у родителя он не меньше, чем у детей (куча)
self.left = None
self.right = None
def merge(left, right):
if left is None:
return right
if right is None:
return left
if left.prio > right.prio:
left.right = merge(left.right, right)
return left
right.left = merge(left, right.left)
return right
def split(node, split_key):
# Возвращает (left, right): в left ключи <= split_key, в right - остальные
if node is None:
return None, None
if node.key <= split_key:
left, right = split(node.right, split_key)
node.right = left
return node, right
left, right = split(node.left, split_key)
node.left = right
return left, node
def keys_in_order(node, keys):
if node is None:
return
keys_in_order(node.left, keys)
keys.append(node.key)
keys_in_order(node.right, keys)
def main():
root = None
for key, prio in [(1, 30), (2, 50), (3, 10), (4, 40), (5, 20)]:
root = merge(root, Node(key, prio))
left, right = split(root, 3)
left_keys, right_keys = [], []
keys_in_order(left, left_keys)
keys_in_order(right, right_keys)
print(left_keys, right_keys) # [1, 2, 3] [4, 5]
if __name__ == "__main__":
main()
Реализация на Rust
// Разрезание декартова дерева по ключу (split): O(log n) в среднем, где n - число вершин.
pub struct Node {
pub key: i32,
pub prio: i32, // приоритет: у родителя он не меньше, чем у детей (куча)
pub left: Tree,
pub right: Tree,
}
pub type Tree = Option<Box<Node>>;
pub fn merge(left: Tree, right: Tree) -> Tree {
match (left, right) {
(None, right) => right,
(left, None) => left,
(Some(mut l), Some(mut r)) => {
if l.prio > r.prio {
l.right = merge(l.right.take(), Some(r));
Some(l)
} else {
r.left = merge(Some(l), r.left.take());
Some(r)
}
}
}
}
// Возвращает (left, right): в left ключи <= split_key, в right - остальные.
pub fn split(node: Tree, split_key: i32) -> (Tree, Tree) {
let Some(mut current) = node else { return (None, None) };
if current.key <= split_key {
let (left, right) = split(current.right.take(), split_key);
current.right = left;
(Some(current), right)
} else {
let (left, right) = split(current.left.take(), split_key);
current.left = right;
(left, Some(current))
}
}
pub fn keys_in_order(node: &Tree, keys: &mut Vec<i32>) {
if let Some(current) = node {
keys_in_order(¤t.left, keys);
keys.push(current.key);
keys_in_order(¤t.right, keys);
}
}
fn main() {
let mut root: Tree = None;
for (key, prio) in [(1, 30), (2, 50), (3, 10), (4, 40), (5, 20)] {
root = merge(root, Some(Box::new(Node { key, prio, left: None, right: None })));
}
let (left, right) = split(root, 3);
let mut left_keys = Vec::new();
keys_in_order(&left, &mut left_keys);
let mut right_keys = Vec::new();
keys_in_order(&right, &mut right_keys);
println!("{:?} {:?}", left_keys, right_keys); // [1, 2, 3] [4, 5]
}Реализация на C++
// Разрезание декартова дерева по ключу (split): O(log n) в среднем, где n - число вершин.
#include <iostream>
#include <memory>
#include <utility>
#include <vector>
struct Node {
int key;
int prio; // приоритет: у родителя он не меньше, чем у детей (куча)
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
Node(int k, int p) : key(k), prio(p) {}
};
using Tree = std::unique_ptr<Node>;
Tree merge(Tree left, Tree right) {
if (!left) return right;
if (!right) return left;
if (left->prio > right->prio) {
left->right = merge(std::move(left->right), std::move(right));
return left;
}
right->left = merge(std::move(left), std::move(right->left));
return right;
}
// Возвращает пару (left, right): в left ключи <= split_key, в right - остальные.
std::pair<Tree, Tree> split(Tree node, int split_key) {
if (!node) return {nullptr, nullptr};
if (node->key <= split_key) {
auto [left, right] = split(std::move(node->right), split_key);
node->right = std::move(left);
return {std::move(node), std::move(right)};
}
auto [left, right] = split(std::move(node->left), split_key);
node->left = std::move(right);
return {std::move(left), std::move(node)};
}
void keys_in_order(const Node* node, std::vector<int>& keys) {
if (!node) return;
keys_in_order(node->left.get(), keys);
keys.push_back(node->key);
keys_in_order(node->right.get(), keys);
}
int main() {
Tree root;
for (auto [key, prio] : {std::pair{1, 30}, std::pair{2, 50}, std::pair{3, 10}, std::pair{4, 40}, std::pair{5, 20}}) {
root = merge(std::move(root), std::make_unique<Node>(key, prio));
}
auto [left, right] = split(std::move(root), 3);
std::vector<int> left_keys, right_keys;
keys_in_order(left.get(), left_keys);
keys_in_order(right.get(), right_keys);
for (int key : left_keys) std::cout << key << ' ';
std::cout << "| ";
for (int key : right_keys) std::cout << key << ' ';
std::cout << '\n'; // 1 2 3 | 4 5
return 0;
}
Добавление новой вершины
{ Добавление вершины с ключём x в дерево T }
procedure Add( var T:Treap; x:integer );
var NV,L,R : Treap;
begin
new(NV); { Создаём новый узел }
NV.x := x; { У него ключ x }
NV.y := Random(High(Integer)); { И случайный приоритет }
NV.Left := nil; { Нет поддеревьев }
NV.Right := nil;
Split(T,x,L,R); { Разрезаем исходное дерево по ключу x }
{ Склеиваем 3 получившихся дерева }
T := Merge(Merge(L,NV),R);
end;
Реализация на Python
# Вставка в декартово дерево через разрезание и склеивание: O(log n) в среднем.
class Node:
def __init__(self, key, prio):
self.key = key
self.prio = prio # приоритет: у родителя он не меньше, чем у детей (куча)
self.left = None
self.right = None
def merge(left, right):
if left is None:
return right
if right is None:
return left
if left.prio > right.prio:
left.right = merge(left.right, right)
return left
right.left = merge(left, right.left)
return right
def split(node, split_key):
# Возвращает (left, right): в left ключи <= split_key, в right - остальные
if node is None:
return None, None
if node.key <= split_key:
left, right = split(node.right, split_key)
node.right = left
return node, right
left, right = split(node.left, split_key)
node.left = right
return left, node
def insert(root, key, prio):
# Разрезаем дерево по ключу и склеиваем: левая часть, новая вершина, правая часть
left, right = split(root, key)
return merge(merge(left, Node(key, prio)), right)
def keys_in_order(node, keys):
if node is None:
return
keys_in_order(node.left, keys)
keys.append(node.key)
keys_in_order(node.right, keys)
def main():
root = None
for key, prio in [(5, 50), (3, 80), (8, 20), (1, 90), (4, 10)]:
root = insert(root, key, prio)
keys = []
keys_in_order(root, keys)
print(keys, root.key) # [1, 3, 4, 5, 8] 1
if __name__ == "__main__":
main()
Реализация на Rust
// Вставка в декартово дерево через разрезание и склеивание: O(log n) в среднем.
pub struct Node {
pub key: i32,
pub prio: i32, // приоритет: у родителя он не меньше, чем у детей (куча)
pub left: Tree,
pub right: Tree,
}
pub type Tree = Option<Box<Node>>;
pub fn merge(left: Tree, right: Tree) -> Tree {
match (left, right) {
(None, right) => right,
(left, None) => left,
(Some(mut l), Some(mut r)) => {
if l.prio > r.prio {
l.right = merge(l.right.take(), Some(r));
Some(l)
} else {
r.left = merge(Some(l), r.left.take());
Some(r)
}
}
}
}
// Возвращает (left, right): в left ключи <= split_key, в right - остальные.
pub fn split(node: Tree, split_key: i32) -> (Tree, Tree) {
let Some(mut current) = node else { return (None, None) };
if current.key <= split_key {
let (left, right) = split(current.right.take(), split_key);
current.right = left;
(Some(current), right)
} else {
let (left, right) = split(current.left.take(), split_key);
current.left = right;
(left, Some(current))
}
}
// Разрезаем дерево по ключу и склеиваем: левая часть, новая вершина, правая часть.
pub fn insert(root: Tree, key: i32, prio: i32) -> Tree {
let (left, right) = split(root, key);
merge(merge(left, Some(Box::new(Node { key, prio, left: None, right: None }))), right)
}
pub fn keys_in_order(node: &Tree, keys: &mut Vec<i32>) {
if let Some(current) = node {
keys_in_order(¤t.left, keys);
keys.push(current.key);
keys_in_order(¤t.right, keys);
}
}
fn main() {
let mut root: Tree = None;
for (key, prio) in [(5, 50), (3, 80), (8, 20), (1, 90), (4, 10)] {
root = insert(root, key, prio);
}
let mut keys = Vec::new();
keys_in_order(&root, &mut keys);
println!("{:?} {}", keys, root.as_ref().map_or(0, |n| n.key)); // [1, 3, 4, 5, 8] 1
}Реализация на C++
// Вставка в декартово дерево через разрезание и склеивание: O(log n) в среднем.
#include <iostream>
#include <memory>
#include <utility>
#include <vector>
struct Node {
int key;
int prio; // приоритет: у родителя он не меньше, чем у детей (куча)
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
Node(int k, int p) : key(k), prio(p) {}
};
using Tree = std::unique_ptr<Node>;
Tree merge(Tree left, Tree right) {
if (!left) return right;
if (!right) return left;
if (left->prio > right->prio) {
left->right = merge(std::move(left->right), std::move(right));
return left;
}
right->left = merge(std::move(left), std::move(right->left));
return right;
}
// Возвращает пару (left, right): в left ключи <= split_key, в right - остальные.
std::pair<Tree, Tree> split(Tree node, int split_key) {
if (!node) return {nullptr, nullptr};
if (node->key <= split_key) {
auto [left, right] = split(std::move(node->right), split_key);
node->right = std::move(left);
return {std::move(node), std::move(right)};
}
auto [left, right] = split(std::move(node->left), split_key);
node->left = std::move(right);
return {std::move(left), std::move(node)};
}
// Разрезаем дерево по ключу и склеиваем: левая часть, новая вершина, правая часть.
Tree insert(Tree root, int key, int prio) {
auto [left, right] = split(std::move(root), key);
return merge(merge(std::move(left), std::make_unique<Node>(key, prio)), std::move(right));
}
void keys_in_order(const Node* node, std::vector<int>& keys) {
if (!node) return;
keys_in_order(node->left.get(), keys);
keys.push_back(node->key);
keys_in_order(node->right.get(), keys);
}
int main() {
Tree root;
for (auto [key, prio] : {std::pair{5, 50}, std::pair{3, 80}, std::pair{8, 20}, std::pair{1, 90}, std::pair{4, 10}}) {
root = insert(std::move(root), key, prio);
}
std::vector<int> keys;
keys_in_order(root.get(), keys);
for (int key : keys) std::cout << key << ' ';
std::cout << "корень " << root->key << '\n'; // 1 3 4 5 8 корень 1
return 0;
}
Удаление вершины с заданным ключом x
{ Удаление вершины }
procedure Delete( var T:Treap; x:integer );
var L,R,M,Rs : Treap;
begin
Split(T,x-1,L,R);
Split(R,x,M,Rs);
{ Удаляем одну верхнюю вершину в M }
if M <> nil then begin
if M.Left = nil then
M := M.Right
else
M := M.Left;
end;
{ Сливаем вместе оставшиеся куски }
T := Merge(L,Merge(M,Rs));
end;
Реализация на Python
# Удаление ключа из декартова дерева (split + merge): O(log n) в среднем, где n - число вершин
class Node:
def __init__(self, key, prio, left=None, right=None):
self.key = key
self.prio = prio # у родителя приоритет не меньше, чем у детей (куча)
self.left = left
self.right = right
def merge(left, right):
"""Все ключи left не больше ключей right; корнем становится вершина с большим приоритетом."""
if left is None:
return right
if right is None:
return left
if left.prio > right.prio:
left.right = merge(left.right, right)
return left
right.left = merge(left, right.left)
return right
def split(node, key):
"""Возвращает два дерева: с ключами <= key и с ключами > key."""
if node is None:
return None, None
if node.key <= key:
left, right = split(node.right, key)
node.right = left
return node, right
left, right = split(node.left, key)
node.left = right
return left, node
def erase(root, key):
"""Удаляет одну вершину с ключом key: режем на части, у средней убираем корень, склеиваем."""
left, rest = split(root, key - 1) # целые ключи
middle, right = split(rest, key)
if middle is not None:
middle = merge(middle.left, middle.right)
return merge(left, merge(middle, right))
def keys(node):
"""Ключи дерева в порядке возрастания."""
if node is None:
return []
return keys(node.left) + [node.key] + keys(node.right)
if __name__ == "__main__":
root = None
for key, prio in [(1, 5), (2, 3), (3, 8), (4, 1), (5, 6)]: # ключи по возрастанию
root = merge(root, Node(key, prio))
print("до:", keys(root))
print("после:", keys(erase(root, 3)))
Реализация на Rust
// Удаление ключа из декартова дерева (split + merge): O(log n) в среднем, где n - число вершин
pub type Link = Option<Box<Node>>;
pub struct Node { pub key: i64, pub prio: u64, pub left: Link, pub right: Link } // приоритет родителя не меньше детского
// Все ключи a не больше ключей b; корнем становится вершина с большим приоритетом
pub fn merge(a: Link, b: Link) -> Link {
match (a, b) {
(None, b) => b,
(a, None) => a,
(Some(mut a), Some(b)) if a.prio > b.prio => {
a.right = merge(a.right.take(), Some(b));
Some(a)
}
(Some(a), Some(mut b)) => {
b.left = merge(Some(a), b.left.take());
Some(b)
}
}
}
// Разрезание: в первом дереве ключи <= key, во втором - больше key
pub fn split(link: Link, key: i64) -> (Link, Link) {
let Some(mut node) = link else { return (None, None) };
if node.key <= key {
let (left, right) = split(node.right.take(), key);
node.right = left;
(Some(node), right)
} else {
let (left, right) = split(node.left.take(), key);
node.left = right;
(left, Some(node))
}
}
// Удаляем одну вершину с ключом key: режем на части, у средней убираем корень, склеиваем
pub fn erase(root: Link, key: i64) -> Link {
let (left, rest) = split(root, key - 1);
let (middle, right) = split(rest, key);
let middle = middle.and_then(|node| merge(node.left, node.right));
merge(left, merge(middle, right))
}
// Ключи дерева в порядке возрастания
pub fn keys(link: &Link) -> Vec<i64> {
match link {
None => vec![],
Some(n) => [keys(&n.left), vec![n.key], keys(&n.right)].concat(),
}
}
fn main() {
// Ключи добавляем по возрастанию: (ключ, приоритет)
let mut root: Link = None;
for (key, prio) in [(1, 5), (2, 3), (3, 8), (4, 1), (5, 6)] {
root = merge(root, Some(Box::new(Node { key, prio, left: None, right: None })));
}
println!("до: {:?}", keys(&root));
root = erase(root, 3);
println!("после: {:?}", keys(&root));
}
Реализация на C++
// Удаление ключа из декартова дерева (split + merge): O(log n) в среднем, где n - число вершин
#include <cstdio>
#include <memory>
#include <utility>
struct Node { int key, prio; std::unique_ptr<Node> left, right; }; // у родителя приоритет не меньше, чем у детей
using Tree = std::unique_ptr<Node>;
// Все ключи a не больше ключей b; корнем становится вершина с большим приоритетом
Tree merge(Tree a, Tree b) {
if (!a) return b;
if (!b) return a;
if (a->prio > b->prio) {
a->right = merge(std::move(a->right), std::move(b));
return a;
}
b->left = merge(std::move(a), std::move(b->left));
return b;
}
// Разрезание: в первом дереве ключи <= key, во втором - больше key
std::pair<Tree, Tree> split(Tree t, int key) {
if (!t) return {nullptr, nullptr};
if (t->key <= key) {
auto [left, right] = split(std::move(t->right), key);
t->right = std::move(left);
return {std::move(t), std::move(right)};
}
auto [left, right] = split(std::move(t->left), key);
t->left = std::move(right);
return {std::move(left), std::move(t)};
}
// Удаляем одну вершину с ключом key: режем на части, у средней убираем корень, склеиваем
Tree erase(Tree root, int key) {
auto [left, rest] = split(std::move(root), key - 1);
auto [middle, right] = split(std::move(rest), key);
if (middle) middle = merge(std::move(middle->left), std::move(middle->right));
return merge(std::move(left), merge(std::move(middle), std::move(right)));
}
void printKeys(const Node* t) { // ключи в порядке возрастания
if (!t) return;
printKeys(t->left.get());
std::printf(" %d", t->key);
printKeys(t->right.get());
}
int main() {
// Ключи добавляем по возрастанию: (ключ, приоритет)
const std::pair<int, int> items[] = {{1, 5}, {2, 3}, {3, 8}, {4, 1}, {5, 6}};
Tree root;
for (const auto& [key, prio] : items) {
root = merge(std::move(root), std::make_unique<Node>(Node{key, prio, nullptr, nullptr}));
}
root = erase(std::move(root), 3);
std::printf("после удаления 3:");
printKeys(root.get());
std::printf("\n");
return 0;
}
Поиск минимума и максимума
{ Поиск минимума в дереве }
function MinT( T:Treap ):integer;
begin
if T = nil then { Если дерево пустое, то минимума нет }
MinT := High(integer)
else if T.Left = nil then { Левого поддерева нет => текущий элемент - минимум }
MinT := T.x
else
MinT := MinT(T.Left); { Минимум в левом поддереве }
end;
{ Поиск максимума в дереве - аналогично минимуму, только идём вправо }
function MaxT( T:Treap ):integer;
begin
if T = nil then
MaxT := Low(Integer)
else if T.Right = nil then
MaxT := T.x
else
MaxT := MaxT(T.Right);
end;
Реализация на Python
# Минимум и максимум в декартовом дереве: O(h) по времени, где h - высота дерева
class Node:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
def min_key(root):
"""Минимум - самая левая вершина дерева; для пустого дерева возвращаем None."""
if root is None:
return None
while root.left is not None:
root = root.left
return root.key
def max_key(root):
"""Максимум - самая правая вершина дерева; для пустого дерева возвращаем None."""
if root is None:
return None
while root.right is not None:
root = root.right
return root.key
if __name__ == "__main__":
# Дерево: корень 4, слева 2 (с сыновьями 1 и 3), справа 6 (с сыном 7)
root = Node(4, Node(2, Node(1), Node(3)), Node(6, None, Node(7)))
print("Минимум:", min_key(root), "Максимум:", max_key(root))
Реализация на Rust
// Минимум и максимум в декартовом дереве: O(h) по времени, где h - высота дерева
pub type Link = Option<Box<Node>>;
pub struct Node {
pub key: i64,
pub left: Link,
pub right: Link,
}
pub fn node(key: i64, left: Link, right: Link) -> Link {
Some(Box::new(Node { key, left, right }))
}
/// Минимум - самая левая вершина дерева; для пустого дерева возвращаем None.
pub fn min_key(mut link: &Link) -> Option<i64> {
let mut best = None;
while let Some(n) = link {
best = Some(n.key);
link = &n.left;
}
best
}
/// Максимум - самая правая вершина дерева; для пустого дерева возвращаем None.
pub fn max_key(mut link: &Link) -> Option<i64> {
let mut best = None;
while let Some(n) = link {
best = Some(n.key);
link = &n.right;
}
best
}
fn main() {
// Дерево: корень 4, слева 2 (с сыновьями 1 и 3), справа 6 (с сыном 7)
let root = node(4, node(2, node(1, None, None), node(3, None, None)), node(6, None, node(7, None, None)));
println!("Минимум: {}, максимум: {}", min_key(&root).unwrap(), max_key(&root).unwrap());
}
Реализация на C++
// Минимум и максимум в декартовом дереве: O(h) по времени, где h - высота дерева
#include <cstdio>
#include <memory>
#include <optional>
#include <utility>
struct Node {
int key;
std::unique_ptr<Node> left, right;
};
std::unique_ptr<Node> makeNode(int key, std::unique_ptr<Node> left = nullptr,
std::unique_ptr<Node> right = nullptr) {
return std::make_unique<Node>(Node{key, std::move(left), std::move(right)});
}
// Минимум - самая левая вершина дерева; для пустого дерева результат пуст
std::optional<int> minKey(const Node* node) {
std::optional<int> best;
for (; node != nullptr; node = node->left.get()) best = node->key;
return best;
}
// Максимум - самая правая вершина дерева; для пустого дерева результат пуст
std::optional<int> maxKey(const Node* node) {
std::optional<int> best;
for (; node != nullptr; node = node->right.get()) best = node->key;
return best;
}
int main() {
// Дерево: корень 4, слева 2 (с сыновьями 1 и 3), справа 6 (с сыном 7)
auto root = makeNode(4, makeNode(2, makeNode(1), makeNode(3)), makeNode(6, nullptr, makeNode(7)));
std::printf("Минимум: %d, максимум: %d\n", minKey(root.get()).value(), maxKey(root.get()).value());
return 0;
}
Поиск значения в дереве
{ Поиск значения в дереве }
function Find( T:Treap; x:integer ):boolean;
begin
if T = nil then
Find := false { Не найдено }
else if T.x = x then begin
Find := true; { x найдено в текущей вершине }
end else if x < T.x then
Find := Find(T.Left,x) { Поищем слева }
else
Find := Find(T.Right,x); { Поищем справа }
end;
Реализация на Python
# Поиск ключа в декартовом дереве (как в двоичном дереве поиска): O(h) по времени, где h - высота дерева
class Node:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
def find_key(root, key) -> bool:
"""Сравниваем с ключом вершины: равен - нашли, меньше - идем влево, больше - вправо."""
node = root
while node is not None:
if node.key == key:
return True
node = node.left if key < node.key else node.right
return False
if __name__ == "__main__":
# Дерево: корень 4, слева 2 (с сыновьями 1 и 3), справа 6 (с сыном 7)
root = Node(4, Node(2, Node(1), Node(3)), Node(6, None, Node(7)))
print("Ключ 3:", find_key(root, 3), "Ключ 5:", find_key(root, 5))
Реализация на Rust
// Поиск ключа в декартовом дереве (как в двоичном дереве поиска): O(h) по времени, где h - высота дерева
pub type Link = Option<Box<Node>>;
pub struct Node {
pub key: i64,
pub left: Link,
pub right: Link,
}
pub fn node(key: i64, left: Link, right: Link) -> Link {
Some(Box::new(Node { key, left, right }))
}
/// Сравниваем с ключом вершины: равен - нашли, меньше - идем влево, больше - вправо.
pub fn find_key(mut link: &Link, key: i64) -> bool {
while let Some(n) = link {
if n.key == key {
return true;
}
link = if key < n.key { &n.left } else { &n.right };
}
false
}
fn main() {
// Дерево: корень 4, слева 2 (с сыновьями 1 и 3), справа 6 (с сыном 7)
let root = node(4, node(2, node(1, None, None), node(3, None, None)), node(6, None, node(7, None, None)));
println!("Ключ 3: {}, ключ 5: {}", find_key(&root, 3), find_key(&root, 5));
}
Реализация на C++
// Поиск ключа в декартовом дереве (как в двоичном дереве поиска): O(h) по времени, где h - высота дерева
#include <cstdio>
#include <memory>
#include <utility>
struct Node {
int key;
std::unique_ptr<Node> left, right;
};
std::unique_ptr<Node> makeNode(int key, std::unique_ptr<Node> left = nullptr,
std::unique_ptr<Node> right = nullptr) {
return std::make_unique<Node>(Node{key, std::move(left), std::move(right)});
}
// Сравниваем с ключом вершины: равен - нашли, меньше - идем влево, больше - вправо
bool findKey(const Node* node, int key) {
while (node != nullptr) {
if (node->key == key) return true;
node = key < node->key ? node->left.get() : node->right.get();
}
return false;
}
int main() {
// Дерево: корень 4, слева 2 (с сыновьями 1 и 3), справа 6 (с сыном 7)
auto root = makeNode(4, makeNode(2, makeNode(1), makeNode(3)), makeNode(6, nullptr, makeNode(7)));
std::printf("Ключ 3: %s, ключ 5: %s\n", findKey(root.get(), 3) ? "да" : "нет",
findKey(root.get(), 5) ? "да" : "нет");
return 0;
}
Вычисление высоты дерева
{ Высота дерева }
function Height( T:Treap ):integer;
begin
if T = nil then
Result := 0
else
Result := max(Height(T.Left),Height(T.Right))+1;
end;
Реализация на Python
# Высота декартова дерева (рекурсивно): O(n) по времени, O(h) по памяти стека рекурсии
class Node:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
def height(node) -> int:
"""Высота пустого дерева равна 0, иначе 1 + максимум из высот поддеревьев."""
if node is None:
return 0
return 1 + max(height(node.left), height(node.right))
if __name__ == "__main__":
# Дерево: корень 4, слева 2 (с сыновьями 1 и 3), справа 6 (с сыном 7)
root = Node(4, Node(2, Node(1), Node(3)), Node(6, None, Node(7)))
print("Высота:", height(root))
Реализация на Rust
// Высота декартова дерева (рекурсивно): O(n) по времени, O(h) по памяти стека рекурсии
pub type Link = Option<Box<Node>>;
pub struct Node {
pub key: i64,
pub left: Link,
pub right: Link,
}
pub fn node(key: i64, left: Link, right: Link) -> Link {
Some(Box::new(Node { key, left, right }))
}
/// Высота пустого дерева равна 0, иначе 1 + максимум из высот поддеревьев.
pub fn height(link: &Link) -> usize {
match link {
None => 0,
Some(n) => 1 + height(&n.left).max(height(&n.right)),
}
}
fn main() {
// Дерево: корень 4, слева 2 (с сыновьями 1 и 3), справа 6 (с сыном 7)
let root = node(4, node(2, node(1, None, None), node(3, None, None)), node(6, None, node(7, None, None)));
println!("Корень {}, высота {}", root.as_ref().map_or(0, |n| n.key), height(&root));
}
Реализация на C++
// Высота декартова дерева (рекурсивно): O(n) по времени, O(h) по памяти стека рекурсии
#include <algorithm>
#include <cstdio>
#include <memory>
#include <utility>
struct Node {
int key;
std::unique_ptr<Node> left, right;
};
std::unique_ptr<Node> makeNode(int key, std::unique_ptr<Node> left = nullptr,
std::unique_ptr<Node> right = nullptr) {
return std::make_unique<Node>(Node{key, std::move(left), std::move(right)});
}
// Высота пустого дерева равна 0, иначе 1 + максимум из высот поддеревьев
int height(const Node* node) {
if (node == nullptr) return 0;
return 1 + std::max(height(node->left.get()), height(node->right.get()));
}
int main() {
// Дерево: корень 4, слева 2 (с сыновьями 1 и 3), справа 6 (с сыном 7)
auto root = makeNode(4, makeNode(2, makeNode(1), makeNode(3)), makeNode(6, nullptr, makeNode(7)));
std::printf("Высота: %d\n", height(root.get()));
return 0;
}
Тестирование всех операций
var
T : Treap = nil;
i,j : Integer;
begin
Randomize;
{ Проверяем что сейчас ничего в дереве нет }
for i := -10 to 10 do
assert( not Find(T,i) );
{ Добавляем вершины }
for i := 1 to 1000000 do begin
Add(T,i);
assert( not Find(T,-1) ); { Вершины -1 по-прежнему нет }
for j := 1 to min(10,i) do { Добавленные вершины есть }
assert( Find(T,j) );
assert( not Find(T,i+1) ); { Вершин с большим номером нет }
end;
Writeln('Высота дерева (оценка: 4*log(N)): ',Height(T));
assert( Find(T,10) );
Delete(T,10);
assert( not Find(T,10) );
end.
Решение задачи поиска чисел в массиве
var
T : Treap = nil;
N,M,x,i : Integer;
begin
Reset(Input,'find.in');
Rewrite(Output,'find.out');
Randomize;
Read(N,M);
for i := 1 to N do begin
Read(x);
Add(T,x);
end;
for i := 1 to M do begin
Read(x);
if Find(T,x) then
Writeln('YES')
else
Writeln('NO');
end;
end.