Основное введение: познакомить со знаниями, связанными с бинарным деревом поиска, включая метод бинарного поиска, бинарное дерево поиска и т. д.
бинарный поиск
определение вики
алгоритм поиска для нахождения определенного элемента в упорядоченном массиве. Процесс поиска начинается со среднего элемента массива и заканчивается, если средний элемент является именно тем элементом, который нужно найти; если конкретный элемент больше или меньше среднего элемента, он ищет в половине массива, которая больше или меньше. меньше, чем средний элемент, и начните сравнение со среднего элемента, как вы делали в начале. Если на каком-то шаге массив пуст, значит, он не найден. Этот алгоритм поиска уменьшает диапазон поиска наполовину для каждого сравнения.
Уведомление
Для упорядоченных последовательностей можно использовать бинарный поиск.
выполнить
<?php
/**
* 二分查找
*/
// 二分查找法,在有序数组arr中,查找target
// 如果找到target,返回相应的索引index
// 如果没有找到target,返回-1
function binarySearch($arr, $n, $target){
//在数组arr[l...r]中查找target
$l = 0;
$r = $n -1;
while ($l <= $r) {
//$mid = (int)(($l + $r) / 2);//容易越界
$mid = $l + (int)(($r - $l) / 2);
if ($arr[$mid] == $target) {
return $mid;
}elseif ($arr[$mid] < $target) {
//在arr[mid + 1, r]中寻找
$l = $mid + 1;
}else{
$r = $mid - 1;
}
}
return -1;
}
echo "程序运行\n";
//测试
$arr = array();
$n = 100000;
for ($i=0; $i < $n; $i++) {
$arr[$i] = $i;
}
$t1 = microtime(true);
for ($i=0; $i < 2 * $n; $i++) {
$v = binarySearch($arr, $n, $i);
if ($i < $n) {
assert($v == $i);
}elseif ($i >= $n) {
assert($v == -1);
}
}
$t2 = microtime(true);
echo "{$sortName}运行的时间为：". (($t2-$t1)).'s'."\n";
Особо следует отметить:
//$mid = (int)(($l + $r) / 2);//容易越界
$mid = $l + (int)(($r - $l) / 2);
Среднее значение не использует 1, потому что это может привести к выходу за пределы допустимого диапазона.
Рекурсивная реализация:
<?php
/**
* 二分查找
*/
//递归法,边界函数
function _binarySearch2($arr, $l, $r, $target){
if ($l > $r) {
return -1;
}
$mid = $l + (int)(($r - $l) / 2);
if ($arr[$mid] == $target) {
return $mid;
}elseif($arr[$mid] < $target){
return _binarySearch2($arr, $mid + 1, $r, $target);
}else{
return _binarySearch2($arr, $l, $mid - 1, $target);
}
}
function binarySearch2($arr, $n, $target){
return _binarySearch2($arr, 0, $n-1, $target);
}
echo "程序运行\n";
//测试
$arr = array();
$n = 100000;
for ($i=0; $i < $n; $i++) {
$arr[$i] = $i;
}
$t1 = microtime(true);
for ($i=0; $i < 2 * $n; $i++) {
$v = binarySearch2($arr, $n, $i);
if ($i < $n) {
assert($v == $i);
}elseif ($i >= $n) {
assert($v == -1);
}
}
$t2 = microtime(true);
echo "{$sortName}运行的时间为：". (($t2-$t1)).'s'."\n";
Расширение бинарного поиска: пол и потолок
определение этажа
Метод бинарного поиска в отсортированном массиве arr находит цель; Если цель найдена, вернуть индекс, соответствующий первой цели; Если цель не найдена, вернуть индекс, соответствующий максимальному значению, меньшему, чем цель, если максимальных значений несколько, вернуть максимальный индекс; Если эта цель меньше минимального значения элемента всего массива, для этой цели нет минимального значения, и возвращается -1;
выполнить
int floor(T arr[], int n, T target){
assert( n >= 0 );
// 寻找比target小的最大索引
int l = -1, r = n-1;
while( l < r ){
// 使用向上取整避免死循环
int mid = l + (r-l+1)/2;
if( arr[mid] >= target )
r = mid - 1;
else
l = mid;
}
assert( l == r );
// 如果该索引+1就是target本身, 该索引+1即为返回值
if( l + 1 < n && arr[l+1] == target )
return l + 1;
// 否则, 该索引即为返回值
return l;
}
определение потолка
Метод бинарного поиска, в отсортированном массиве arr найти цель Если цель найдена, вернуть индекс, соответствующий последней цели; Если цель не найдена, вернуть индекс, соответствующий наименьшему значению, большему, чем цель, если есть несколько значений этого наименьшего значения, вернуть наименьший индекс; Если цель больше, чем максимальное значение элемента всего массива, значение ceil цели не существует, и возвращается количество элементов во всем массиве n;
выполнить
int ceil(T arr[], int n, T target){
assert( n >= 0 );
// 寻找比target大的最小索引值
int l = 0, r = n;
while( l < r ){
// 使用普通的向下取整即可避免死循环
int mid = l + (r-l)/2;
if( arr[mid] <= target )
l = mid + 1;
else // arr[mid] > target
r = mid;
}
assert( l == r );
// 如果该索引-1就是target本身, 该索引+1即为返回值
if( r - 1 >= 0 && arr[r-1] == target )
return r-1;
// 否则, 该索引即为返回值
return r;
}
Основы двоичного дерева поиска
Определение двоичного дерева поиска
Также называется бинарным деревом поиска. Он может не только находить данные, но также эффективно вставлять и удалять данные. Особенности: ключевое значение каждого узла больше, чем у левого дочернего узла, и меньше, чем у правого дочернего узла. Обратите внимание, что это не обязательно полное бинарное дерево. Следовательно, ключ узла уникален, и мы используем его для индексации значения, соответствующего ключу.Обратите внимание, что ключ отмечен на рисунке.
Следовательно, бинарное дерево поиска не подходит для представления в виде массива и обычно представляется в виде узлового узла. Преимущества структур данных по сравнению с массивами:
Еще одним преимуществом является то, что его ключ может быть определен сам по себе, например, с использованием String в качестве ключа для реализации таблицы поиска, в то время как массив может использовать только индекс
Структура узла
Сначала реализуйте каждый узел: элементы узла включают ключ, значение, левый дочерний узел и правый дочерний узел.
struct Node{
Key key;
Value value;
Node *left;
Node *right;
Node(Key key, Value value){
this->key = key;
this->value = value;
this->left = this->right = NULL;
}
};
Для того, чтобы облегчить работу класса BST, построенного здесь.
#include <iostream>
using namespace std;
template <typename Key, typename Value>
class BST{
private:
struct Node{
Key key;
Value value;
Node *left;
Node *right;
Node(Key key, Value value){
this->key = key;
this->value = value;
this->left = this->right = NULL;
}
};
Node *root;
int count;
public:
BST(){
root = NULL;
count = 0;
}
~BST(){
// TODO: ~BST()
}
int size(){
return count;
}
bool isEmpty(){
return count == 0;
}
};
int main() {
return 0;
}
Создание бинарного дерева поиска (операция вставки)
На самом деле создание дерева — это процесс вставки, и каждая вставка не меняет природу и структуру дерева. Если узел существует, обновите его напрямую
МысльОсновная идея: начать с корневого узла, чтобы найти позицию вставки, которая удовлетворяет характеристикам бинарного дерева поиска, больше, чем левый дочерний узел, и меньше, чем правый дочерний узел.
- шаг:
- Начиная с корневого узла, сначала сравните текущий узел, если текущий узел имеет значение null, то он, очевидно, должен быть вставлен в этот узел.
- Если указанный выше узел не нулевой, то по сравнению с текущим узлом, если он меньше узла, он помещается в левое поддерево, а если он больше узла, он помещается в правое поддерево.
- Затем выполните операции шагов 1 и 2 выше для рекурсивной рекурсии левого поддерева или правого поддерева соответственно.
** Уведомление**
На этом этапе используется рекурсия, затем рекурсия для определенной проблемы, и ее подзадачи должны быть одной и той же модели. Небольшая проблема здесь: в определенный узел, а затем для работы, поэтому параметр должен иметь узел для реализации цикла. Здесь узел (ключ, значение) вставляется в бинарное дерево поиска с корнем в узле, здесь используется тип int, а внешние пользователи Не нужно понимать концепцию узла, им нужно знать только входящий ключ и значение. Временный дизайн легко понять по ключу и значению, переданному пользователем, а также удобно использовать его в соответствии с ключом.
** выполнить**
public:
void insert(Key key, Value value){
root = insert(root, key, value);
}
private:
// 向以node为根的二叉搜索树中,插入节点(key, value)
// 返回插入新节点后的二叉搜索树的根
Node* insert(Node *node, Key key, Value value){
if( node == NULL ){
count ++;
return new Node(key, value);
}
if( key == node->key )
node->value = value;
else if( key < node->key )
node->left = insert( node->left , key, value);
else // key > node->key
node->right = insert( node->right, key, value);
return node;
}
};
Поисковая операция бинарного дерева поиска
public:
bool contain(Key key){
return contain(root, key);
}
Value* search(Key key){
return search( root , key );
}
private:
// 查看以node为根的二叉搜索树中是否包含键值为key的节点
bool contain(Node* node, Key key){
if( node == NULL )
return false;
if( key == node->key )
return true;
else if( key < node->key )
return contain( node->left , key );
else // key > node->key
return contain( node->right , key );
}
// 在以node为根的二叉搜索树中查找key所对应的value
Value* search(Node* node, Key key){
if( node == NULL )
return NULL;
if( key == node->key )
return &(node->value);
else if( key < node->key )
return search( node->left , key );
else // key > node->key
return search( node->right, key );
}
Обход бинарного дерева поиска (обход в глубину)
Обход бинарного дерева поиска.
Обход означает посещение каждого узла дерева один раз и только один раз по определенному маршруту поиска. Существует три способа обхода бинарного дерева:
- Предварительный обход: сначала посетите текущий узел, а затем рекурсивно посетите левое и правое поддеревья по очереди.
- Неупорядоченный обход: сначала рекурсивно посещаем левое поддерево, затем посещаем себя, а затем рекурсивно посещаем правое поддерево.
- Обход в обратном порядке: сначала рекурсивно посещаем левое и правое поддеревья и, наконец, посещаем текущий узел.
Как понять первый рекурсивный доступ выше? Например, для обхода порядка, если левый дочерний узел любого узла не был посещен, продолжайте посещать его левый дочерний узел, пока левый дочерний узел не будет завершен. После завершения всего обхода будет выполняться обход по порядку от узла, который посещается первым, а затем по очереди вверх.
шаг
обход предварительного заказа
Неупорядоченный обход
последующий обход
Примечание: Каждый узел будет посещен три раза.Предварительный порядок, средний порядок и пост-порядок этих трех типов относятся к порядку текущего узла (то есть среднего).
Код
#include <iostream>
#include <queue>
using namespace std;
template <typename Key, typename Value>
class BST{
private:
struct Node{
Key key;
Value value;
Node *left;
Node *right;
Node(Key key, Value value){
this->key = key;
this->value = value;
this->left = this->right = NULL;
}
};
Node *root;
int count;
public:
BST(){
root = NULL;
count = 0;
}
~BST(){
destroy( root );
}
int size(){
return count;
}
bool isEmpty(){
return count == 0;
}
void insert(Key key, Value value){
root = insert(root, key, value);
}
bool contain(Key key){
return contain(root, key);
}
Value* search(Key key){
return search( root , key );
}
// 前序遍历
void preOrder(){
preOrder(root);
}
// 中序遍历
void inOrder(){
inOrder(root);
}
// 后序遍历
void postOrder(){
postOrder(root);
}
// 层序遍历
void levelOrder(){
queue<Node*> q;
q.push(root);
while( !q.empty() ){
Node *node = q.front();
q.pop();
cout<<node->key<<endl;
if( node->left )
q.push( node->left );
if( node->right )
q.push( node->right );
}
}
private:
// 向以node为根的二叉搜索树中,插入节点(key, value)
// 返回插入新节点后的二叉搜索树的根
Node* insert(Node *node, Key key, Value value){
if( node == NULL ){
count ++;
return new Node(key, value);
}
if( key == node->key )
node->value = value;
else if( key < node->key )
node->left = insert( node->left , key, value);
else // key > node->key
node->right = insert( node->right, key, value);
return node;
}
// 查看以node为根的二叉搜索树中是否包含键值为key的节点
bool contain(Node* node, Key key){
if( node == NULL )
return false;
if( key == node->key )
return true;
else if( key < node->key )
return contain( node->left , key );
else // key > node->key
return contain( node->right , key );
}
// 在以node为根的二叉搜索树中查找key所对应的value
Value* search(Node* node, Key key){
if( node == NULL )
return NULL;
if( key == node->key )
return &(node->value);
else if( key < node->key )
return search( node->left , key );
else // key > node->key
return search( node->right, key );
}
// 对以node为根的二叉搜索树进行前序遍历
void preOrder(Node* node){
if( node != NULL ){
cout<<node->key<<endl;
preOrder(node->left);
preOrder(node->right);
}
}
// 对以node为根的二叉搜索树进行中序遍历
void inOrder(Node* node){
if( node != NULL ){
inOrder(node->left);
cout<<node->key<<endl;
inOrder(node->right);
}
}
// 对以node为根的二叉搜索树进行后序遍历
void postOrder(Node* node){
if( node != NULL ){
postOrder(node->left);
postOrder(node->right);
cout<<node->key<<endl;
}
}
void destroy(Node* node){
if( node != NULL ){
destroy( node->left );
destroy( node->right );
delete node;
count --;
}
}
};
int main() {
srand(time(NULL));
BST<int,int> bst = BST<int,int>();
int n = 10;
for( int i = 0 ; i < n ; i ++ ){
int key = rand()%n;
// 为了后续测试方便,这里value值取和key值一样
int value = key;
cout<<key<<" ";
bst.insert(key,value);
}
cout<<endl;
// test size
cout<<"size: "<<bst.size()<<endl<<endl;
// test preOrder
cout<<"preOrder: "<<endl;
bst.preOrder();
cout<<endl<<endl;
// test inOrder
cout<<"inOrder: "<<endl;
bst.inOrder();
cout<<endl<<endl;
// test postOrder
cout<<"postOrder: "<<endl;
bst.postOrder();
cout<<endl<<endl;
// test levelOrder
cout<<"levelOrder: "<<endl;
bst.levelOrder();
cout<<endl<<endl;
return 0;
}
результат
2 0 8 3 6 8 3 0 0 1
size: 6
preOrder:
2
0
1
8
3
6
inOrder:
0
1
2
3
6
8
postOrder:
1
0
6
3
8
2
levelOrder:
2
0
8
1
3
6
Обход в порядке уровней (обход в ширину)
То, что мы упоминали ранее, — это обход в глубину, реализуемый рекурсией.Пока нижний узел по-прежнему соответствует требуемым условиям, он будет продолжать выполняться сначала на запад.
Обход в порядке уровней — это метод обхода в ширину, который сначала обходит корневой узел, затем обходит второй слой и так далее сверху вниз и слева направо. Идея, реализованная здесь: использовать функцию очереди «первым пришел – первым обслужен» (поскольку конкретная реализация очереди не ясна, я только пока понимаю эту идею здесь). Когда очередь не пуста, начните операцию. Если очередь не пуста, то корневой узел должен существовать. Сначала поместите корень в очередь, а затем начните оценку цикла: очередь условий оценки - kong, сначала пройдите через текущего узла, а затем dequeue, (очередь в это время пуста) и затем посмотреть, есть ли у этого узла левый и правый дочерние узлы, есть ли в очереди левый и правый дочерние узлы (чтобы она снова не была пустой, и спускается на один слой), когда обрабатываются левый и правый дочерние узлы. Продолжайте цикл, чтобы сделать то же самое.
выполнить
public:
// 层序遍历
void levelOrder(){
queue<Node*> q;
q.push(root);
while( !q.empty() ){
Node *node = q.front();
q.pop();
cout<<node->key<<endl;
if( node->left )
q.push( node->left );
if( node->right )
q.push( node->right );
}
}
private:
void destroy(Node* node){
if( node != NULL ){
destroy( node->left );
destroy( node->right );
delete node;
count --;
}
}
};
}
Уведомление
Удаление бинарного дерева заключается в использовании последующего обхода
удалить макс, мин
Найдите максимум и минимум
// 寻找最小的键值
Key minimum(){
assert( count != 0 );
Node* minNode = minimum( root );
return minNode->key;
}
// 寻找最大的键值
Key maximum(){
assert( count != 0 );
Node* maxNode = maximum(root);
return maxNode->key;
}
// 在以node为根的二叉搜索树中,返回最小键值的节点
Node* minimum(Node* node){
if( node->left == NULL )
return node;
return minimum(node->left);
}
// 在以node为根的二叉搜索树中,返回最大键值的节点
Node* maximum(Node* node){
if( node->right == NULL )
return node;
return maximum(node->right);
}
Удалить максимальное и минимальное значения бинарного дерева поиска.
// 从二叉树中删除最小值所在节点
void removeMin(){
if( root )
root = removeMin( root );
}
// 从二叉树中删除最大值所在节点
void removeMax(){
if( root )
root = removeMax( root );
}
// 删除掉以node为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
Node* removeMin(Node* node){
if( node->left == NULL ){
Node* rightNode = node->right;
delete node;
count --;
return rightNode;
}
node->left = removeMin(node->left);
return node;
}
// 删除掉以node为根的二分搜索树中的最大节点
// 返回删除节点后新的二分搜索树的根
Node* removeMax(Node* node){
if( node->right == NULL ){
Node* leftNode = node->left;
delete node;
count --;
return leftNode;
}
node->right = removeMax(node->right);
return node;
}
Удаление бинарного дерева поиска
Удаление произвольных узлов: метод, предложенный Хиббардом, под названием Удаление Хаббарда. Разница между удалением любого узла и удалением наименьшего и наибольшего узлов заключается в том, что при удалении любого узла возможно, что и слева, и справа есть дочерние узлы. Прежде всего, мы не можем просто поместить левый дочерний узел или правый дочерний узел непосредственно на позицию удаленного в данный момент узла, потому что это Легко сделать так, чтобы характеристики бинарного дерева поиска не удовлетворялись.Мы должны найти, когда предшествующий предшественник или преемник помещается в текущую позицию, предшественник: фронт Элемент, который меньше его; преемник: элемент, который больше его. Например, метод, в котором мы находим все узлы в его правом дочернем элементе. Наименьший узел в , а затем поместите наименьший узел в удаленный узел, в это время все еще соответствует характеристикам двоичного дерева поиска, левый дочерний узел меньше его, а правые дочерние узлы больше его. Другой аналогичный — найти самый большой узел из всех узлов в левом поддереве.
** ШАГ **
- Найдите минимальное значение правого дочернего узла и удалите его.
- Затем поместите удаленный узел на место найденного узла. Это назначение правого дочернего узла и левого дочернего узла найденного узла удаленному узлу соответственно.
- Наконец, этому узлу также должна быть назначена правильная позиция родительского узла удаленного узла.
Код
// 从二叉树中删除键值为key的节点
void remove(Key key){
root = remove(root, key);
}
// 删除掉以node为根的二分搜索树中键值为key的节点
// 返回删除节点后新的二分搜索树的根
Node* remove(Node* node, Key key){
if( node == NULL )
return NULL;
if( key < node->key ){
node->left = remove( node->left , key );
return node;
}
else if( key > node->key ){
node->right = remove( node->right, key );
return node;
}
else{ // key == node->key
if( node->left == NULL ){
Node *rightNode = node->right;
delete node;
count --;
return rightNode;
}
if( node->right == NULL ){
Node *leftNode = node->left;
delete node;
count--;
return leftNode;
}
// node->left != NULL && node->right != NULL
Node *successor = new Node(minimum(node->right));
count ++;
successor->right = removeMin(node->right);
successor->left = node->left;
delete node;
count --;
return successor;
}
}
Последовательность бинарных деревьев поиска
- предшественник (предшественник)
- преемник
- этаж: не больше значения, соответствующего входящему ключу
- ceil: не меньше значения, соответствующего входящему ключу
- Рейтинг книг в бинарном поиске
Хотите знать, какое место в книге занимает ключ в двоичном дереве поиска? Для каждого узла дерева добавьте поле, чтобы отметить, сколько дочерних узлов имеет текущий узел, а затем его можно вычислить с помощью простой логической суммы. Вышел номер один. Обратите внимание, что при добавлении такой записи домена самое сложное — сохранить соответствующий домен при вставке и удалении, не забывайте об этом.
- выберите: Кто 10-й элемент?
-
Бинарное дерево поиска с повторяющимися элементами
- Первая реализация: поместите те, которые больше узла, на правый дочерний узел, а те, которые меньше или равны текущему узлу, на левый дочерний узел. Но это пустая трата места, когда много повторяющихся элементов.
- Вторая реализация: также добавить в Node поле, которое используется для отметки количества текущих узлов.
Ограничения бинарных деревьев поиска
Одни и те же данные могут соответствовать разным бинарным деревьям поиска. Когда порядок вставки данных близок к упорядоченному, бинарное дерево поиска может выродиться в связанный список, а временная сложность в это время снова меняется с logn на n. Но мы не можем перетасовать все элементы сразу, потому что может быть немного данных, которые вы вводите, и вы не можете получить все элементы. На данный момент улучшенное бинарное дерево выглядит так:
Реализация сбалансированного бинарного дерева: 1), красно-черное дерево 2), 2-3 дерева 3), дерево АВЛ 4), раскладное дерево 5), комбинация сбалансированного бинарного дерева Treap и кучи. Сбалансированное бинарное дерево обладает следующими свойствами: это пустое дерево или абсолютное значение разности высот между его левым и правым поддеревьями не превышает 1, а левое и правое поддеревья являются сбалансированным бинарным деревом.
Вопросы о деревьях и больше деревьев.
- KD-дерево: (сокращение от k-мерного дерева) представляет собой структуру данных, которая разделяет k-мерное пространство данных. Он в основном используется при поиске ключевых данных в многомерном пространстве (например, поиск по диапазону и поиск ближайшего соседа). Деревья K-D являются частными случаями деревьев разбиения бинарного пространства.
- Дерево интервалов: Дерево интервалов расширено на основе красно-черного дерева для поддержки операции динамического сбора с интервалом в качестве элемента, в котором ключевое значение каждого узла является левой конечной точкой интервала.
- Дерево Хаффмана: Учитывая n весов в качестве n листовых узлов, постройте бинарное дерево, если длина взвешенного пути достигает минимума, такое бинарное дерево называется оптимальным бинарным деревом, также известным как дерево Хаффмана (Huffman Tree). Дерево Хаффмана — это дерево с наименьшей взвешенной длиной пути, а узел с большим весом находится ближе к корню.
Окончательная упаковка кода
#include <iostream>
#include <queue>
#include <cassert>
using namespace std;
template <typename Key, typename Value>
class BST{
private:
struct Node{
Key key;
Value value;
Node *left;
Node *right;
Node(Key key, Value value){
this->key = key;
this->value = value;
this->left = this->right = NULL;
}
Node(Node *node){
this->key = node->key;
this->value = node->value;
this->left = node->left;
this->right = node->right;
}
};
Node *root;
int count;
public:
BST(){
root = NULL;
count = 0;
}
~BST(){
destroy( root );
}
int size(){
return count;
}
bool isEmpty(){
return count == 0;
}
void insert(Key key, Value value){
root = insert(root, key, value);
}
bool contain(Key key){
return contain(root, key);
}
Value* search(Key key){
return search( root , key );
}
// 前序遍历
void preOrder(){
preOrder(root);
}
// 中序遍历
void inOrder(){
inOrder(root);
}
// 后序遍历
void postOrder(){
postOrder(root);
}
// 层序遍历
void levelOrder(){
queue<Node*> q;
q.push(root);
while( !q.empty() ){
Node *node = q.front();
q.pop();
cout<<node->key<<endl;
if( node->left )
q.push( node->left );
if( node->right )
q.push( node->right );
}
}
// 寻找最小的键值
Key minimum(){
assert( count != 0 );
Node* minNode = minimum( root );
return minNode->key;
}
// 寻找最大的键值
Key maximum(){
assert( count != 0 );
Node* maxNode = maximum(root);
return maxNode->key;
}
// 从二叉树中删除最小值所在节点
void removeMin(){
if( root )
root = removeMin( root );
}
// 从二叉树中删除最大值所在节点
void removeMax(){
if( root )
root = removeMax( root );
}
// 从二叉树中删除键值为key的节点
void remove(Key key){
root = remove(root, key);
}
private:
// 向以node为根的二叉搜索树中,插入节点(key, value)
// 返回插入新节点后的二叉搜索树的根
Node* insert(Node *node, Key key, Value value){
if( node == NULL ){
count ++;
return new Node(key, value);
}
if( key == node->key )
node->value = value;
else if( key < node->key )
node->left = insert( node->left , key, value);
else // key > node->key
node->right = insert( node->right, key, value);
return node;
}
// 查看以node为根的二叉搜索树中是否包含键值为key的节点
bool contain(Node* node, Key key){
if( node == NULL )
return false;
if( key == node->key )
return true;
else if( key < node->key )
return contain( node->left , key );
else // key > node->key
return contain( node->right , key );
}
// 在以node为根的二叉搜索树中查找key所对应的value
Value* search(Node* node, Key key){
if( node == NULL )
return NULL;
if( key == node->key )
return &(node->value);
else if( key < node->key )
return search( node->left , key );
else // key > node->key
return search( node->right, key );
}
// 对以node为根的二叉搜索树进行前序遍历
void preOrder(Node* node){
if( node != NULL ){
cout<<node->key<<endl;
preOrder(node->left);
preOrder(node->right);
}
}
// 对以node为根的二叉搜索树进行中序遍历
void inOrder(Node* node){
if( node != NULL ){
inOrder(node->left);
cout<<node->key<<endl;
inOrder(node->right);
}
}
// 对以node为根的二叉搜索树进行后序遍历
void postOrder(Node* node){
if( node != NULL ){
postOrder(node->left);
postOrder(node->right);
cout<<node->key<<endl;
}
}
void destroy(Node* node){
if( node != NULL ){
destroy( node->left );
destroy( node->right );
delete node;
count --;
}
}
// 在以node为根的二叉搜索树中,返回最小键值的节点
Node* minimum(Node* node){
if( node->left == NULL )
return node;
return minimum(node->left);
}
// 在以node为根的二叉搜索树中,返回最大键值的节点
Node* maximum(Node* node){
if( node->right == NULL )
return node;
return maximum(node->right);
}
// 删除掉以node为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
Node* removeMin(Node* node){
if( node->left == NULL ){
Node* rightNode = node->right;
delete node;
count --;
return rightNode;
}
node->left = removeMin(node->left);
return node;
}
// 删除掉以node为根的二分搜索树中的最大节点
// 返回删除节点后新的二分搜索树的根
Node* removeMax(Node* node){
if( node->right == NULL ){
Node* leftNode = node->left;
delete node;
count --;
return leftNode;
}
node->right = removeMax(node->right);
return node;
}
// 删除掉以node为根的二分搜索树中键值为key的节点
// 返回删除节点后新的二分搜索树的根
Node* remove(Node* node, Key key){
if( node == NULL )
return NULL;
if( key < node->key ){
node->left = remove( node->left , key );
return node;
}
else if( key > node->key ){
node->right = remove( node->right, key );
return node;
}
else{ // key == node->key
if( node->left == NULL ){
Node *rightNode = node->right;
delete node;
count --;
return rightNode;
}
if( node->right == NULL ){
Node *leftNode = node->left;
delete node;
count--;
return leftNode;
}
// node->left != NULL && node->right != NULL
Node *successor = new Node(minimum(node->right));
count ++;
successor->right = removeMin(node->right);
successor->left = node->left;
delete node;
count --;
return successor;
}
}
};
void shuffle( int arr[], int n ){
srand( time(NULL) );
for( int i = n-1 ; i >= 0 ; i -- ){
int x = rand()%(i+1);
swap( arr[i] , arr[x] );
}
}
int main() {
srand(time(NULL));
BST<int,int> bst = BST<int,int>();
int n = 10000;
for( int i = 0 ; i < n ; i ++ ){
int key = rand()%n;
// 为了后续测试方便,这里value值取和key值一样
int value = key;
//cout<<key<<" ";
bst.insert(key,value);
}
// test remove
// remove elements in random order
int order[n];
for( int i = 0 ; i < n ; i ++ )
order[i] = i;
shuffle( order , n );
for( int i = 0 ; i < n ; i ++ )
if( bst.contain( order[i] )){
bst.remove( order[i] );
cout<<"After remove "<<order[i]<<" size = "<<bst.size()<<endl;
}
return 0;
}
------------------------- Великолепная разделительная линия --------------------
Друзья, которые прочитали это, могут нажать «Нравится» / «Подписаться», ваша поддержка — самая большая поддержка для меня.
личный блогСтек томатной технологииа такжеДомашняя страница Наггетс
Если вы хотите узнать больше, обратите внимание на мой публичный аккаунт WeChat: Tomato Technology Stack.