This is the 12th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Balanced binary tree

The world needs balance, and the party that destroys the balance may seek hegemony with great strength for a while, but the final outcome cannot escape isolation and failure

define

  • The left and right subtrees are balanced binary trees;
  • The absolute value of the difference between the left and right subtree depths of all nodes is ≤ 1

Equilibrium factor: the height difference between the left subtree and the right subtree of the node

  • The equilibrium factor of any node can only be -1, 0 or 1; If the absolute value of the balance factor of any node in the tree is greater than 1, then the binary tree is out of balance and no longer an AVL tree;
  • For an AVL tree with n nodes, the height remains on the order of O(log2n), and the ASL remains on the order of O(log2n).

Storage structure

typedef struct BSTNode{
	ElemType data;
	int bf;  // Balance factor
	struct BSTNode* lchild, *rchild; 
} BSTNode, *BSTree;
Copy the code

Balanced rotation

LL balanced rotation

  • LL type: The smallest root node that is out of balance is defined as A, then this kind of imbalance can be summarized as: The imbalance caused by insertion into the left subtree of the left subtree of a’s left subtree root node can be treated by unidirectional right-handed balance, and can be denoted asLeft left – > right.

    BF(B) changed from 1 to 0 and BF(A) changed from 2 to 0 after unidirectional dextral equilibrium treatment.

RR balanced rotation

  • Type RR: The imbalance caused by insertion in the right subtree of the right subtree of a’s right subtree root node can be handled by using single left-rotation balance, which can be denoted as right-right -> left.

BF(B) is changed from -1 to 0 and BF(A) is changed from -2 to 0 after single left rotation balancing treatment.

LR balanced rotation

  • LR type: Node 2 is inserted into the right subtree of node 1 of the left subtree of 3, resulting in imbalance. Bidirectional rotation can be used: first make the subtree turn left and then the whole tree turn right, which can be denoted as left -> left.

After bidirectional rotation balance treatment, BF(A) changes from 2 to -1, BF(B) changes from -1 to 0, and BF(C) changes from 1 to 0.

RL balance rotation

  • RL type: Node 23 is inserted into the left subtree of the right subtree of the root node 25 of the right subtree of 19, resulting in imbalance. Bidirectional rotation can be used: first make the subtree right-turn and then the whole tree left-turn, which can be denoted as right-left -> right-left

After bidirectional rotation balance treatment,BF(A) changes from -2 to 0,BF(B) from 1 to -1, and BF(C) from 1 to 0.

Rotating operation characteristics

  • Operation on the loptiest tree.
  • After rotation, the balance factor of sub-root node was 0.
  • The same subtree depth after rotation does not affect the whole tree, nor does it affect the balance degree of all ancestor nodes on the insertion path.

The keywords inserted are 5, 4, 2, 8, 6, and 9

Balanced binary tree insertion algorithm idea

  • If the tree is empty, insert the node as the root node, and the tree depth is increased by 1.

  • If the key value of the inserted node is equal to the key value of the root node, the node is not inserted.

  • Insert node key value less than root node key value, insert into the left subtree, left subtree depth by 1 and:

    • Left subtree depth < right subtree depth
    • If the balance factor of root node is -1 before insertion, it is changed to 0 after insertion, and the tree depth remains unchanged.

    • Left subtree depth = right subtree depth
    • If the root node balance factor is 0 before insertion, it is changed to 1 after insertion, and the tree depth is increased by 1.

    • Left subtree depth > right subtree depth LL type
    • If the balance factor of the root node before insertion is 1, and the balance factor of the left subtree after insertion is 1 (left-left), then the balance factor of the root node and the right subtree is changed to 0 after rotation, and the tree depth remains unchanged.

    • Left subtree depth > right subtree depth LR type
    • If the balance factor of the root node before insertion is 1, and the balance factor of the left subtree after insertion is -1 (about), then the rotation is left and then right. After rotation, the balance factor of the root node and its left subtree is changed to 0, and the balance factor of the right subtree is changed to -1, and the tree depth remains unchanged.

  • If the key value of the insert node is greater than the key value of the root node, insert it into the right subtree. The method is similar

Search performance analysis of balanced binary tree

  • The search process in the balanced tree is the same as that in the binary sort tree, so the number of keywords that are compared with the given value in the search process does not exceed the depth of the balanced tree.

When I look in the binary equilibrium tree,

The number of keywords that are compared to the given value during the search is equal to log(n).

Variant of AVL tree — red black tree

  • Color characteristics: Each node is “black” or “red”
  • Root characteristics: Roots are always “black”
  • External features: Extended external leaves are empty “black” nodes
  • Internal features: both children of a “red” node are “black”, that is, two consecutive red nodes are not allowed
  • Depth feature: For each node, the path from that node to all its descendant leaves must contain the same number of black nodes