What is balanced binary search tree?

Answer 1

A "balanced" tree is a tree which is not lopsided. A semi-official definition of "balanced" mean that the "deepest" leaf node has a depth no greater than 1 more than the "shallowest" leaf node's depth.

An "unbalanced" tree is one which is lopsided, meaning that some of the leaf nodes have very high depths and some leaf nodes have very low depths. The most extreme case of an "unbalanced" tree is a linked list, with the root being one end of the linked list and the only leaf node being the other end.

A balanced Binary Search Tree (BST) guarantees that a search operation can be completed in O(log n) time. An unbalanced Binary Search Tree has a search operation of O(n) time.

There are a class of BSTs called self balancing BSTs - they automatically restructure themselves as nodes are added and removed to guarantee that they will always be balanced. Examples include the AVL tree and Red-Black tree.

Answer 2

A balanced tree is a tree which is balanced - it has roughly the same height on each of its sub-nodes. A balanced tree will have the lowest possible overall height.

For example, a balanced binary search tree will have equal heights (plus or minus one) on the left and right sub-trees of each node. This ensures that operations on the tree always are guaranteed to have O(lg n) time, rather than the O(n) time that they might have in an unbalanced tree.

Certain tree algorithms are designed for ensuring that the tree stays balanced at all times, while maintaining the O(lg n) time for all operations. Such algorithms, such as red-black trees, AVL trees, and others, are generally used in standard library implementation of binary search trees.

Answer 3

A balanced binary tree is one where each node has a balanced number of left and right child nodes. The act of adding or deleting a node from a balanced tree makes it imbalanced and, as this imbalance progresses, the performance of search time through the tree degrades. In the worst case, a completely unbalanced tree is no more than a sorted linked list.

To compensate for this, modern binary tree insertion and deletion algorithms have mechanisms in place to detect the imbalance and the restore balance by pivoting nodes around each other. There is cost to that, however, so most algorithms have logic that allows a certain amount of imbalance before doing the repivoting process.

Answer 4

A balanced tree is a tree structure where all the nodes are evenly distributed, such that the tree is as close to symmetric as possible. In balanced binary trees, every leaf is at the same depth or is within one level of the majority of leafs, and the nodes are as evenly distributed on either side of the root as possible.

Answer 5

A balanced binary tree is where every node has a similar number of nodes to the left and right. Balanced binary trees are typically implemented as red/black trees which automatically restores the balance upon each insertion.

Answer 6

It means that all the branches have, more or less, the same length.