Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 7.4 Двоичное дерево поиска

Как показано на рисунке 7-16, двоичное дерево поиска (binary search tree) удовлетворяет следующим условиям.

1. Для корневого узла все значения в левом поддереве меньше значения корневого узла, а все значения в правом поддереве больше значения корневого узла.
2. Левое и правое поддеревья любого узла также являются двоичными деревьями поиска, то есть тоже удовлетворяют условию `1.` .

Рисунок 7-16 Двоичное дерево поиска

## 7.4.1 Операции с двоичным деревом поиска

Мы инкапсулируем двоичное дерево поиска в класс `BinarySearchTree` и объявляем переменную-член `root` , которая указывает на корневой узел дерева.

### 1. Поиск узла

Для заданного целевого значения узла `num` можно выполнить поиск, опираясь на свойства двоичного дерева поиска. Как показано на рисунке 7-17, мы объявляем узел `cur` , стартуем от корня дерева `root` и циклически сравниваем значения `cur.val` и `num` .

- Если `cur.val < num` , это означает, что целевой узел находится в правом поддереве `cur` , поэтому выполняем `cur = cur.right` .
- Если `cur.val > num` , это означает, что целевой узел находится в левом поддереве `cur` , поэтому выполняем `cur = cur.left` .
- Если `cur.val = num` , это означает, что целевой узел найден, и мы выходим из цикла, возвращая этот узел.

<1><2><3><4>

Рисунок 7-17 Пример поиска узла в двоичном дереве поиска

Операция поиска в двоичном дереве поиска работает по тому же принципу, что и двоичный поиск: на каждом шаге она отбрасывает половину вариантов. Число итераций не превосходит высоты двоичного дерева, а когда дерево сбалансировано, требуется \(O(\log n)\) времени. Пример кода приведен ниже:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
binary_search_tree.py

    def search(self, num: int) -> TreeNode | None:
        """Поиск узла"""
        cur = self._root
        # Искать в цикле и выйти после прохода за листовой узел
        while cur is not None:
            # Целевой узел находится в правом поддереве cur
            if cur.val < num:
                cur = cur.right
            # Целевой узел находится в левом поддереве cur
            elif cur.val > num:
                cur = cur.left
            # Найти целевой узел и выйти из цикла
            else:
                break
        return cur

binary_search_tree.cpp

    /* Поиск узла */
    TreeNode *search(int num) {
        TreeNode *cur = root;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur != nullptr) {
            // Целевой узел находится в правом поддереве cur
            if (cur->val < num)
                cur = cur->right;
            // Целевой узел находится в левом поддереве cur
            else if (cur->val > num)
                cur = cur->left;
            // Найти целевой узел и выйти из цикла
            else
                break;
        }
        // Вернуть целевой узел
        return cur;
    }

binary_search_tree.java

    /* Поиск узла */
    TreeNode search(int num) {
        TreeNode cur = root;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur != null) {
            // Целевой узел находится в правом поддереве cur
            if (cur.val < num)
                cur = cur.right;
            // Целевой узел находится в левом поддереве cur
            else if (cur.val > num)
                cur = cur.left;
            // Найти целевой узел и выйти из цикла
            else
                break;
        }
        // Вернуть целевой узел
        return cur;
    }

binary_search_tree.cs

    /* Поиск узла */
    TreeNode? Search(int num) {
        TreeNode? cur = root;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur != null) {
            // Целевой узел находится в правом поддереве cur
            if (cur.val < num) cur =
                cur.right;
            // Целевой узел находится в левом поддереве cur
            else if (cur.val > num)
                cur = cur.left;
            // Найти целевой узел и выйти из цикла
            else
                break;
        }
        // Вернуть целевой узел
        return cur;
    }

binary_search_tree.go

    /* Поиск узла */
    func (bst *binarySearchTree) search(num int) *TreeNode {
        node := bst.root
        // Искать в цикле и выйти после прохода за листовой узел
        for node != nil {
            if node.Val.(int) < num {
                // Целевой узел находится в правом поддереве cur
                node = node.Right
            } else if node.Val.(int) > num {
                // Целевой узел находится в левом поддереве cur
                node = node.Left
            } else {
                // Найти целевой узел и выйти из цикла
                break
            }
        }
        // Вернуть целевой узел
        return node
    }

binary_search_tree.swift

    /* Поиск узла */
    func search(num: Int) -> TreeNode? {
        var cur = root
        // Искать в цикле и выйти после прохода за листовой узел
        while cur != nil {
            // Целевой узел находится в правом поддереве cur
            if cur!.val < num {
                cur = cur?.right
            }
            // Целевой узел находится в левом поддереве cur
            else if cur!.val > num {
                cur = cur?.left
            }
            // Найти целевой узел и выйти из цикла
            else {
                break
            }
        }
        // Вернуть целевой узел
        return cur
    }

binary_search_tree.js

    /* Поиск узла */
    search(num) {
        let cur = this.root;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur !== null) {
            // Целевой узел находится в правом поддереве cur
            if (cur.val < num) cur = cur.right;
            // Целевой узел находится в левом поддереве cur
            else if (cur.val > num) cur = cur.left;
            // Найти целевой узел и выйти из цикла
            else break;
        }
        // Вернуть целевой узел
        return cur;
    }

binary_search_tree.ts

    /* Поиск узла */
    search(num: number): TreeNode | null {
        let cur = this.root;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur !== null) {
            // Целевой узел находится в правом поддереве cur
            if (cur.val < num) cur = cur.right;
            // Целевой узел находится в левом поддереве cur
            else if (cur.val > num) cur = cur.left;
            // Найти целевой узел и выйти из цикла
            else break;
        }
        // Вернуть целевой узел
        return cur;
    }

binary_search_tree.dart

    /* Поиск узла */
    TreeNode? search(int _num) {
      TreeNode? cur = _root;
      // Искать в цикле и выйти после прохода за листовой узел
      while (cur != null) {
        // Целевой узел находится в правом поддереве cur
        if (cur.val < _num)
          cur = cur.right;
        // Целевой узел находится в левом поддереве cur
        else if (cur.val > _num)
          cur = cur.left;
        // Найти целевой узел и выйти из цикла
        else
          break;
      }
      // Вернуть целевой узел
      return cur;
    }

binary_search_tree.rs

    /* Поиск узла */
    pub fn search(&self, num: i32) -> OptionTreeNodeRc {
        let mut cur = self.root.clone();
        // Искать в цикле и выйти после прохода за листовой узел
        while let Some(node) = cur.clone() {
            match num.cmp(&node.borrow().val) {
                // Целевой узел находится в правом поддереве cur
                Ordering::Greater => cur = node.borrow().right.clone(),
                // Целевой узел находится в левом поддереве cur
                Ordering::Less => cur = node.borrow().left.clone(),
                // Найти целевой узел и выйти из цикла
                Ordering::Equal => break,
            }
        }

        // Вернуть целевой узел
        cur
    }

binary_search_tree.c

    /* Поиск узла */
    TreeNode *search(BinarySearchTree *bst, int num) {
        TreeNode *cur = bst->root;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur != NULL) {
            if (cur->val < num) {
                // Целевой узел находится в правом поддереве cur
                cur = cur->right;
            } else if (cur->val > num) {
                // Целевой узел находится в левом поддереве cur
                cur = cur->left;
            } else {
                // Найти целевой узел и выйти из цикла
                break;
            }
        }
        // Вернуть целевой узел
        return cur;
    }

binary_search_tree.kt

    /* Поиск узла */
    fun search(num: Int): TreeNode? {
        var cur = root
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur != null) {
            // Целевой узел находится в правом поддереве cur
            cur = if (cur._val < num)
                cur.right
            // Целевой узел находится в левом поддереве cur
            else if (cur._val > num)
                cur.left
            // Найти целевой узел и выйти из цикла
            else
                break
        }
        // Вернуть целевой узел
        return cur
    }

binary_search_tree.rb

    ### Поиск узла ###
    def search(num)
      cur = @root

      # Искать в цикле и выйти после прохода за листовой узел
      while !cur.nil?
        # Целевой узел находится в правом поддереве cur
        if cur.val < num
          cur = cur.right
        # Целевой узел находится в левом поддереве cur
        elsif cur.val > num
          cur = cur.left
        # Найти целевой узел и выйти из цикла
        else
          break
        end
      end

      cur
    end

Визуализация кода

Во весь экран >

### 2. Вставка узла

Пусть дан элемент `num` , который нужно вставить. Чтобы сохранить свойство двоичного дерева поиска «левое поддерево < корень < правое поддерево», процесс вставки показан на рисунке 7-18.

1. Найти позицию для вставки: как и в операции поиска, начиная от корня, мы циклически спускаемся вниз в зависимости от соотношения между текущим значением узла и `num` , пока не выйдем за листовой узел (то есть не дойдем до `None` ).
2. Вставить узел в найденную позицию: инициализировать узел `num` и поставить его на место этого `None` .

Рисунок 7-18 Вставка узла в двоичное дерево поиска

В реализации кода нужно обратить внимание на следующие два момента.

- Двоичное дерево поиска не допускает дублирующихся узлов, иначе его определение будет нарушено. Поэтому если вставляемый узел уже существует в дереве, вставка не выполняется и функция сразу возвращается.
- Чтобы реализовать вставку, нам нужно использовать узел `pre` для сохранения узла предыдущей итерации цикла. Тогда, когда обход дойдет до `None` , мы сможем получить его родителя и завершить вставку.

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
binary_search_tree.py

    def insert(self, num: int):
        """Вставка узла"""
        # Если дерево пусто, инициализировать корневой узел
        if self._root is None:
            self._root = TreeNode(num)
            return
        # Искать в цикле и выйти после прохода за листовой узел
        cur, pre = self._root, None
        while cur is not None:
            # Найти повторяющийся узел и сразу вернуть
            if cur.val == num:
                return
            pre = cur
            # Позиция вставки находится в правом поддереве cur
            if cur.val < num:
                cur = cur.right
            # Позиция вставки находится в левом поддереве cur
            else:
                cur = cur.left
        # Вставка узла
        node = TreeNode(num)
        if pre.val < num:
            pre.right = node
        else:
            pre.left = node

binary_search_tree.cpp

    /* Вставка узла */
    void insert(int num) {
        // Если дерево пусто, инициализировать корневой узел
        if (root == nullptr) {
            root = new TreeNode(num);
            return;
        }
        TreeNode *cur = root, *pre = nullptr;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur != nullptr) {
            // Найти повторяющийся узел и сразу вернуть
            if (cur->val == num)
                return;
            pre = cur;
            // Позиция вставки находится в правом поддереве cur
            if (cur->val < num)
                cur = cur->right;
            // Позиция вставки находится в левом поддереве cur
            else
                cur = cur->left;
        }
        // Вставка узла
        TreeNode *node = new TreeNode(num);
        if (pre->val < num)
            pre->right = node;
        else
            pre->left = node;
    }

binary_search_tree.java

    /* Вставка узла */
    void insert(int num) {
        // Если дерево пусто, инициализировать корневой узел
        if (root == null) {
            root = new TreeNode(num);
            return;
        }
        TreeNode cur = root, pre = null;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur != null) {
            // Найти повторяющийся узел и сразу вернуть
            if (cur.val == num)
                return;
            pre = cur;
            // Позиция вставки находится в правом поддереве cur
            if (cur.val < num)
                cur = cur.right;
            // Позиция вставки находится в левом поддереве cur
            else
                cur = cur.left;
        }
        // Вставка узла
        TreeNode node = new TreeNode(num);
        if (pre.val < num)
            pre.right = node;
        else
            pre.left = node;
    }

binary_search_tree.cs

    /* Вставка узла */
    void Insert(int num) {
        // Если дерево пусто, инициализировать корневой узел
        if (root == null) {
            root = new TreeNode(num);
            return;
        }
        TreeNode? cur = root, pre = null;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur != null) {
            // Найти повторяющийся узел и сразу вернуть
            if (cur.val == num)
                return;
            pre = cur;
            // Позиция вставки находится в правом поддереве cur
            if (cur.val < num)
                cur = cur.right;
            // Позиция вставки находится в левом поддереве cur
            else
                cur = cur.left;
        }

        // Вставка узла
        TreeNode node = new(num);
        if (pre != null) {
            if (pre.val < num)
                pre.right = node;
            else
                pre.left = node;
        }
    }

binary_search_tree.go

    /* Вставка узла */
    func (bst *binarySearchTree) insert(num int) {
        cur := bst.root
        // Если дерево пусто, инициализировать корневой узел
        if cur == nil {
            bst.root = NewTreeNode(num)
            return
        }
        // Позиция узла, предшествующего вставляемому
        var pre *TreeNode = nil
        // Искать в цикле и выйти после прохода за листовой узел
        for cur != nil {
            if cur.Val == num {
                return
            }
            pre = cur
            if cur.Val.(int) < num {
                cur = cur.Right
            } else {
                cur = cur.Left
            }
        }
        // Вставка узла
        node := NewTreeNode(num)
        if pre.Val.(int) < num {
            pre.Right = node
        } else {
            pre.Left = node
        }
    }

binary_search_tree.swift

    /* Вставка узла */
    func insert(num: Int) {
        // Если дерево пусто, инициализировать корневой узел
        if root == nil {
            root = TreeNode(x: num)
            return
        }
        var cur = root
        var pre: TreeNode?
        // Искать в цикле и выйти после прохода за листовой узел
        while cur != nil {
            // Найти повторяющийся узел и сразу вернуть
            if cur!.val == num {
                return
            }
            pre = cur
            // Позиция вставки находится в правом поддереве cur
            if cur!.val < num {
                cur = cur?.right
            }
            // Позиция вставки находится в левом поддереве cur
            else {
                cur = cur?.left
            }
        }
        // Вставка узла
        let node = TreeNode(x: num)
        if pre!.val < num {
            pre?.right = node
        } else {
            pre?.left = node
        }
    }

binary_search_tree.js

    /* Вставка узла */
    insert(num) {
        // Если дерево пусто, инициализировать корневой узел
        if (this.root === null) {
            this.root = new TreeNode(num);
            return;
        }
        let cur = this.root,
            pre = null;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur !== null) {
            // Найти повторяющийся узел и сразу вернуть
            if (cur.val === num) return;
            pre = cur;
            // Позиция вставки находится в правом поддереве cur
            if (cur.val < num) cur = cur.right;
            // Позиция вставки находится в левом поддереве cur
            else cur = cur.left;
        }
        // Вставка узла
        const node = new TreeNode(num);
        if (pre.val < num) pre.right = node;
        else pre.left = node;
    }

binary_search_tree.ts

    /* Вставка узла */
    insert(num: number): void {
        // Если дерево пусто, инициализировать корневой узел
        if (this.root === null) {
            this.root = new TreeNode(num);
            return;
        }
        let cur: TreeNode | null = this.root,
            pre: TreeNode | null = null;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur !== null) {
            // Найти повторяющийся узел и сразу вернуть
            if (cur.val === num) return;
            pre = cur;
            // Позиция вставки находится в правом поддереве cur
            if (cur.val < num) cur = cur.right;
            // Позиция вставки находится в левом поддереве cur
            else cur = cur.left;
        }
        // Вставка узла
        const node = new TreeNode(num);
        if (pre!.val < num) pre!.right = node;
        else pre!.left = node;
    }

binary_search_tree.dart

    /* Вставка узла */
    void insert(int _num) {
      // Если дерево пусто, инициализировать корневой узел
      if (_root == null) {
        _root = TreeNode(_num);
        return;
      }
      TreeNode? cur = _root;
      TreeNode? pre = null;
      // Искать в цикле и выйти после прохода за листовой узел
      while (cur != null) {
        // Найти повторяющийся узел и сразу вернуть
        if (cur.val == _num) return;
        pre = cur;
        // Позиция вставки находится в правом поддереве cur
        if (cur.val < _num)
          cur = cur.right;
        // Позиция вставки находится в левом поддереве cur
        else
          cur = cur.left;
      }
      // Вставка узла
      TreeNode? node = TreeNode(_num);
      if (pre!.val < _num)
        pre.right = node;
      else
        pre.left = node;
    }

binary_search_tree.rs

    /* Вставка узла */
    pub fn insert(&mut self, num: i32) {
        // Если дерево пусто, инициализировать корневой узел
        if self.root.is_none() {
            self.root = Some(TreeNode::new(num));
            return;
        }
        let mut cur = self.root.clone();
        let mut pre = None;
        // Искать в цикле и выйти после прохода за листовой узел
        while let Some(node) = cur.clone() {
            match num.cmp(&node.borrow().val) {
                // Найти повторяющийся узел и сразу вернуть
                Ordering::Equal => return,
                // Позиция вставки находится в правом поддереве cur
                Ordering::Greater => {
                    pre = cur.clone();
                    cur = node.borrow().right.clone();
                }
                // Позиция вставки находится в левом поддереве cur
                Ordering::Less => {
                    pre = cur.clone();
                    cur = node.borrow().left.clone();
                }
            }
        }
        // Вставка узла
        let pre = pre.unwrap();
        let node = Some(TreeNode::new(num));
        if num > pre.borrow().val {
            pre.borrow_mut().right = node;
        } else {
            pre.borrow_mut().left = node;
        }
    }

binary_search_tree.c

    /* Вставка узла */
    void insert(BinarySearchTree *bst, int num) {
        // Если дерево пусто, инициализировать корневой узел
        if (bst->root == NULL) {
            bst->root = newTreeNode(num);
            return;
        }
        TreeNode *cur = bst->root, *pre = NULL;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur != NULL) {
            // Найти повторяющийся узел и сразу вернуть
            if (cur->val == num) {
                return;
            }
            pre = cur;
            if (cur->val < num) {
                // Позиция вставки находится в правом поддереве cur
                cur = cur->right;
            } else {
                // Позиция вставки находится в левом поддереве cur
                cur = cur->left;
            }
        }
        // Вставка узла
        TreeNode *node = newTreeNode(num);
        if (pre->val < num) {
            pre->right = node;
        } else {
            pre->left = node;
        }
    }

binary_search_tree.kt

    /* Вставка узла */
    fun insert(num: Int) {
        // Если дерево пусто, инициализировать корневой узел
        if (root == null) {
            root = TreeNode(num)
            return
        }
        var cur = root
        var pre: TreeNode? = null
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur != null) {
            // Найти повторяющийся узел и сразу вернуть
            if (cur._val == num)
                return
            pre = cur
            // Позиция вставки находится в правом поддереве cur
            cur = if (cur._val < num)
                cur.right
            // Позиция вставки находится в левом поддереве cur
            else
                cur.left
        }
        // Вставка узла
        val node = TreeNode(num)
        if (pre?._val!! < num)
            pre.right = node
        else
            pre.left = node
    }

binary_search_tree.rb

    ### Вставка узла ###
    def insert(num)
      # Если дерево пусто, инициализировать корневой узел
      if @root.nil?
        @root = TreeNode.new(num)
        return
      end

      # Искать в цикле и выйти после прохода за листовой узел
      cur, pre = @root, nil
      while !cur.nil?
        # Найти повторяющийся узел и сразу вернуть
        return if cur.val == num

        pre = cur
        # Позиция вставки находится в правом поддереве cur
        if cur.val < num
          cur = cur.right
        # Позиция вставки находится в левом поддереве cur
        else
          cur = cur.left
        end
      end

      # Вставка узла
      node = TreeNode.new(num)
      if pre.val < num
        pre.right = node
      else
        pre.left = node
      end
    end

Визуализация кода

Во весь экран >

Как и поиск узла, вставка узла требует \(O(\log n)\) времени.

### 3. Удаление узла

Сначала нужно найти в двоичном дереве целевой узел, а затем удалить его. Как и при вставке, после удаления необходимо сохранить свойство двоичного дерева поиска: «левое поддерево < корень < правое поддерево». Поэтому в зависимости от числа дочерних узлов у удаляемого узла, то есть для случаев со степенью 0, 1 и 2, выполняются разные операции удаления.

Как показано на рисунке 7-19, когда степень удаляемого узла равна \(0\) , это значит, что узел является листом и может быть удален напрямую.

Рисунок 7-19 Удаление узла в двоичном дереве поиска (степень 0)

Как показано на рисунке 7-20, когда степень удаляемого узла равна \(1\) , достаточно заменить удаляемый узел его дочерним узлом.

Рисунок 7-20 Удаление узла в двоичном дереве поиска (степень 1)

Когда степень удаляемого узла равна \(2\) , мы уже не можем удалить его напрямую и должны использовать для замены другой узел. Чтобы сохранить свойство двоичного дерева поиска «левое поддерево \(<\) корень \(<\) правое поддерево», этим узлом может быть минимальный узел правого поддерева или максимальный узел левого поддерева.

Предположим, мы выбираем минимальный узел правого поддерева, то есть следующий узел в симметричном обходе. Тогда процесс удаления показан на рисунке 7-21.

1. Найти следующий узел в «последовательности симметричного обхода» для удаляемого узла и обозначить его как `tmp` .
2. Значением `tmp` перезаписать значение удаляемого узла, а затем рекурсивно удалить узел `tmp` из дерева.

<1><2><3><4>

Рисунок 7-21 Удаление узла в двоичном дереве поиска (степень 2)

Операция удаления узла также требует \(O(\log n)\) времени, где поиск удаляемого узла стоит \(O(\log n)\) , а получение следующего узла симметричного обхода также требует \(O(\log n)\) . Пример кода приведен ниже:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
binary_search_tree.py

    def remove(self, num: int):
        """Удаление узла"""
        # Если дерево пусто, сразу вернуть
        if self._root is None:
            return
        # Искать в цикле и выйти после прохода за листовой узел
        cur, pre = self._root, None
        while cur is not None:
            # Найти узел для удаления и выйти из цикла
            if cur.val == num:
                break
            pre = cur
            # Узел для удаления находится в правом поддереве cur
            if cur.val < num:
                cur = cur.right
            # Узел для удаления находится в левом поддереве cur
            else:
                cur = cur.left
        # Если узел для удаления отсутствует, сразу вернуть
        if cur is None:
            return

        # Число дочерних узлов = 0 или 1
        if cur.left is None or cur.right is None:
            # Когда число дочерних узлов = 0 / 1, child = null / этот дочерний узел
            child = cur.left or cur.right
            # Удалить узел cur
            if cur != self._root:
                if pre.left == cur:
                    pre.left = child
                else:
                    pre.right = child
            else:
                # Если удаляемый узел является корнем, заново назначить корневой узел
                self._root = child
        # Число дочерних узлов = 2
        else:
            # Получить следующий узел после cur в симметричном обходе
            tmp: TreeNode = cur.right
            while tmp.left is not None:
                tmp = tmp.left
            # Рекурсивно удалить узел tmp
            self.remove(tmp.val)
            # Перезаписать cur значением tmp
            cur.val = tmp.val

binary_search_tree.cpp

    /* Удаление узла */
    void remove(int num) {
        // Если дерево пусто, сразу вернуть
        if (root == nullptr)
            return;
        TreeNode *cur = root, *pre = nullptr;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur != nullptr) {
            // Найти узел для удаления и выйти из цикла
            if (cur->val == num)
                break;
            pre = cur;
            // Узел для удаления находится в правом поддереве cur
            if (cur->val < num)
                cur = cur->right;
            // Узел для удаления находится в левом поддереве cur
            else
                cur = cur->left;
        }
        // Если узел для удаления отсутствует, сразу вернуть
        if (cur == nullptr)
            return;
        // Число дочерних узлов = 0 или 1
        if (cur->left == nullptr || cur->right == nullptr) {
            // Когда число дочерних узлов = 0 / 1, child = nullptr / этот дочерний узел
            TreeNode *child = cur->left != nullptr ? cur->left : cur->right;
            // Удалить узел cur
            if (cur != root) {
                if (pre->left == cur)
                    pre->left = child;
                else
                    pre->right = child;
            } else {
                // Если удаляемый узел является корнем, заново назначить корневой узел
                root = child;
            }
            // Освободить память
            delete cur;
        }
        // Число дочерних узлов = 2
        else {
            // Получить следующий узел после cur в симметричном обходе
            TreeNode *tmp = cur->right;
            while (tmp->left != nullptr) {
                tmp = tmp->left;
            }
            int tmpVal = tmp->val;
            // Рекурсивно удалить узел tmp
            remove(tmp->val);
            // Перезаписать cur значением tmp
            cur->val = tmpVal;
        }
    }

binary_search_tree.java

    /* Удаление узла */
    void remove(int num) {
        // Если дерево пусто, сразу вернуть
        if (root == null)
            return;
        TreeNode cur = root, pre = null;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur != null) {
            // Найти узел для удаления и выйти из цикла
            if (cur.val == num)
                break;
            pre = cur;
            // Узел для удаления находится в правом поддереве cur
            if (cur.val < num)
                cur = cur.right;
            // Узел для удаления находится в левом поддереве cur
            else
                cur = cur.left;
        }
        // Если узел для удаления отсутствует, сразу вернуть
        if (cur == null)
            return;
        // Число дочерних узлов = 0 или 1
        if (cur.left == null || cur.right == null) {
            // Когда число дочерних узлов = 0 / 1, child = null / этот дочерний узел
            TreeNode child = cur.left != null ? cur.left : cur.right;
            // Удалить узел cur
            if (cur != root) {
                if (pre.left == cur)
                    pre.left = child;
                else
                    pre.right = child;
            } else {
                // Если удаляемый узел является корнем, заново назначить корневой узел
                root = child;
            }
        }
        // Число дочерних узлов = 2
        else {
            // Получить следующий узел после cur в симметричном обходе
            TreeNode tmp = cur.right;
            while (tmp.left != null) {
                tmp = tmp.left;
            }
            // Рекурсивно удалить узел tmp
            remove(tmp.val);
            // Перезаписать cur значением tmp
            cur.val = tmp.val;
        }
    }

binary_search_tree.cs

    /* Удаление узла */
    void Remove(int num) {
        // Если дерево пусто, сразу вернуть
        if (root == null)
            return;
        TreeNode? cur = root, pre = null;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur != null) {
            // Найти узел для удаления и выйти из цикла
            if (cur.val == num)
                break;
            pre = cur;
            // Узел для удаления находится в правом поддереве cur
            if (cur.val < num)
                cur = cur.right;
            // Узел для удаления находится в левом поддереве cur
            else
                cur = cur.left;
        }
        // Если узел для удаления отсутствует, сразу вернуть
        if (cur == null)
            return;
        // Число дочерних узлов = 0 или 1
        if (cur.left == null || cur.right == null) {
            // Когда число дочерних узлов = 0 / 1, child = null / этот дочерний узел
            TreeNode? child = cur.left ?? cur.right;
            // Удалить узел cur
            if (cur != root) {
                if (pre!.left == cur)
                    pre.left = child;
                else
                    pre.right = child;
            } else {
                // Если удаляемый узел является корнем, заново назначить корневой узел
                root = child;
            }
        }
        // Число дочерних узлов = 2
        else {
            // Получить следующий узел после cur в симметричном обходе
            TreeNode? tmp = cur.right;
            while (tmp.left != null) {
                tmp = tmp.left;
            }
            // Рекурсивно удалить узел tmp
            Remove(tmp.val!.Value);
            // Перезаписать cur значением tmp
            cur.val = tmp.val;
        }
    }

binary_search_tree.go

    /* Удаление узла */
    func (bst *binarySearchTree) remove(num int) {
        cur := bst.root
        // Если дерево пусто, сразу вернуть
        if cur == nil {
            return
        }
        // Позиция узла, предшествующего удаляемому
        var pre *TreeNode = nil
        // Искать в цикле и выйти после прохода за листовой узел
        for cur != nil {
            if cur.Val == num {
                break
            }
            pre = cur
            if cur.Val.(int) < num {
                // Удаляемый узел находится в правом поддереве
                cur = cur.Right
            } else {
                // Удаляемый узел находится в левом поддереве
                cur = cur.Left
            }
        }
        // Если узел для удаления отсутствует, сразу вернуть
        if cur == nil {
            return
        }
        // Число дочерних узлов равно 0 или 1
        if cur.Left == nil || cur.Right == nil {
            var child *TreeNode = nil
            // Извлечь дочерний узел удаляемого узла
            if cur.Left != nil {
                child = cur.Left
            } else {
                child = cur.Right
            }
            // Удалить узел cur
            if cur != bst.root {
                if pre.Left == cur {
                    pre.Left = child
                } else {
                    pre.Right = child
                }
            } else {
                // Если удаляемый узел является корнем, заново назначить корневой узел
                bst.root = child
            }
            // Число дочерних узлов равно 2
        } else {
            // Получить следующий после cur узел в симметричном обходе для удаляемого узла
            tmp := cur.Right
            for tmp.Left != nil {
                tmp = tmp.Left
            }
            // Рекурсивно удалить узел tmp
            bst.remove(tmp.Val.(int))
            // Перезаписать cur значением tmp
            cur.Val = tmp.Val
        }
    }

binary_search_tree.swift

    /* Удаление узла */
    func remove(num: Int) {
        // Если дерево пусто, сразу вернуть
        if root == nil {
            return
        }
        var cur = root
        var pre: TreeNode?
        // Искать в цикле и выйти после прохода за листовой узел
        while cur != nil {
            // Найти узел для удаления и выйти из цикла
            if cur!.val == num {
                break
            }
            pre = cur
            // Узел для удаления находится в правом поддереве cur
            if cur!.val < num {
                cur = cur?.right
            }
            // Узел для удаления находится в левом поддереве cur
            else {
                cur = cur?.left
            }
        }
        // Если узел для удаления отсутствует, сразу вернуть
        if cur == nil {
            return
        }
        // Число дочерних узлов = 0 или 1
        if cur?.left == nil || cur?.right == nil {
            // Когда число дочерних узлов = 0 / 1, child = null / этот дочерний узел
            let child = cur?.left ?? cur?.right
            // Удалить узел cur
            if cur !== root {
                if pre?.left === cur {
                    pre?.left = child
                } else {
                    pre?.right = child
                }
            } else {
                // Если удаляемый узел является корнем, заново назначить корневой узел
                root = child
            }
        }
        // Число дочерних узлов = 2
        else {
            // Получить следующий узел после cur в симметричном обходе
            var tmp = cur?.right
            while tmp?.left != nil {
                tmp = tmp?.left
            }
            // Рекурсивно удалить узел tmp
            remove(num: tmp!.val)
            // Перезаписать cur значением tmp
            cur?.val = tmp!.val
        }
    }

binary_search_tree.js

    /* Удаление узла */
    remove(num) {
        // Если дерево пусто, сразу вернуть
        if (this.root === null) return;
        let cur = this.root,
            pre = null;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur !== null) {
            // Найти узел для удаления и выйти из цикла
            if (cur.val === num) break;
            pre = cur;
            // Узел для удаления находится в правом поддереве cur
            if (cur.val < num) cur = cur.right;
            // Узел для удаления находится в левом поддереве cur
            else cur = cur.left;
        }
        // Если узел для удаления отсутствует, сразу вернуть
        if (cur === null) return;
        // Число дочерних узлов = 0 или 1
        if (cur.left === null || cur.right === null) {
            // Когда число дочерних узлов = 0 / 1, child = null / этот дочерний узел
            const child = cur.left !== null ? cur.left : cur.right;
            // Удалить узел cur
            if (cur !== this.root) {
                if (pre.left === cur) pre.left = child;
                else pre.right = child;
            } else {
                // Если удаляемый узел является корнем, заново назначить корневой узел
                this.root = child;
            }
        }
        // Число дочерних узлов = 2
        else {
            // Получить следующий узел после cur в симметричном обходе
            let tmp = cur.right;
            while (tmp.left !== null) {
                tmp = tmp.left;
            }
            // Рекурсивно удалить узел tmp
            this.remove(tmp.val);
            // Перезаписать cur значением tmp
            cur.val = tmp.val;
        }
    }

binary_search_tree.ts

    /* Удаление узла */
    remove(num: number): void {
        // Если дерево пусто, сразу вернуть
        if (this.root === null) return;
        let cur: TreeNode | null = this.root,
            pre: TreeNode | null = null;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur !== null) {
            // Найти узел для удаления и выйти из цикла
            if (cur.val === num) break;
            pre = cur;
            // Узел для удаления находится в правом поддереве cur
            if (cur.val < num) cur = cur.right;
            // Узел для удаления находится в левом поддереве cur
            else cur = cur.left;
        }
        // Если узел для удаления отсутствует, сразу вернуть
        if (cur === null) return;
        // Число дочерних узлов = 0 или 1
        if (cur.left === null || cur.right === null) {
            // Когда число дочерних узлов = 0 / 1, child = null / этот дочерний узел
            const child: TreeNode | null =
                cur.left !== null ? cur.left : cur.right;
            // Удалить узел cur
            if (cur !== this.root) {
                if (pre!.left === cur) pre!.left = child;
                else pre!.right = child;
            } else {
                // Если удаляемый узел является корнем, заново назначить корневой узел
                this.root = child;
            }
        }
        // Число дочерних узлов = 2
        else {
            // Получить следующий узел после cur в симметричном обходе
            let tmp: TreeNode | null = cur.right;
            while (tmp!.left !== null) {
                tmp = tmp!.left;
            }
            // Рекурсивно удалить узел tmp
            this.remove(tmp!.val);
            // Перезаписать cur значением tmp
            cur.val = tmp!.val;
        }
    }

binary_search_tree.dart

    /* Удаление узла */
    void remove(int _num) {
      // Если дерево пусто, сразу вернуть
      if (_root == null) return;
      TreeNode? cur = _root;
      TreeNode? pre = null;
      // Искать в цикле и выйти после прохода за листовой узел
      while (cur != null) {
        // Найти узел для удаления и выйти из цикла
        if (cur.val == _num) break;
        pre = cur;
        // Узел для удаления находится в правом поддереве cur
        if (cur.val < _num)
          cur = cur.right;
        // Узел для удаления находится в левом поддереве cur
        else
          cur = cur.left;
      }
      // Если удаляемого узла нет, сразу вернуть
      if (cur == null) return;
      // Число дочерних узлов = 0 или 1
      if (cur.left == null || cur.right == null) {
        // Когда число дочерних узлов = 0 / 1, child = null / этот дочерний узел
        TreeNode? child = cur.left ?? cur.right;
        // Удалить узел cur
        if (cur != _root) {
          if (pre!.left == cur)
            pre.left = child;
          else
            pre.right = child;
        } else {
          // Если удаляемый узел является корнем, заново назначить корневой узел
          _root = child;
        }
      } else {
        // Число дочерних узлов = 2
        // Получить следующий узел после cur в симметричном обходе
        TreeNode? tmp = cur.right;
        while (tmp!.left != null) {
          tmp = tmp.left;
        }
        // Рекурсивно удалить узел tmp
        remove(tmp.val);
        // Перезаписать cur значением tmp
        cur.val = tmp.val;
      }
    }

binary_search_tree.rs

    /* Удаление узла */
    pub fn remove(&mut self, num: i32) {
        // Если дерево пусто, сразу вернуть
        if self.root.is_none() {
            return;
        }
        let mut cur = self.root.clone();
        let mut pre = None;
        // Искать в цикле и выйти после прохода за листовой узел
        while let Some(node) = cur.clone() {
            match num.cmp(&node.borrow().val) {
                // Найти узел для удаления и выйти из цикла
                Ordering::Equal => break,
                // Узел для удаления находится в правом поддереве cur
                Ordering::Greater => {
                    pre = cur.clone();
                    cur = node.borrow().right.clone();
                }
                // Узел для удаления находится в левом поддереве cur
                Ordering::Less => {
                    pre = cur.clone();
                    cur = node.borrow().left.clone();
                }
            }
        }
        // Если узел для удаления отсутствует, сразу вернуть
        if cur.is_none() {
            return;
        }
        let cur = cur.unwrap();
        let (left_child, right_child) = (cur.borrow().left.clone(), cur.borrow().right.clone());
        match (left_child.clone(), right_child.clone()) {
            // Число дочерних узлов = 0 или 1
            (None, None) | (Some(_), None) | (None, Some(_)) => {
                // Когда число дочерних узлов = 0 / 1, child = nullptr / этот дочерний узел
                let child = left_child.or(right_child);
                let pre = pre.unwrap();
                // Удалить узел cur
                if !Rc::ptr_eq(&cur, self.root.as_ref().unwrap()) {
                    let left = pre.borrow().left.clone();
                    if left.is_some() && Rc::ptr_eq(left.as_ref().unwrap(), &cur) {
                        pre.borrow_mut().left = child;
                    } else {
                        pre.borrow_mut().right = child;
                    }
                } else {
                    // Если удаляемый узел является корнем, заново назначить корневой узел
                    self.root = child;
                }
            }
            // Число дочерних узлов = 2
            (Some(_), Some(_)) => {
                // Получить следующий узел после cur в симметричном обходе
                let mut tmp = cur.borrow().right.clone();
                while let Some(node) = tmp.clone() {
                    if node.borrow().left.is_some() {
                        tmp = node.borrow().left.clone();
                    } else {
                        break;
                    }
                }
                let tmp_val = tmp.unwrap().borrow().val;
                // Рекурсивно удалить узел tmp
                self.remove(tmp_val);
                // Перезаписать cur значением tmp
                cur.borrow_mut().val = tmp_val;
            }
        }
    }

binary_search_tree.c

    /* Удаление узла */
    // Из-за подключения stdio.h здесь нельзя использовать ключевое слово remove
    void removeItem(BinarySearchTree *bst, int num) {
        // Если дерево пусто, сразу вернуть
        if (bst->root == NULL)
            return;
        TreeNode *cur = bst->root, *pre = NULL;
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur != NULL) {
            // Найти узел для удаления и выйти из цикла
            if (cur->val == num)
                break;
            pre = cur;
            if (cur->val < num) {
                // Удаляемый узел находится в правом поддереве root
                cur = cur->right;
            } else {
                // Удаляемый узел находится в левом поддереве root
                cur = cur->left;
            }
        }
        // Если узел для удаления отсутствует, сразу вернуть
        if (cur == NULL)
            return;
        // Проверить, есть ли дочерние узлы у удаляемого узла
        if (cur->left == NULL || cur->right == NULL) {
            /* Число дочерних узлов = 0 или 1 */
            // Когда число дочерних узлов = 0 / 1, child = nullptr / этот дочерний узел
            TreeNode *child = cur->left != NULL ? cur->left : cur->right;
            // Удалить узел cur
            if (pre->left == cur) {
                pre->left = child;
            } else {
                pre->right = child;
            }
            // Освободить память
            free(cur);
        } else {
            /* Число дочерних узлов = 2 */
            // Получить следующий узел после cur в симметричном обходе
            TreeNode *tmp = cur->right;
            while (tmp->left != NULL) {
                tmp = tmp->left;
            }
            int tmpVal = tmp->val;
            // Рекурсивно удалить узел tmp
            removeItem(bst, tmp->val);
            // Перезаписать cur значением tmp
            cur->val = tmpVal;
        }
    }

binary_search_tree.kt

    /* Удаление узла */
    fun remove(num: Int) {
        // Если дерево пусто, сразу вернуть
        if (root == null)
            return
        var cur = root
        var pre: TreeNode? = null
        // Искать в цикле и выйти после прохода за листовой узел
        while (cur != null) {
            // Найти узел для удаления и выйти из цикла
            if (cur._val == num)
                break
            pre = cur
            // Узел для удаления находится в правом поддереве cur
            cur = if (cur._val < num)
                cur.right
            // Узел для удаления находится в левом поддереве cur
            else
                cur.left
        }
        // Если узел для удаления отсутствует, сразу вернуть
        if (cur == null)
            return
        // Число дочерних узлов = 0 или 1
        if (cur.left == null || cur.right == null) {
            // Когда число дочерних узлов = 0 / 1, child = null / этот дочерний узел
            val child = if (cur.left != null)
                cur.left
            else
                cur.right
            // Удалить узел cur
            if (cur != root) {
                if (pre!!.left == cur)
                    pre.left = child
                else
                    pre.right = child
            } else {
                // Если удаляемый узел является корнем, заново назначить корневой узел
                root = child
            }
            // Число дочерних узлов = 2
        } else {
            // Получить следующий узел после cur в симметричном обходе
            var tmp = cur.right
            while (tmp!!.left != null) {
                tmp = tmp.left
            }
            // Рекурсивно удалить узел tmp
            remove(tmp._val)
            // Перезаписать cur значением tmp
            cur._val = tmp._val
        }
    }

binary_search_tree.rb

    ### Удаление узла ###
    def remove(num)
      # Если дерево пусто, сразу вернуть
      return if @root.nil?

      # Искать в цикле и выйти после прохода за листовой узел
      cur, pre = @root, nil
      while !cur.nil?
        # Найти узел для удаления и выйти из цикла
        break if cur.val == num

        pre = cur
        # Узел для удаления находится в правом поддереве cur
        if cur.val < num
          cur = cur.right
        # Узел для удаления находится в левом поддереве cur
        else
          cur = cur.left
        end
      end
      # Если узел для удаления отсутствует, сразу вернуть
      return if cur.nil?

      # Число дочерних узлов = 0 или 1
      if cur.left.nil? || cur.right.nil?
        # Когда число дочерних узлов = 0 / 1, child = null / этот дочерний узел
        child = cur.left || cur.right
        # Удалить узел cur
        if cur != @root
          if pre.left == cur
            pre.left = child
          else
            pre.right = child
          end
        else
          # Если удаляемый узел является корнем, заново назначить корневой узел
          @root = child
        end
      # Число дочерних узлов = 2
      else
        # Получить следующий узел после cur в симметричном обходе
        tmp = cur.right
        while !tmp.left.nil?
          tmp = tmp.left
        end
        # Рекурсивно удалить узел tmp
        remove(tmp.val)
        # Перезаписать cur значением tmp
        cur.val = tmp.val
      end
    end

Визуализация кода

Во весь экран >

### 4. Упорядоченность симметричного обхода

Как показано на рисунке 7-22, симметричный обход двоичного дерева следует порядку «лево \(\rightarrow\) корень \(\rightarrow\) право», а двоичное дерево поиска удовлетворяет соотношению «левый дочерний узел \(<\) корень \(<\) правый дочерний узел».

Это означает, что при симметричном обходе двоичного дерева поиска мы всегда сначала будем посещать следующий минимальный узел, и отсюда получается важное свойство: последовательность симметричного обхода двоичного дерева поиска является возрастающей.

Используя это свойство возрастающей последовательности симметричного обхода, мы можем получить отсортированные данные из двоичного дерева поиска всего за \(O(n)\) времени, без дополнительной сортировки, что очень эффективно.

Рисунок 7-22 Последовательность симметричного обхода двоичного дерева поиска

## 7.4.2 Эффективность двоичного дерева поиска

Для заданного набора данных можно рассмотреть хранение либо в массиве, либо в двоичном дереве поиска. Как видно по данным в таблице 7-2, временная сложность операций двоичного дерева поиска имеет логарифмический порядок и обеспечивает стабильную высокую производительность. Только в сценариях с очень частыми вставками и редкими поисками и удалениями массив может быть эффективнее, чем двоичное дерево поиска.

Таблица 7-2 Сравнение эффективности массива и дерева поиска

| Неупорядоченный массив | Двоичное дерево поиска
--- | --- | ---
Поиск элемента | \(O(n)\) | \(O(\log n)\)
Вставка элемента | \(O(1)\) | \(O(\log n)\)
Удаление элемента | \(O(n)\) | \(O(\log n)\)

В идеальном случае двоичное дерево поиска является «сбалансированным», и тогда любой узел можно найти за \(\log n\) итераций.

Однако если в двоичное дерево поиска непрерывно вставлять и удалять узлы, оно может выродиться в связный список, как показано на рисунке 7-23. Тогда временная сложность различных операций тоже вырождается до \(O(n)\) .

Рисунок 7-23 Деградация двоичного дерева поиска

## 7.4.3 Типичные применения двоичного дерева поиска

- Используется как многоуровневый индекс в системах, обеспечивая эффективный поиск, вставку и удаление.
- Служит базовой структурой данных для некоторых поисковых алгоритмов.
- Применяется для хранения потока данных в отсортированном состоянии.

##### Оставляйте свои идеи, вопросы и предложения в комментариях