Cisco CloudCenter: Get the Hybrid IT Advantage

Self-Balancing Binary Search Tree

Definition - What does Self-Balancing Binary Search Tree mean?

A self-balancing binary search tree is a type of data structure that self-adjusts to provide consistent levels of node access. In a self-balancing binary search tree, the connections from the top node to additional nodes are sorted and re-adjusted so that the tree is even, and search trajectory lines for each end node are equal in terms of length.

A self-balancing binary search tree is also known as a balanced tree or height-balanced binary search tree.

Techopedia explains Self-Balancing Binary Search Tree

A binary search tree in general provides a data structure with one node at the top, and either one or two nodes connected to it on each subsequent level. Binary search trees support three operations – operators can insert components, delete components, or look up some number or other node content. Part of the benefit of binary search trees is that the system can sort to ignore one half of the tree at every level, leading to more efficient search workloads.

The positive aspect of a self-balancing binary search tree is that node access is equal – for instance, instead of having to go five steps on one side of the tree, or three steps on the other side of the tree, because of the self-adjusted node structure, the search would only go a certain number of steps (n) to any given end node. This is achieved by taking out individual node connections and replacing them with binary ones to shorten particular limbs of the tree.

The drawback to a self-balancing binary search three is that it only works if the node connections are “level-agnostic” – in other words, if an individual node can be re-adjusted to a prior level in order to shorten the tree branch. For example, if a self-balancing binary search tree is composed with a given number at the top, and two subsequent numbers on either side, and there is a chain of three additional numbers with single node connections, the adjustment of the tree would put the fifth node together with the third node instead of the fourth node, so that the third node has two connecting nodes instead of one. However, if the data structure needs to identify particular node contents as being related in a specific parent/child relationship, adjusting these nodes to fit the tree structure evenness is not going to work.

Share this:

Connect with us

Email Newsletter

Join thousands of others with our weekly newsletter

The 4th Era of IT Infrastructure: Superconverged Systems
The 4th Era of IT Infrastructure: Superconverged Systems:
Learn the benefits and limitations of the 3 generations of IT infrastructure – siloed, converged and hyperconverged – and discover how the 4th...
Approaches and Benefits of Network Virtualization
Approaches and Benefits of Network Virtualization:
Businesses today aspire to achieve a software-defined datacenter (SDDC) to enhance business agility and reduce operational complexity. However, the...
Free E-Book: Public Cloud Guide
Free E-Book: Public Cloud Guide:
This white paper is for leaders of Operations, Engineering, or Infrastructure teams who are creating or executing an IT roadmap.
Free Tool: Virtual Health Monitor
Free Tool: Virtual Health Monitor:
Virtual Health Monitor is a free virtualization monitoring and reporting tool for VMware, Hyper-V, RHEV, and XenServer environments.
Free 30 Day Trial – Turbonomic
Free 30 Day Trial – Turbonomic:
Turbonomic delivers an autonomic platform where virtual and cloud environments self-manage in real-time to assure application performance.