data_structures.binary_tree.avl_tree

Implementation of an auto-balanced binary tree! For doctests run following command: python3 -m doctest -v avl_tree.py For testing run: python avl_tree.py

Attributes

t

Classes

AVLtree

An AVL tree doctest

MyNode

MyQueue

Functions

_test(→ None)

del_node(→ MyNode | None)

get_height(→ int)

get_left_most(→ Any)

get_right_most(→ Any)

insert_node(→ MyNode | None)

left_rotation(→ MyNode)

a mirror symmetry rotation of the left_rotation

lr_rotation(→ MyNode)

A A Br

my_max(→ int)

right_rotation(→ MyNode)

A B

rl_rotation(→ MyNode)

Module Contents

class data_structures.binary_tree.avl_tree.AVLtree

An AVL tree doctest Examples: >>> t = AVLtree() >>> t.insert(4) insert:4 >>> print(str(t).replace(” n”,”n”))

4

>>> print(str(t).replace(" \n","\n").replace(" \n","\n"))
  4
 2  *
*************************************
>>> t.insert(3)
insert:3
right rotation node: 2
left rotation node: 4
>>> print(str(t).replace(" \n","\n").replace(" \n","\n"))
  3
 2  4
*************************************
>>> t.get_height()
2
>>> t.del_node(3)
delete:3
>>> print(str(t).replace(" \n","\n").replace(" \n","\n"))
  4
 2  *
*************************************
__str__() → str
del_node(data: Any) → None
get_height() → int
insert(data: Any) → None
root: MyNode | None = None
class data_structures.binary_tree.avl_tree.MyNode(data: Any)
get_data() → Any
get_height() → int
get_left() → MyNode | None
get_right() → MyNode | None
set_data(data: Any) → None
set_height(height: int) → None
set_left(node: MyNode | None) → None
set_right(node: MyNode | None) → None
data
height: int = 1
left: MyNode | None = None
right: MyNode | None = None
class data_structures.binary_tree.avl_tree.MyQueue
count() → int
is_empty() → bool
pop() → Any
print_queue() → None
push(data: Any) → None
data: list[Any] = []
head: int = 0
tail: int = 0
data_structures.binary_tree.avl_tree._test() → None
data_structures.binary_tree.avl_tree.del_node(root: MyNode, data: Any) → MyNode | None
data_structures.binary_tree.avl_tree.get_height(node: MyNode | None) → int
data_structures.binary_tree.avl_tree.get_left_most(root: MyNode) → Any
data_structures.binary_tree.avl_tree.get_right_most(root: MyNode) → Any
data_structures.binary_tree.avl_tree.insert_node(node: MyNode | None, data: Any) → MyNode | None
data_structures.binary_tree.avl_tree.left_rotation(node: MyNode) → MyNode

a mirror symmetry rotation of the left_rotation

data_structures.binary_tree.avl_tree.lr_rotation(node: MyNode) → MyNode

A A Br

/ / /

B C LR Br C RR B A

/ –> / –> / /

Bl Br B UB Bl UB C

/ UB Bl

RR = right_rotation LR = left_rotation

data_structures.binary_tree.avl_tree.my_max(a: int, b: int) → int
data_structures.binary_tree.avl_tree.right_rotation(node: MyNode) → MyNode

A B

/ /

B C Bl A

/ –> / /

Bl Br UB Br C

/

UB

UB = unbalanced node

data_structures.binary_tree.avl_tree.rl_rotation(node: MyNode) → MyNode
data_structures.binary_tree.avl_tree.t