数据结构中的平衡二叉查找树

在此，我们将了解平衡二叉查找树是什么。二叉查找树 (BST) 是二叉树，其左子树具有较小的元素，而右子树具有较大的元素。

在 BST 中搜索元素的平均时间复杂度为 O(log n)。它取决于二叉查找树的高度。为了维护二叉查找树的属性，有时树会变得倾斜。因此，倾斜的树将如下所示 −

这实际上是一棵树，但看起来更像是一个链表。对于这种树，搜索时间将为 O(n)。这对于二叉树来说是无效的。

为了克服这些问题，我们可以创建一棵高度平衡的树。这样，树就不会倾斜。我们必须强行让它们保持平衡。因此，每个节点的每一侧都会保存一颗子树，其高度几乎相同

有多种平衡技术。其中一些是 −

  • AVL 树

  • 红黑树

上述示例的高度平衡形式将如下所示 −

更新于：10-8-2020

792 次查看

开启你的 职业生涯

完成课程获得认证

开始
广告