Channi Studies

Heaps Concept때때로 프로그램들은 변화하는 데이터 셋에서 최대/최소값의 아이템을 빠르게 접근하고 제거할 수 있는 능력이 필요합니다. 이럴 때 힙 자료 구조는 아주 유용합니다. Max-HeapMaintaining jobs in fully-sorted order requires more operations than necessary, since only the maximum item is needed. A max-heap is a complete binary tree that maintains the simple property that a node's key is greater than equal to the node's children's keys. (Max heap, 최대힙은 어떤 트리 구조..

Insertion AlgorithmGiven a new node, a red-black tree insert operation inserts the new node in the proper location such that all red-lack tree requirements still hold after the insertion completes. It begins by calling BSTInsert to insert the node using the orginary BST insert rules. The newly inserted node is red colored and then a balance operation is performed on this node. RBTreeInsert(tree,..

A red-black tree is a BST with two node types, namely red and black, and supporting operations that ensure the tree is balanced when a node is inserted or removed. Rules:Every node is colored either red or black.The root node is black.A red node's children cannot be red. A null child is considered to be a black leaf node.All paths from a node to any null leaf descendant node must have the same n..

AVL InsertionsInserting an item into an AVL tree may cause the tree to become temporarily unbalanced. A rotation can rebalance the tree.If you have read the pseudocode of rotation carefully, you would've noticed that there is a case labeled as Double Rotation case, where we need to apply two rotations for rebalancing. In the following case, we apply double right rotation at C to rebalance the AV..