Chapter 4. Binary Search Tree#
Binary Search Tree (BST) is a node-based binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with
keys less than the node’s key.The right subtree of a node contains only nodes with
keys greater than the node’s key.This means
everything to the left of the root is less than the value of the root and everything to the right of the root is greater than the value of the root. Due to this performing, a binary search is very easy.The left and right subtree each must also be a binary search tree.
There must be no duplicate nodes (BST may have duplicate values with different handling approaches)
Terminology
traversal order: the order of the nodes generated from a given traversal direction.preorder traversal: repeatly traverse the node first, then the left and lastly the right.
Key Properties
Keep track of the range of node value. -> can be used to check if a tree is a valid BST or construct a BST from given preorder traversal order.
class Node():
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def traverse_preorder(root: Node) -> list:
if not root:
return []
res = [root.val]
if root.left:
res.extend(traverse_preorder(root.left))
if root.right:
res.extend(traverse_preorder(root.right))
return res
def printTree(root, method='preorder'):
traversal = []
if method == "preorder":
pass
Build#
From Preorder#
How to build a BST from given preorder traversal? For example if the given preorder traversal is [10,5,1,7,40,50], then the BST has the following format:
10
/ \
5 40
/ \ \
1 7 50
Important
In
preordertraversal, the root node always comes first.The key is to find its left subtree and right subtree from a given root using the above principle.
Together with
inorder, where left subtree always comes first, it is easy to reconstruct a general binary tree.
Notes
General BT construction needs both preorder and inorder traversals, but BST can be constructed from preorder traversal only or postorder traversal only.
BST cannot be constructed from inorder traveral only.
Leetcode
Method 1#
The first element of the preorder traversal
Ais always root.Then we find the first element that is greater than the root, and get its index
i. In 0-index language, any values between1andishall be the left subtree, and values betweeniand-1shall be the right subtree.Recursively cconstruct the left subtree using
A[1:i]and right subtree usingA[i:].
Complexity
time: \(O(n^2)\)
def build_preorder(A):
# return None if empty
if not A:
return None
# get root
root = Node(val = A[0])
n = len(A)
# get left subtree and right subtree
# using the first element of the right subtree
# or we can use inorder traversal here by sorting the preorder traversal
i = 1
while i < n and A[i] < A[0]:
i += 1
# recurse
left = build_preorder(A[1:i])
right = build_preorder(A[i:])
# combine
root.left = left
root.right = right
return root
# test
A = [10,5,1,7,40,50]
root = build_preorder(A)
print(traverse_preorder(root))
A = []
root = build_preorder(A)
print(traverse_preorder(root))
A = [1]
root = build_preorder(A)
print(traverse_preorder(root))
[10, 5, 1, 7, 40, 50]
[]
[1]
Method 2#
Traverse each element in the preorder traversal, and compare its value with the root value
if the node value is less than the root value, change root to its left
if the node value is greater than the root value, change root to its right
recurse until the node is inserted correctly
Complexity
time: \(O(n^2)\)
def buildBST(preorder):
if not A:
return None
root = Node(preorder[0])
n = len(preorder)
if n == 1:
return root
# insert
def insert(root, node):
# base case
if not root:
return node
# insert to left tree or right tree
if node.val < root.val:
root.left = insert(root.left, node)
else:
root.right = insert(root.right, node)
return root
for i in range(1,n):
root = insert(root, Node(preorder[i]))
return root
# test
A = [10,5,1,7,40,50]
root = buildBST(A)
print(traverse_preorder(root))
A = []
root = buildBST(A)
print(traverse_preorder(root))
A = [1]
root = buildBST(A)
print(traverse_preorder(root))
[10, 5, 1, 7, 40, 50]
[]
[1]
Method 3#
The information of the binary tree can be saved using preorder traversal and inorder traversal.
The key idea here is:
preorder traversal preserves the node order in [root, left, right]
inorder traversal preserves the node order in [left, root, right]. For BST, the inorder traversal is sorted increasingly.
we can get the inroder traversal of BST easily from sorting the preorder traversal.
The first element in the preorder traversal is always the root, and the left slice of the inorder traversal to the root is the whole left subtree.
Therefore, we just need to know the index of the root in the inorder traversal.
Complexity
time: \(O(n^2log(n))\)
space: \(O(n)\). Extra space for storing inorder traversal and recursive call stack, whose worst scenario is \(O(n)\) when the tree is left-skewed.
This could be improved to \(O(n)\) time
def buildBST(preorder):
# base case
if len(preorder) < 1:
return None
root = Node(preorder[0])
# get inorder traversal of a BST
inorder = sorted(preorder)
# find root index in inorder traversal
ind = inorder.index(preorder[0])
# build left
root.left = buildBST(preorder[1:ind+1])
root.right = buildBST(preorder[ind+1:])
return root
# test
A = [10,5,1,7,40,50]
root = buildBST(A)
print(traverse_preorder(root))
A = [10, 5, 3, 1, 4, 7, 6, 8, 40, 50]
root = buildBST(A)
print(traverse_preorder(root))
[10, 5, 1, 7, 40, 50]
[10, 5, 3, 1, 4, 7, 6, 8, 40, 50]
Method 4#
See https://www.youtube.com/watch?v=UmJT3j26t1I.
BST node has a property that determines the range of its subtree. The key idea here is use the upper bounds of each explored node to decide where a specific node should be inserted:
initialize the upper bound of the root as
INFfor each node, recursively
build the left subtree using upper bound
node.valbuild the right subtree using upper bound the current node’s parent upper bound
Complexity
time: O(n). For each node, we at most visit 3 times, thus the worst scenario is \(O(3n)\), which is \(O(n)\)
space: O(n). This recursive algorithm uses stack space.
# The recursion is so beatiful here. Try to understand
# The key point here is:
# 1. A is globally changed by each recursion.
# 2. The recusion always build left brach first. Until no left node is possible, it will build the right branch from the bottom of left subtree to the right subtree of the root.
def buildBST(preorder):
def build(A, ub=float('inf')):
if not A or A[0] > ub: return None
#print(A)
root = Node(A.pop(0))
print(f"A for left: {A}")
root.left = build(A, root.val)
print(f"A for right: {A}")
root.right = build(A, ub)
return root
return build(preorder)
# test
A = [10,5,1,7,40,50]
root = buildBST(A)
print(traverse_preorder(root))
#A = []
#root = buildBST(A)
#print(traverse_preorder(root))
#A = [1]
#root = buildBST(A)
#print(traverse_preorder(root))
A for left: [5, 1, 7, 40, 50]
A for left: [1, 7, 40, 50]
A for left: [7, 40, 50]
A for right: [7, 40, 50]
A for right: [7, 40, 50]
A for left: [40, 50]
A for right: [40, 50]
A for right: [40, 50]
A for left: [50]
A for right: [50]
A for left: []
A for right: []
[10, 5, 1, 7, 40, 50]
# A wrong implementation:
# the index i is not global, which results the same node will be attached to both left and right if possible.
def buildBST(preorder):
def build(A, i, ub=float('inf')):
if i == len(A) or A[i] > ub:
return None
root = Node(A[i])
root.left = build(A, i+1, root.val)
root.right = build(A, i+1, ub)
return root
return build(preorder, 0)
# The following implementation fixes the above code
def buildBST(preorder):
global i
i = 0
def build(A, ub=float('inf')):
global i
if i == len(A) or A[i] > ub:
return None
root = Node(A[i])
i += 1
root.left = build(A, root.val)
root.right = build(A, ub)
return root
return build(preorder)
# test
A = [10,5,1,7,40,50]
root = buildBST(A)
print(traverse_preorder(root))
[10, 5, 1, 7, 40, 50]
Build All BST from Inorder Traversal#
Inorder traversal alone cannot define a unique BST. But based on inorder traversal, we can get all the possible BST structures. How?
See here.
This will require dynamic programming. We will come back later.
Traverse#
Traverse the BST node by node.
Depth-first Searchpreorder
inorder
postorder
Breadth-first Searchlevel-order
Preorder Traversal#
Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix expressions on an expression tree.
visit the root
traverse the left subtree
traverse the right subtree
# Method 1: dynamic programming: divide into subproblem and integrate subproblem solutions to get final solution
def preorder(root):
# base case
if not root:
return []
# store node
order = [root.val]
# traverse the left subtree and right subtree
order.extend(preorder(root.left))
order.extend(preorder(root.right))
# return
return order
A = [10,5,1,7,40,50]
root = buildBST(A)
print(preorder(root))
[10, 5, 1, 7, 40, 50]
# Method 2: backtracking
def preorder(root):
# traverse function
def traverse(root):
if not root:
return
res.append(root.val)
traverse(root.left)
traverse(root.right)
res = []
traverse(root)
return res
A = [10,5,1,7,40,50]
root = buildBST(A)
print(preorder(root))
[10, 5, 1, 7, 40, 50]
Inorder#
In the case of BST, Inorder traversal gives nodes in non-decreasing order. To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal is reversed can be used.
traverse the left subtree
visit the root
traverse the rigth subtree
Recursive Implementation
## A recursive implementation
def inorder(root):
# base case
if not root:
return []
order = []
# traverse left subtree
order.extend(inorder(root.left))
order.extend([root.val])
order.extend(inorder(root.right))
return order
A = [10,5,1,7,40,50]
root = buildBST(A)
print(inorder(root))
[1, 5, 7, 10, 40, 50]
Iterative Implementation Using Stack
Create an empty stack S.
Initialize current node as root
Push the current node to S and set
current = current.leftuntil current is NULLIf current is NULL and stack is not empty then
Pop the top item from stack.
Print the popped item, set
current = popped_item.rightGo to step 3.
If current is NULL and stack is empty then we are done
============================================================ Let us consider the below tree for example 1 / \ 2 3 / \ 4 5 Step 1 Creates an empty stack: S = NULL Step 2 sets current as address of root: current -> 1 Step 3 Pushes the current node and set current = current->left until current is NULL current -> 1 push 1: Stack S -> 1 current -> 2 push 2: Stack S -> 2, 1 current -> 4 push 4: Stack S -> 4, 2, 1 current = NULL Step 4 pops from S a) Pop 4: Stack S -> 2, 1 b) print "4" c) current = NULL /*right of 4 */ and go to step 3 Since current is NULL step 3 doesn't do anything. Step 4 pops again. a) Pop 2: Stack S -> 1 b) print "2" c) current -> 5/*right of 2 */ and go to step 3 Step 3 pushes 5 to stack and makes current NULL Stack S -> 5, 1 current = NULL Step 4 pops from S a) Pop 5: Stack S -> 1 b) print "5" c) current = NULL /*right of 5 */ and go to step 3 Since current is NULL step 3 doesn't do anything Step 4 pops again. a) Pop 1: Stack S -> NULL b) print "1" c) current -> 3 /*right of 1 */ Step 3 pushes 3 to stack and makes current NULL Stack S -> 3 current = NULL Step 4 pops from S a) Pop 3: Stack S -> NULL b) print "3" c) current = NULL /*right of 3 */ Traversal is done now as stack S is empty and current is NULL.
## A iterative implementation: use a stack to store
def inorder(root):
order = []
stack = [root] # if use stack=[root]
curr = root
# Note len([None]=1)
while stack:
# pop if current is none and stack is not empty
if not curr:
curr = stack.pop()
# get the order
order.append(curr.val)
# update current node
curr = curr.right
# push all left nodes and then right node
while curr:
# avoid storing root twice
if curr.val != root.val:
stack.append(curr)
curr = curr.left
return order
# Test
A = [10,5,1,7,40]
root = buildBST(A)
print(inorder(root))
[1, 5, 7, 10, 40]
Iterative Implementation without Stack
This method is known as Morris Traversal. See here.
Postorder#
Postorder traversal is used to delete the tree. Please see the question for the deletion of a tree for details. Postorder traversal is also useful to get the postfix expression of an expression tree
traverse the left subtree
traverse the right subtree
visit the root
def postorder(root):
# base
if not root:
return []
order = []
# traverse
order.extend(postorder(root.left))
order.extend(postorder(root.right))
order.extend([root.val])
# return
return order
A = [10,5,1,7, 40, 50]
root = buildBST(A)
print(inorder(root))
print(postorder(root))
[1, 5, 7, 10, 40, 50]
[1, 7, 5, 50, 40, 10]
Level Order Traversal#
Traverse the tree level by level from top to bottom
def levelOrderTop(root):
if not root:
return []
# initialize
level = 1
queue = [(root, level)]
res = []
while queue:
level_res = []
level = queue[0][1]
# traverse each level
while queue and level == queue[0][1]:
# pop all nodes from the same level
node, level = queue.pop(0)
# stack level result
if node:
level_res.append(node.val)
else:
level_res.append('null')
# update queue: node at least has one child
if node and (node.left or node.right):
queue.extend([(node.left, level+1), (node.right, level+1)])
# stack level results to head:
res.append(level_res)
return res
A = [10,5,1,7, 40, 50]
root = buildBST(A)
print(inorder(root))
print(levelOrderTop(root))
[1, 5, 7, 10, 40, 50]
[[10], [5, 40], [1, 7, 'null', 50]]
Traverse the tree level by level from bottom to top
Method 1:
use a stack to store all nodes and level info level-by-level from top to bottom
pop the stack to another stack so that all the nodes in the same level are in the new stack
def levelOrderBottom(root):
if not root:
return []
level = 1
queue = [(root, level)]
# initialize two stacks
stack = []
# initialize output
res= []
# traverse to store all nodes in stack
while queue:
node, level = queue.pop(0)
# save to a stack
stack.append((node, level))
# append children to queue: keep null as a place holder
if node and (node.left or node.right):
queue.extend([(node.left, level + 1), (node.right, level + 1)])
# pop stack to get level order traversal from bottom
while stack:
level_stack = []
# traverse level
level = stack[-1][1]
while stack and level == stack[-1][1]:
node, level = stack.pop()
level_stack.append(node)
# pop level_stack to get the output
level_res = []
while level_stack:
node = level_stack.pop()
if node:
level_res.append(node.val)
else:
level_res.append('null')
# output
res.append(level_res)
return res
A = [10,5,1,7, 40, 50]
root = buildBST(A)
print(levelOrderBottom(root))
[[1, 7, 'null', 50], [5, 40], [10]]
Method 2:
This method is the same as level traversal from top to down, but when appending level results, we insert the level result at the head instead of tail.
def levelOrderBottom(root):
if not root:
return []
# initialize
level = 1
queue = [(root, level)]
res = []
while queue:
level_res = []
level = queue[0][1]
# traverse each level
while queue and level == queue[0][1]:
# pop all nodes from the same level
node, level = queue.pop(0)
# stack level result
if node:
level_res.append(node.val)
else:
level_res.append('null')
# update queue: node at least has one child
if node and (node.left or node.right):
queue.extend([(node.left, level+1), (node.right, level+1)])
# stack level results to head:
res.insert(0, level_res)
return res
A = [10,5,1,7, 40, 50]
root = buildBST(A)
print(levelOrderBottom(root))
[[1, 7, 'null', 50], [5, 40], [10]]
Serialization and Deserialization#
Serialization is a way to convert a binary tree to a standard format, which then can be used by external tools.#
Deserialization is a way to construct a binary tree from a given serialization format.
def serialize(root, order = "level-order"):
def level_order_serialize(root):
if not root:
return []
# traverse level by level from top to down, and use null as a placeholder for missing child or children
queue = [root]
res = []
while queue:
node = queue.pop(0)
val = node.val if node else "null"
res.append(val)
# update queue
if node and (node.left or node.right):
queue.extend([node.left, node.right])
return res
if order == "level-order":
return level_order_serialize(root)
else:
pass
A = [10,5,1,7, 40, 50]
root = buildBST(A)
print(serialize(root, "level-order"))
[10, 5, 40, 1, 7, 'null', 50]
def deserialize(serialization, order='level-order'):
# serialization represent a binary tree in its complete format by introducing null whereever possible.
if not serialization:
return None
def level_order_deserialize(serialization):
pass
Insertion#
A new key is always inserted at the leaf. We start searching for a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.
Insert 3 to the following BST will lead to:
10 10
/ \ insert 3 / \
5 40 -------> 5 40
/ \ \ / \ \
1 7 50 1 7 50
\
3
# A recursion Implementation
def insert(root, key):
node = Node(key)
# base case
if not root:
return node
# insert recursively assuming no duplicates
if root.val > key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
A = [10,5,1,7, 40, 50]
root = buildBST(A)
root = insert(root, 3)
print(inorder(root))
print(preorder(root))
[1, 3, 5, 7, 10, 40, 50]
[10, 5, 1, 3, 7, 40, 50]
# An iterative implementation
def insert(root, key):
node = Node(key)
cur = root
prev = None
while cur:
prev = cur
# go left
if cur.val > key:
cur = cur.left
else: # go right
cur = cur.right
# specify connections
if prev.val > key:
prev.left = node
else:
prev.right = node
return root
A = [10,5,1,7, 40, 50]
root = buildBST(A)
root = insert(root, 3)
print(inorder(root))
print(preorder(root))
[1, 3, 5, 7, 10, 40, 50]
[10, 5, 1, 3, 7, 40, 50]
Deletion#
When we delete a node, three possibilities arise.
Node to be deleted is the leaf: Simply remove from the tree.
50 50
/ \ delete(20) / \
30 70 ---------> 30 70
/ \ / \ \ / \
20 40 60 80 40 60 80
Node to be deleted has only one child: Copy the child to the node and delete the child
50 50
/ \ delete(30) / \
30 70 ---------> 40 70
\ / \ / \
40 60 80 60 80
Node to be deleted has two children: Find
inorder successorof the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note thatinorder predecessorcan also be used.
50 60
/ \ delete(50) / \
40 70 ---------> 40 70
/ \ \
60 80 80
The important thing to note is, inorder successor is needed only when the right child is not empty. In this particular case, inorder successor can be obtained by finding the minimum value in the right child of the node.
def delete(root, key):
def successor(root):
"""find the inorder successor for a given node
- if root has no right child, return None
- else return the leftmost node in the right subtree
"""
if not root or not root.right:
return None
node = root.right
while node.left:
node = node.left
return node
# base case
if not root:
return root
# if key is smaller than the root's key then it lies in the left subtree
if key < root.val:
root.left = delete(root.left, key)
elif key > root.val:
root.right = delete(root.right, key)
# key is the same as the root key
else:
# root is a leaf
if not root.left and not root.right:
return None
# root has only one child - left
elif root.left and not root.right:
temp = root.left
root = None
return temp
# root has only one child - right
elif not root.left and root.right:
temp = root.right
root = None
return temp
# root has two children
succ = successor(root)
# copy the content
#right = root.right # need reverse the right subtree before deletion
#left = root.left
root.val = succ.val
# delete the inorder successor
#root.left = left
root.right = delete(root.right, succ.val)
return root
# test
A = [50,30,20,40,70,60,80]
root = buildBST(A)
root = delete(root, 20)
print(preorder(root))
A = [50,30,40,70,60,80]
root = buildBST(A)
root = delete(root, 30)
print(preorder(root))
A = [50,40,70,60,80]
root = buildBST(A)
root = delete(root, 50)
print(preorder(root))
[50, 30, 40, 70, 60, 80]
[50, 40, 70, 60, 80]
[60, 40, 70, 80]
Search#
Search in binary tree is very simple which is the same as binary search.
Search an element#
ITERATIVE_TREE_SEARCH(root, x):
while x and x != root.val
if x < root.key:
root = root.left
else
root = root.right
return root
Minimum and Maximum#
Minimum: go to leftmost leaf nodeMaximum: go to rightmost leaf node
Successor and Predecessor#
Successor: inorder sucessor is the next element in the inorder traversal order.If current node has right subtree, then return left most leaf of the right-subtree (for BST, which is the minimum node of the right subtree)
If current node has no right subtree, then return the lowest ancestor
Applications#
Binary Tree to BST#
Given a Binary Tree, convert it to a Binary Search Tree. The conversion must be done in such a way that keeps the original structure of Binary Tree.
Example 1
Input:
10
/ \
2 7
/ \
8 4
Output:
8
/ \
4 10
/ \
2 7
Example 2
Input:
10
/ \
30 15
/ \
20 5
Output:
15
/ \
10 20
/ \
5 30
Analysis#
three steps:
get inorder traveral as an array from binary tree
sort the array for BST
inorder traverse the binary tree, and copy to the value of each node from the sorted array. We have to do inorder, because the sorted array is an inorder representation of BST.
def convertBTtoBST(root):
def traverse_inorder(root):
if not root:
return []
l = traverse_inorder(root.left)
v = [root.val]
r = traverse_inorder(root.right)
return l + v + r
def buildBST(root, arr_sort):
if root is None:
return
# no preorder operation
# traverse left subtree
left = buildBST(root.left, arr_sort)
# inorder operation - replace value
v = arr_sort.pop(0)
root.val = v
# traverse right subtree
right = buildBST(root.right, arr_sort)
# no postorder operation
return root
arr = traverse_inorder(root)
arr_sort = sorted(arr)
return buildBST(root, arr_sort)
# test
root = Node(10)
root.left = Node(30)
root.right = Node(15)
root.left.left = Node(20)
root.right.right = Node(5)
print(traverse_preorder(root))
bst = convertBTtoBST(root)
print(traverse_preorder(bst))
[10, 30, 20, 15, 5]
[15, 10, 5, 20, 30]
Tree Map#
See Leetcode 1038 and 538.
The problem is to map a BST to a greater tree or a geater sum tree.
For a greater tree, convert a BST to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.
Analysis#
inorder traversal of a BST is a sequence with increasingly sorted keys. One naive apporach is:
get inorder traversal of BST
get greater sum of the inorder sequences
build binary tree with the greater sum sequence but follow the original BST structure
this method is O(n) in both time and complexity
How can we implement it using sub-problem method?
maintain a sum that recursively add the current value to previous greater sum
inorder traverse the BST with decreasing keys (traverse right then left)
inorder change the node value with presum
Valid BST#
It looks easy to check if a binary tree is a valid BST by simply comparing the keys in node, node.left, and node.right.
But there is a trap using this method. Look at the below tree, where the left subtree and right subtree are both valid BST, and the node value 5<10<15, but it is not a valid BST as a whole.
10
/ \
5 15
/ \
6 20
The reason is the above method doesn’t guarantee that all values in the right subtree is greater than the node value, and all values in the left subtree should be smaller than the node value.
For binary tree, we know the upper and lower bound for each node. We can use this property to check if all nodes are within correct bounds.
Pesudo code:
boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
/* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
// base case
if (root == null) return true;
// 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
if (min != null && root.val <= min.val) return false;
if (max != null && root.val >= max.val) return false;
// 限定左子树的最大值是 root.val，右子树的最小值是 root.val
return isValidBST(root.left, min, root)
&& isValidBST(root.right, root, max);
}
AVL Tree#
AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.
Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that the height of the tree remains O(log(n)) after every insertion and deletion, then we can guarantee an upper bound of O(log(n)) for all these operations. The height of an AVL tree is always O(log(n)) where n is the number of nodes in the tree.
Insertion#
To make sure that the given tree remains AVL after every insertion, we must augment the standard BST insert operation to perform some re-balancing without violating BST properties. Two operations can be performed:
left rotation
right rotation
** Steps for Insertion **
Let the newly inserted node be w
Perform standard BST insert for
w.Starting from
w, travel up and find the first unbalanced node. Letzbe the first unbalanced node,ybe the child ofzthat comes on the path fromwtozandxbe the grandchild ofzthat comes on the path fromwtoz.Re-balance the tree by performing appropriate rotations on the subtree rooted with
z. There can be 4 possible cases that need to be handled asx,yandzcan be arranged in 4 ways.Following are the possible 4 arrangements:
yis the left child ofzandxis the left child ofy(Left Left Case)yis the left child ofzandxis the right child ofy(Left Right Case)yis the right child ofzandxis the right child ofy(Right Right Case)yis the right child ofzandxis the left child ofy(Right Left Case)
Red-Black Tree#
red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either red or black.
Every node is either red or black.
The root is black.
Every leaf is black.
If a node is red, then both its children are black.
For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.