平衡树 | Baeldung中文网

1. Introduction

In this tutorial, we’ll learn about balanced binary trees.

In particular, we’ll see why such trees come in handy and explore three types of them. We’ll talk about the AVL trees, the red-black trees, and weight-balanced trees. Each type has its definition of balance.

2. Binary and Binary Search Trees

We call a tree binary if each node in it has at most two children. A node’s left child with descendants forms the node’s left sub-tree. The definition of the right sub-tree is similar.

Although suitable for storing hierarchical data, binary trees of this general form don’t guarantee a fast lookup. Let’s take as the example the search for number 9 in the following tree:

binary tree

Whichever node we visit, we don’t know if we should traverse the left or the right sub-tree next. That’s because the tree hierarchy doesn’t follow the relation $\leq$ .

So, in the worst case, a search takes $\boldsymbol{O(n)}$ time, where $\boldsymbol{n}$ is the number of nodes in the tree.

2.1. Binary Search Tree

We solve this problem by turning to a special type of binary tree called binary search tree (BST). For each node $\boldsymbol{x}$ in a BST, all the nodes in the left sub-tree of $\boldsymbol{x}$ contain the values that are strictly lower than $\boldsymbol{x}$ . Further, all the nodes in the $\boldsymbol{x}$ ‘s right sub-tree are $\boldsymbol{\geq x}$ . For instance:

The order the tree maintains allows us to prune it during a lookup. Suppose we visit the node x < y while searching for . We can disregard the ‘s left sub-tree and focus only on the right, which speeds up the search. This is how we find 9 in the above search tree:

However, the worst-case complexity of the search is still $\boldsymbol{O(n)}$ . It occurs if we construct the tree from a sorted array, in which case the tree has height and degenerates to a linked list. Since insertion and deletion include the search, all operations commonly performed on a BST are $\boldsymbol{O(n)}$ in the worst case. So, it’s the height of the tree that determines the complexity. That’s where balanced trees come in. They’re a special type of binary search tree.

3. Balanced Trees

A balanced tree is a search tree that doesn’t just maintain the order between nodes. It also controls its height, making sure it stays $\boldsymbol{O(\log n)}$ after insertion or deletion.

To do that, a balanced tree must re-balance itself after we add or delete a node. That causes a computational overhead and complicates the algorithms for insertion and deletion. However, that’s the price we’re ready to pay for a logarithmic-height search tree with fast search, insertion, and deletion operations. We won’t cover the re-balancing algorithms in this article.

There are several types of such trees. They require all their nodes to be balanced, but the notion of balance differs from type to type.

4. AVL Trees

In an AVL tree, we call a node balanced if the heights of its left and right sub-trees differ at most by 1. So, a search tree with root is an AVL tree if all its nodes are balanced in the AVL sense (empty search trees, with height 0, are trivially balanced):

(1) $\begin{equation*} AVL(x) \iff \left|height(x.left) - height(x.right)\right| \leq 1 \text{ and } AVL(x.left) \text{ and } AVL(x.right) \end{equation*}$

For example:

A Balanced AVL Tree

A consequence of this definition of balance is that an AVL tree’s height is $O(\log n)$ in the worst case.

4.1. Proof That Height Is Logarithmic

An AVL tree is balanced the least if the heights of all the sibling sub-trees differ by one. For instance:

A Minimal AVL tree

That’s the worst-case structure of an AVL tree. Adding a node to a least-balanced AVL tree, we either get a non-AVL tree or balance one of its nodes. The same goes for deleting a node. So, such AVL trees are minimal: no AVL tree of the same height has fewer nodes.

Even if we switch the node’s left and right sub-trees, the tree will remain balanced. So, we’ll assume that the left sub-trees have more nodes. Then, if N(h) is the number of nodes of a minimal AVL tree with height , we have:

$[N(h) = 1 + \underbrace{N(h-1)}_{\text{left sub-tree}} + \underbrace{N(h-2)}_{\text{right sub-tree}}]$

From our assumption, we have that N(h-1) > N(h-2) , so:

$[N(h) > 1 + 2N(h-2) > 2N(h-2) > 4N(h-4) > 8N(h-6) > \ldots > 2^{\frac{h}{2}} N(0)]$

An AVL structure with height has only one node, so N(0)=1 , and:

$[\begin{aligned} n &= N(h) > 2^{\frac{h}{2}} \\ \log_2 n &> \frac{h}{2} \\ h &< 2 \log_2 n \in O(\log n) \end{aligned}]$

Therefore, in the worst-balanced case, an AVL tree’s height is $\boldsymbol{O(\log n)}$ . Hence, the operations such as search, insertion, and deletion have logarithmic time complexity.

5. Red-Black Trees

The Red-Black Trees (RBTs) also balance the sibling subtrees’ heights. But, an RBT differentiates between two types of nodes: the red ones and the black ones. An RBT ensures that all the paths from a node to its descendant leaves to pass through the same number of black nodes. Also, the number of black nodes from a node to its leaves, excluding the node, is called the node’s black height. The black height of the whole RBT is the black height of its root. For example (with NULL leaves coalesced into a single node to save space):

Red Black Tree

By definition, an RBT fulfills these conditions:

Every node is either black or red.
The root is black.
Every empty node (NULL or NIL) is black.
If a node is red, then both its children are black.
For every node , the paths from , not including it, to its descendant leaves contain the same number of black nodes.

Some authors don’t require the root to be black because we can repaint a tree in any case.

The properties of an RBT ensure:

that no path from the root to a leaf is more than twice as long as a path to another leaf,
and that the tree’s height is $O(\log n)$ .

5.1. Proof That the Height of an Rbt Is $\boldsymbol{O(\log n)}$

Let bh(x) be the black height of . We’ll first prove, by induction, that a sub-tree rooted at $\boldsymbol{x}$ has at least $\boldsymbol{2^{bh(x)} - 1}$ internal nodes.

The base case is bh(x) = 0 , which means that is an empty node, that is, a leaf:

$[2^{bh(NULL) } - 1 = 2^0 - 1 = 0]$

So, we’ve covered the base case. In the inductive step, we focus on and its children. Their black heights are equal to bh(x) or bh(x) - 1 , depending on their colors. By the hypothesis, they contain at least $2^{bh(x) - 1} - 1$ nodes each. So, the whole tree rooted at contains this many nodes at a minimum:

$[2 \cdot \left(2^{bh(x) - 1} - 1\right) + 1 &= 2^{bh(x)-1+1} -2 + 1 = 2^{bh(x)} - 1]$

Now, let be the height of the root node . Since red nodes can have only black children, at least half of the nodes from the root to any leaf must be black. Therefore, the root’s black height is $\geq h/2$ .

Using the result about the internal nodes, we get:

$[\begin{aligned} n &\geq 2^{\frac{h}{2}} - 1 \\ n + 1 &\geq 2^{\frac{h}{2}} \\ 2^{\frac{h}{2}} &\leq n + 1 \\ h &\leq 2\log_2{n+1} \in O(\log n) \end{aligned}]$

Again, we get that the height grows as the logarithm of the number of nodes.

6. Weight-Balanced Trees

The weight-balanced trees (WBTs) don’t balance the heights of the sibling sub-trees, but the numbers of leaves in them. So, let and x'' be the sub-trees of and let $leaves(x') \geq leaves(x'')$ . We say that is balanced if:

$[\frac{leaves(x'')}{leaves(x')} \leq \beta \in (0, 1)]$

We also require all the descendants of to fulfill the same condition. This is equivalent to stating that there exists an $\boldsymbol{\alpha \in \left(0, 1\right)}$ such that the following holds for every node $\boldsymbol{x}$ in the tree:

$[\begin{aligned} leaves(x.left) &\geq \alpha \cdot leaves(x) \\ leaves(x.right) &\geq \alpha \cdot leaves(x) \end{aligned}]$

To see why, let’s remember that leaves(x') > leaves(x'') and follow the derivation:

$[\begin{aligned} leaves(x) &= leaves(x') + leaves(x'') \\ &\leq 2\beta \cdot leaves(x'') \\ &\implies \\ leaves(x'') &\geq \frac{1}{2\beta} \cdot leaves(x) \end{aligned}]$

So, this is the recursive definition of a WBT :

(2) $\begin{equation*} WBT(x) \iff leaves(x.left) \geq leaves(x) \text{ and } leaves(x.right) \geq leaves(x) \text{ and } WBT(x.left) \text{ and } WBT(x.right) \end{equation*}$

Here’s an example of a WBT with $\alpha = 0.29$ (the number of leaves is written inside each node):

Weight Balanced Tree

The number of leaves in the tree is its weight, hence the name. We’ll prove that the height of a WBT is also bounded by $\log n$ .

6.1. Proof That the Height of a Weight-Balanced Tree Is $\boldsymbol{O(\log n)}$

Let’s suppose that is a minimal WBT whose height is , and let L(h) denote the number of leaves in it. From the definition of a WBT, we see that a sub-tree of contains at most $1 - \alpha$ of the node’s leaves. Also, a subtree’s height is at most h-1 . So, we have:

$[\begin{aligned} L(h-1) &\leq (1-\alpha) L(h) \\ L(h-2) & \leq (1-\alpha)^2 L(h) \\ &\ldots \\ L(0) &= 1 \leq (1-\alpha)^h L(h) \end{aligned}]$

Since $L(h) \leq n$ , where is the number of nodes in the tree, we have:

$[\begin{aligned} (1 - \alpha)^h n &\geq 1 \\ n &\geq (1 - \alpha)^{-h} \\ (1-\alpha)^{-h} &\leq n \\ \left( \frac{1}{1-\alpha} \right)^{h} &\leq n \\ h &\leq \log_{\frac{1}{1-\alpha}}n \in O(\log n) \\ \end{aligned}]$

So, the height of a WBT is also logarithmic in the number of nodes.

6.2. The Value Of $\boldsymbol{\alpha}$

If we use a too large $\alpha$ , re-balancing may become impossible. Its value should be $< 1 - \frac{1}{\sqrt{2}}$ .

If we’re ready to use a complicated custom re-balancing algorithm, we can use an arbitrarily small $\alpha$ . However, the recommendation is to use $\alpha \in \left( \frac{2}{11}, 1 - \frac{1}{\sqrt{2}}\right)$ .

7. Conclusion

In this article, we presented three types of balanced trees. Those were: the AVL trees, red-black trees, and weight-balanced trees. Using different notions of balance, they all guarantee the $\boldsymbol{O(\log n)}$ time complexity of search, insertion, and deletion.

However, the trees have to re-balance themselves upon change so that their height stays logarithmic in the number of nodes. The additional work complicates and slows down the algorithms for insertion and deletion. But, the overhead pays off because the complexity of the operations remains $O(\log n)$ .

Persistence

REST

Security