[PYTHON] Binary search tree is a relative of Hash chain !?
Good evening (* ´ω ｀)
As an amateur, At first glance, what is "tree"? .. (Sorry for all the experts m (_ _) m)
The tree structure seems to be a data structure that expresses the hierarchical relationship between data.
Personally, it looked like an extension of the previous Hash chain. I was excited about what kind of thinking it was For the time being, I will play with it (laugh)
test.py
class Node:
def __init__(self,key,value,left:None,right:None):
self.key = key
self.value = value
self.left = left
self.right = right
It may be as it is, but I wrote the contents of the node.
In this way, more Nodes may be stored in the left and right areas inside the Node.
I tried to make it a little more woody.
It's similar to a Hash chain, it's interesting.
I'm sure there are rules on how to store data. Yes, there were rules. ..
A binary search tree is a binary tree in which ** all nodes ** meet the following conditions. The node key of the left subtree is ** smaller ** than that node key The node key of the right subtree is ** larger ** than that node key
The left subtree is the left child, the right subtree is the right noko, child !? (laughs)
From whom to judge right or left, it seems that there is no problem if you think at the turning point.
How is it? No matter where you are, the above conditions are met! ??
But why do you have such a rule? (11) The reason is the key setting rule provided earlier. Try to find key = 5.
- The Start point starts at 11, which is called the Root. The key I was looking for was 5. Keys smaller than the current location (= 11) were stored on the left side.
- Let's open the left pointer. There was in that Node, key = 5 !!
It's a happy goal.
Now let's look for another key = 9.
The transition is colored in red.
1.start from 11 (root), key (= 9) <11, so go to the left !!
2. key (= 9) is greater than 5, so go to the right !!
3. key (= 9) is larger than 7, so go to the right !!
There was key = 9 !!, Go ---- Le !!
I see, by devising the next pointer provided in the Hash chain Even more concise, it logically realizes complex data structures. great!!
test.py
class Node:
def __init__(self,key,value,left:None,right:None):
self.key = key
self.value = value
self.left = left
self.right = right
class BinarySearchTree:
def __init__(self):
self.root = None
def search(self,key):
#start from root!!
p = self.root
while True:
#return None if the structure has nothing connected to root
if p.key is None:
return None
#If key is applicable, p.return value
if p.key == key:
return p.value
#First, p mentioned above.key ==Since the key is passed,
#Describe the following transition to right or left
elif p.key < key:
p = p.right
else:
p = p.left
For the time being, describe the basic Node and Added the description to search. At this stage, Tree has not done anything. Now there is only an empty Root. Let's add Node here.
First of all, let's create from root.
test.py
def add(self,key,value):
#At the beginning, it was defined in Node as follows.
#class BinarySearchTree:
# def __init__(self):
# self.root = None
if self.root is None:
#The corresponding data may also be stored in root.
#left ,I will make right from now on, so I will leave it as None for the time being
self.root = Node(key,value,None,None)
else:
#If Node is already inserted in root
#You need to start from root and add Nodes.
#As you might expect, add_We will recurse node.
BinarySearchTree.add_node(self.root,key,value)
Once you have created the root Based on root, we will add Nodes according to the definition of the binary tree above. The following is a description of add_node that branches recursively.
test.py
def add_node(node,key,value):
#Fail if found duplicate key
if key == node.key:
return print("fail to add")
#New node.key <Existing Node.For key, store in left!
elif key < node.key:
#If pointer left is empty, add it as a new Node
if node.left is None:
node.left = Node(key,value,None,None)
#If there is already a store in left, process it recursively
else:
BinarySearchTree.add_node(node.left,key,value)
else:
#If pointer right is empty, add it as a new Node
if node.right is None:
node.right = Node(key,value,None,None)
#If right already has a store, process it recursively
else:
BinarySearchTree.add_node(node.right,key,value)
return True
Every time you execute add, start from root, search for the corresponding pointer, and add Node. It's as if a plant, nourished by root, follows its own definition of growth. It's just a "tree" that grows little by little. I want to see pulsing creatures.
Make such an image while reading and writing the text code Are you smirking yourself? !! (* ´з`) It means that you are feeling your own growth (laughs).
Next is remove. As mentioned earlier, Add starts with root and I am taking action to find the relevant part and add Node at any time. Therefore, remove is the same, Go to root to find the Node you want to remove.
It's a little complicated. It may be too difficult to think about, In that case, please plunge. m (_ _) m
Let's go. As mentioned above, everything starts with root. It's over if you have what you want as root If root doesn't have a key in the first place, it's over, right? ??
test.py
def remove(self,key):
#Start from root with pointer as p.
p = self.root
#A flag that will be useful later, whether it came from the right or the left.
direction_is_left = None
while True:
#If root or Node doesn't have a key, return False and exit
if p.key is None:
print("root has no Node or tree has no Node that you want,faile")
return False
#If the key contained in Node matches the input key, break out while
if p.key == key:
print("find out the Node")
break
#If the key does not correspond to Node, select the direction of travel right or left according to the rules described above.
#At this time, give a value to the flag in the direction of travel.(direction_is_left)
else:
if p.key > key:
direction_is_left = True
p = p.left
else:
direction_is_left = False
p = p.right
As shown in the figure below, if the node you want to delete has no children and if it has only one child
How to delete it? ??
In that case, if you don't touch the parent .left or .right, you can't do anything.
So add a "parent" to the above description to make it easier to find the deleted node and identify its parent as well.
test.py
def remove(self,key):
p = self.root
parent = None #Sky(Kara)Prepare parents
direction_is_left = None
while True:
if p.key is None:
print("root has no Node or tree has no Node that you want,faile")
return False
if p.key == key:
print("find out the Node")
break
else:
#It doesn't matter whether you go to the right or the left, so set the value of p to p.left or p.right and
#Assign p as parent before updating.
parent = p
if p.key > key:
direction_is_left = True
p = p.left
else:
direction_is_left = False
p = p.right
I will post it again!
If you have none or one child, you are concentrating on the left or right part.
test.py
#There is no right, yes, it refers to the case of the left part
if p.right is None:
#From the perspective of parents, p came from the left, right?
if direction_is_left:
#In the above figure, in the case of the left, None is stored in the left of Node of 1.
#In the above figure, in the case of the right, Node 1 is possible for the left of Node of 4
parent.left = p.left
else:
#??↓ What is this? ('Д').. I'm sorry, as shown below.
parent.right = p.left
But there are times when you want to remove root, for example, right?
In the above description, there is no node on the right side, so
You have to substitute the node on the left as root, right?
So, if you want to remove root, add it as well.
test.py
if p.right is None:
if p == self.root: #I want to delete root??
self.root = p.left #Now let's make the left Node root.
if direction_is_left:
parent.left = p.left
else:
parent.right = p.left
If this is the case without the right, It's the same even if there is no left, right? That's why I will also list the version without the left.
test.py
if p.left is None:
if p == self.root:
self.root = p.right
if direction_is_left:
parent.left = p.right
else:
parent.right = p.right
elif p.right is None:
if p == self.root:
self.root = p.left
if direction_is_left:
parent.left = p.left
else:
parent.right = p.left
So, this is the most difficult part,
What if you want to delete a Node that has two children?
You want to remove 5 as shown above.
Certainly, there was such a rule, right?
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ A binary search tree is a binary tree in which ** all nodes ** meet the following conditions. The node key of the left subtree is ** smaller ** than that node key The node key of the right subtree is ** larger ** than that node key ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
In other words, extract the maximum value from the child on the left part, If you can substitute it, you can connect with the child on the right, right?
That's right, if you have two children With the above idea, find the maximum value, Overwrite the Node you want to delete. As a post-processing, the maximum value found is deleted. Let's drop it into the code as shown in the figure, 4 is the maximum.
test.py
else:
#You may use the information in 5 later.
#Let's leave it as parent
parent = p
#Let the Node to the left of parent be left
left = p.left
#True because the direction of travel is to the left
direction_is_left = True
#As shown in the figure above, the Node of 4 corresponding to the left of 5 is
#It is the maximum value among the children on the left part.
#Let's rewrite the information of Node 5 to Node 4.
p.key = left.key
p.value = left.value
#Let's remove Node 4.
#Specifically, parent.left to left.Substitute 1 for left!!As it is(Lol)
if direction_is_left:
parent.left = left.left
#↓ What???this??
else:
parent.right = left.left
Finally there was a mysterious description.
One update that was closed peacefully,
What if the structure of the Tree is like this?
When branching from left to right
The value of right increases steadily.
So we have to add a way to find the maximum value.
test.py
else:
parent = p
left = p.left
direction_is_left = True
#Added right search!!
#left.Update left until right becomes None
while left.right is None:
#If you find the Node on the right, update parent and left
parent = left
left = left.right
#Declare that you came from the right with False
direction_is_left = False
p.key = left.key
p.value = left.value
if direction_is_left:
parent.left = left.left
#If you want to set the maximum value of Node found from the right,
#left.left to parent.Connect to right.
else:
parent.right = left.left
That's why remove has become a big volume.
test.py
def remove(self,key):
p = self.root
parent = None
direction_is_left = None
while True:
if p.key is None:
print("root has no Node or tree has no Node that you want,faile")
return False
if p.key == key:
print("find out the Node")
break
else:
parent = p
if p.key > key:
direction_is_left = True
p = p.left
else:
direction_is_left = False
p = p.right
if p.left is None:
if p == self.root:
self.root = p.right
if direction_is_left:
parent.left = p.right
else:
parent.right = p.right
elif p.right is None:
if p == self.root:
self.root = p.left
if direction_is_left:
parent.left = p.left
else:
parent.right = p.left
else:
parent = p
left = p.left
direction_is_left = True
while left.right is None:
parent = left
left = left.right
direction_is_left = False
p.key = left.key
p.value = left.value
if direction_is_left:
parent.left = left.left
else:
parent.right = left.left
return True
If you can imagine what you want to do with remove I think you can read it somehow. Thank you for your hard work (´ ー ｀) y- ~~
Recommended Posts