Definition: A binary tree is... umm... well, lets ditch formal definition (refer wikipedia for that). A binary tree represents a data-structure as this image:
The elements are called nodes. Each node can have at most two children. The top element is called root-node or just root. A binary search tree (BST) is one that has elements in its left subtree less than itself; and elements in its right subtree is higher than it[1]. If you remember quick sort earlier, any node in a BST is basically a pivot. Expected height[2] of a randomly build binary search tree with
Most operations in a BST is simple and recursive. I will list the algorithms here.
Successor and Predecessor: A successor of a node is a node which comes the next if we sort the tree in increasing order. A predecessor of a node is the node that comes immediately before it, if we sort the tree in increasing order. That is it. In a tree containing values
To find successor of a node we need to find immediate larger node. So, here is the algorithm:
Once you get the idea behind the successor, predecessor is easy.
Deletion: You must be wondering why I am covering
Now, if you read successor code properly, you will observe that if the successor chosen from right subtree, the successor will have at most one child. So, it is NOT going to be a recursive as in "delete a node with two children, then delete the successor with two children, and so on". NO. Just place the successor's value in node. Then clip the successor using either step
[1] The basic idea is to have elements less than the parent on one side and greater than the parent, on the other. And, whatever criteria you choose, it must apply to all the nodes. The most common is to have smaller in left, but if your rebel inner self does not want to conform to the standard go ahead, make a tree with higher in left.
[2] Refer Introduction to Algorithms - CLRS, Chapter 12 Binary Search Trees: 12.4 Randomly built binary search trees
[3] View/download Java code from GitHub, You can see sample output here.
The elements are called nodes. Each node can have at most two children. The top element is called root-node or just root. A binary search tree (BST) is one that has elements in its left subtree less than itself; and elements in its right subtree is higher than it[1]. If you remember quick sort earlier, any node in a BST is basically a pivot. Expected height[2] of a randomly build binary search tree with
n
elemements is lg(n)
where lg is log2.Most operations in a BST is simple and recursive. I will list the algorithms here.
Node value left right parent insert(root, node) // use two pointer, current to the place where new node will be inserted, // and parent holds it's parent reference val = node.val current = root parent = root // move in tree following BST rule, searching the place where this node // should be. This loop ends at a leaf, giving the future parent to the node while current != NIL if val < parent.value current = parent.left else current = parent.right parent = current // root was null, no tree was pre-exiting if parent = NIL node.parent // plug in the node to correct side of the parent if val < parent.value parent.left = node else parent.right = node //assign the parent node.parent = parent return root //iterative search(root, value) current = root found = false result = NIL while found = false and current != NIL if current.value = value result = current found = true else if value < current.value current = current.left else current = current.right return result //recursive search(root, value) if root = NIL or root.value = value return root if value < root.value return search(root.left, value) else return search(root.right, value) //min is left most node, right? Think about it. findMin(root) if root = NIL error("Nil BST?") min = root while min.left != NIL min = min.left return min //max, same as min but in right subtree findMax(root) if root = NIL error("Nil BST?") max = root while max.right != NIL max = max.right return max //in order traversal, prints sorted node values inOrderTraversal(root) if root = NIL return inOrderTraversal(root.left) print root.value inOrderTraversal(root.right)So, these were the easier ones. With a little effort one can understand these. I will now discuss, some of the harder ones.
Successor and Predecessor: A successor of a node is a node which comes the next if we sort the tree in increasing order. A predecessor of a node is the node that comes immediately before it, if we sort the tree in increasing order. That is it. In a tree containing values
1 3 5 6 7 9
, the successor and predecessor of 5
are 6
and 3
, respectively.To find successor of a node we need to find immediate larger node. So, here is the algorithm:
- The right subtree of the node will contain the values larger than the node. (right?) If we find the lowest node in right subtree we will have the immediate larger node, and we get our successor.
- What if the node does not have a right subtree? We will have to go up in the tree somewhere. See the image below.
- If the node is left child, the parent will the immediate next.
- If the node is right child, we need to keep moving up until we get a node whose left child is one of the node's parents.
Once you get the idea behind the successor, predecessor is easy.
- Predecessor is highest in left subtree.
- If there exists no left subtree, then:
- If the node is right-child, immediate parent is the predecessor.
- If the node is left child move up till you get a node whose right child is one of the node's parents.
Deletion: You must be wondering why I am covering
delete
so late? That's because it's so damn hard without understanding the concepts above. So, here is the algorithm to delete a node:- If the node had no child, well just knock it off.
- If it has one child, yank the node and connect the child to the node's parent.
- If it has two children, then we need to get a replacement for this node. What would be a good replacement? A good replacement is the one that on replacement, maintains the BST property. (At this moment I want you to pause, and think if you have to replace this node who could be the best candidate?) You can choose either the successor or the predecessor. The common practice is too use successor (further discussion assumes we replaced with successor). And then delete the successor from the subtree.
Now, if you read successor code properly, you will observe that if the successor chosen from right subtree, the successor will have at most one child. So, it is NOT going to be a recursive as in "delete a node with two children, then delete the successor with two children, and so on". NO. Just place the successor's value in node. Then clip the successor using either step
1
or step 2
.successor(node) //if exists a right subtree if node.right != NIL return findMin(node.right) parent = node.parent // if it is left child this loop wont executeoutput here // else move up until a we get first right parent while parent != NIL and parent.right = node node = parent parent = parent.parent return parent predecessor(node) //if exists a left subtree if node.left != NIL return findMax(node.left) parent = node.parent // if it is left child, this loop wouldn't execute // else move up till a left parent arrives while parent != NIL and parent.left = node node = parent parent = parent.parent return parent delete(node) // leaf node if node.left = NIL and node.right = NIL if node = node.parent.left node.parent.left = NIL else node.parent.right = NIL // half node if node.left = NIL node.right.parent = node.parent if node.parent.left = node node.parent.left = node.right else node.parent.right = node.right else if node.right = NIL node.left.parent = node.parent if node.parent.left = node node.parent.left = node.left else node.parent.right = node.left // complete node successor = successor(node) node.value = successor.value delete(successor)Footnotes:
[1] The basic idea is to have elements less than the parent on one side and greater than the parent, on the other. And, whatever criteria you choose, it must apply to all the nodes. The most common is to have smaller in left, but if your rebel inner self does not want to conform to the standard go ahead, make a tree with higher in left.
[2] Refer Introduction to Algorithms - CLRS, Chapter 12 Binary Search Trees: 12.4 Randomly built binary search trees
[3] View/download Java code from GitHub, You can see sample output here.
شركة تخزين عفش بنجران
ReplyDeleteشركة عزل خزانات بنجران
شركة تعقيم خزانات بنجران
شركة صيانة خزانات بنجران
شركة غسيل خزانات بنجران
شركة صيانة مسابح بنجران
شركة تنظيف الاثاث بنجران
شركة جلي بلاط بنجران
شركة تنظيف شقق بنجران
شركة نقل عفش بنجران
شركة تنظيف موكيت بنجران
شركة تنظيف مجالس بنجران
شركة تنظيف مسابح بنجران
شركة تنظيف بنجران
شركة تنظيف ستائر بنجران
شركة مكافحة حشرات بنجران