在完整的二进制搜索树中动态插入节点 [英] Inserting node dynamically in Complete Binary Search Tree

问题描述

我知道二进制搜索树和完整二进制树的概念。有没有一种方法可以为完全二进制搜索树编写插入算法，或者我在考虑错误的数据结构？

I know the concept of Binary Search Tree and Complete Binary tree. Is there a way we can write insert algorithm for Complete binary search tree or I am thinking of wrong data structure?

我的目标是每次插入一个节点时，Tree应该保持完整的二进制搜索树。

My objective is every time we insert a node, Tree should remain complete binary search tree.

推荐答案

当然可以。但这将是O（N）算法，只需在每次插入或删除后重建树即可。

Of course you can. But it will be O(N) algorithm, just rebuild tree after every insertion or deletion.

您这样做的速度不能超过O（N）时间。因为：

You can't do this faster than O(N) time. Because:

1）仅存在1个具有给定键的完整树。

1) Exists only 1 complete tree with given keys.

2）您可以删除或插入

2) You can remove or insert the minimum and you will have to change the whole tree (costs you O(N) operations).

不是完整的搜索二叉树，而是使用平衡的二叉树（例如RB，AVL，笛卡尔，Splay等）。

Instead of complete search binary trees, balanced binary trees are used (like RB, AVL, Cartesian, Splay and etc.).

这篇关于在完整的二进制搜索树中动态插入节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！