Binary Search Tree--Data Structure

Hash table

RangeSearch: impossible

NearestNeighbors: impossible

Insert: O(1)

Delete: O(1)

Array:

RangeSearch: O(n)

NearestNeighbors: O(n)

Insert: O(1)

Delete: O(1)

Sorted Array:

RangeSearch: O(logn)

NearestNeighbors: O(logn)

Insert: O(n)

Delete: O(n)

Linked List:

RangeSearch: O(n)

NearestNeighbors: O(n)

Insert: O(1)

Delete: O(1)

Search Tree Property

X’s key is larger than the key of any descendent of its left child, and smaller than the key of any descendant of its right child.

Operations:

Find(k,R)

if R.Key= k:

return R

else if R.Key> k:

return Find(k,R.Left)

else if R.Key< k:

return Find(k,R.Right)

Find (modified)

else if R.Key> k:

if R.Left!=null:

return Find(k,R.Left)

return R

Next(N)

if N.Right!=null:
return LeftDescendant(N.Right)

else:
return RightAncestor(N)

LeftDescendant(N)

if N.Left= null

return N

else:
return LeftDescendant(N.Left)

RightAncestor(N)

if N.Key< N.Parent.Key

return N.Parent

else:
return RightAncestor(N.Parent)

RangeSearch(x,y,R)

L←∅
N ←Find(x,R)

while N.Key≤ y

if N.Key≥ x:
L ←L.Append(N)

N ←Next(N)

return L

Insert(k,R)

P ←Find(k,R)
Add new node with keyk as child of P

Delete(N)

if N.Right= null:
Remove N, promoteN.Left

else:
X ←Next(N)

\\ X.Left= null
Replace N byX, promoteX.Right

Binary Search Tree--Data Structure

RotateRight(X)

P ←X .Parent
Y ←X.Left
B ←Y .Right
Y .Parent← P

P.AppropriateChild← Y

X.Parent← Y, Y.Right← X

B.Parent← X, X.Left← B

Binary Search Tree--Data Structure

相关推荐