an unbalanced tree is one whose root has many more left descendents than right descendantsor vice versa searching for node involves comparing the value to be found with the key value of nodeand going to that node' left child if the key search value is lessor to the node' right child if the search value is greater insertion involves finding the place to insert the new nodeand then changing child field in its new parent to refer to it an inorder traversal visits nodes in order of ascending keys preorder and postorder traversals are useful for parsing algebraic expressions when node has no childrenit can be deleted by setting the child field in its parent to null when node has one childit can be deleted by setting the child field in its parent to point to its child when node has two childrenit can be deleted by replacing it with its successor the successor to node can be found by finding the minimum node in the subtree whose root is ' right child in deletion of node with two childrendifferent situations arisedepending on whether the successor is the right child of the node to be deleted or one of the right child' left descendants nodes with duplicate key values may cause trouble in arrays because only the first one can be found in search trees can be represented in the computer' memory as an arrayalthough the reference-based approach is more common red-black trees overview as you learned in the last ordinary binary search trees offer important advantages as data storage devicesyou can quickly search for an item with given keyand you can also quickly insert or delete an item other data storage structuressuch as arrayssorted arraysand linked listsperform one or the other of these activities slowly thus binary search trees might appear to be the ideal data storage structure unfortunatelyordinary binary search trees suffer from troublesome problem they work well if the data is inserted into the tree in random order howeverthey become much slower if data is inserted in already sorted order ( or inversely sorted order ( when the values to be inserted are already ordereda binary tree becomes unbalanced with an unbalanced treethe capability to quickly find (or insert or deletea given element is lost this explores one way to solve the problem of unbalanced treesthe red-black treewhich is binary search tree with some added features